자료구조 및 알고리즘

이분 탐색(Binary Search) 탐색(search) 기법 중 하나로, 정렬된 배열에서 찾고자하는 값을 탐색할 때 그 범위를 두 부분으로 나누어(=이분) 탐색하는 방법이다. 탐색하고자 하는 범위를 계속해서 줄여감으로써 시간 효율성을 O(logN)까지 올릴 수 있다. 탐색 범위를 줄이는 방법은 다음과 같다. 범위의 가장 중앙 인덱스(mid)의 값과 찾고자 하는 값을 비교한다. 찾고자 하는 값이 해당 인덱스(mid) 값보다 클 경우 범위는 해당 인덱스(mid)의 바로 뒤(mid + 1)부터 탐색 범위의 마지막 인덱스(처음에는 끝 인덱스)까지이다. 다시 정의된 범위에서 가장 중앙 인덱스의 값과 비교한다. (mid 값 변경) 찾고자 하는 값이 중앙 인덱스 값보다 작을 경우 범위는 탐색 범위의 시작 인덱스부터..

문제(백준 캡쳐) 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(String str) { int answer = 0, idx = 0; char[] stack = new char[str.length()]; stack[idx++] = '('; for (int i = 1; i < str.length(); i++) { char c = str.charAt(i); if (c == '(') stack[idx++] = c; else { if (c == str.charAt(i - 1)) { stack[--idx] = ' '; answer++; } else { stack[--idx] = ' '; answer += idx; } } } ..

문자열 S와 T가 주어지고, S에서 문자열 T와 아나그램이 되는 부분문자열의 개수를 출력하는 문제이다. 첫 줄에 S가, 다음 줄에 T가 입력된다. 주어지는 문자열의 각 문자를 해싱해서 문자의 개수를 value로 삼는 것이 기본이 된다. 여기에 문자 T는 항상 S보다 짧은 문자열이고, S 내에서 T와 아나그램인 연속되는 문자를 찾는 것이기 때문에, T의 길이만큼 sliding-window 알고리즘 기법을 사용하면 된다. 사실 처음에 two-pointer 알고리즘 기법도 함께 적용하려 했으나 다른 문제로 실패하면서 보류하게 되었다. 이후에 코드를 개선할 때 추가할 예정이다. 많은 시간이 소요된 부분 two-pointer, sliding-window 알고리즘을 사용하기 위해 문자열 T를 해싱할 때 S 문자열의..

0과 1로 구성된 길이가 N인 수열이 주어지면, 이 수열에서 최대 k번 0을 1로 변경할 수 있습니다. 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하는 문제이다. 첫 줄에 수열의 길이인 자연수 N(5

N개의 수로 이루어진 수열이 주어지면, 이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 문제이다. 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(int n, int m, int[] arr) { int answer = 0; for (int i = 0; i m) break; } } return answer; } public static void main(String[] args..

N일 동안의 매출 중 연속 K일 동안의 최대 매출액을 출력하는 문제다. 첫 줄에 N(5

초기 작성 코드 import java.util.*; public class Main { private List solution(List a, List b) { List answer = new ArrayList(); answer.addAll(a); answer.addAll(b); Collections.sort(answer, new Comparator() { @Override public int compare(Integer o1, Integer o2) { return o1 > o2 ? 1 : o1 < o2 ? -1 : 0; } }); return answer; } public static void main(String[] args) { Main al = new Main(); Scanner sc = new S..

봉우리란, N*N 형태의 격자판에서 주변(상하좌우)의 값보다 높은 값을 가지는 인덱스들이 봉우리가 된다. 주변과 같은 값이 있다면 봉우리가 아님에 유의하자. + 격자판은 0으로만 구성된 행, 열에 감싸진다. (격자판의 상하좌우 마지막 행, 열은 모두 0으로 구성되어있다.) 초기 작성 코드 import java.util.Scanner; public class Main { private int solution(int n, int[][] grid) { int answer = 0; for (int i = 1; i grid[i][j + 1]) { if (grid[i][j] > grid[i - 1][j] && grid[i][j] > grid[i + 1][j]) { answer++; } } } } return ans..

자연수 N이 주어지면 N*N 만큼 숫자가 주어진다. 이 격자판에서의 각 행, 열, 대각선의 합 중 가장 큰 값을 구하는 문제이다. 초기 작성 코드 import java.util.Scanner; public class Main { private int solution (int num, int[][] grid) { int answer = 0; // 행의 합 중 가장 큰 값 도출 for (int i = 0; i answer) answer = sum; } // 열의 합 중 가장 큰 값 도출 for (int i = 0; i < num; i++) { int..

문자열 뒤집기 문자열을 입력받는 부분의 코드는 아래와 같다. 여기서는 실제 문제를 해결해 답안을 도출해내는 solution 메서드만 추가적으로 작성하겠다. (import문도 생략한다.) import java.util.Scanner; public class Main { public static void main(String args[]) { Main main = new Main(); Scanner sc = new Scanner(System.in); String str = sc.nextLine(); System.out.println(main.solution(str)); } } 1. 직접 문자열을 뒤집는 방법 1) 가장 간단하게는 직접 문자열을 뒤집는 방법이 있다. 여기에도 가장 원초적인 방식으로는 문자열의 ..