상태 반전이 가능한 문제 [ 문제 ]문자열 길이 4인 0100이 주어졌을 때, 부분 문자열을 고르면, 해당 문자열 내 문자들이0은 1, 1은 0으로 반전이 일어난다고 한다.이때, 부분 문자열을 적절하게 골라 최소 횟수로 문자열이 1111이 되도록 하세요.  [ 접근 방법 ]0100에서 [2,2] 구간을 0000으로 만든 뒤, [1,4] 구간을 뒤집으면 1111이 되므로 최소 횟수는 2가 된다.먼저, 다음과 같이 생각을 해보자.전부 숫자 1을 만들기 위해 뒤집어야 하는 구간 끼리는 어떤 관계가 있을까?문제 특성상, 두 구간이 겹치는 곳에 있는 문자들은 2번 뒤집히기 때문에 결국 뒤집히지 않은 것과 같다.즉, 2번 뒤집혔다는 것은, 뒤집지 않았다는 것과 같다.이는 곧, 뒤집을 필요가 없다는 말과도 같다.예를..

Binary Search [ 문제 ][4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 숫자 2가 위치하는 인덱스 값을 찾는프로그램을 작성하시오.   [ 해결책(1) - O(N) ]무작정 코드를 작성한다면, 아래 코드처럼 처음부터 끝까지 O(N)만큼 해당 숫자가 나올때까지 검색해야 할 것이다.123456789101112131415161718public class Main {    public static void main(String[] args) {        int n = 6, target = 2;        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};         int idx = -1;         for(int i=1; i=n; i++){ ..

Two Pointer [ 문제 ][4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 특정 구간을 선택하여 구간 내 숫자의 합이 10이 넘지 않으면서 가장 큰 구간의 크기를 구하는 프로그램을 작성하시오.  [ 해결책(1) - O(N^2) ]무작정 코드를 작성한다면, 아래 코드처럼 모든 구간 O(N^2)개를 잡아보면서 합이 10을 넘지 않는 경우 중 구간 크기의 최댓값을 구한다. 123456789101112131415161718192021222324252627282930313233public class Main {    public static void main(String[] args) {        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};       ..

PreProcessing [ 문제 ][4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 특정 위치를 적절하게 선택하여 해당 위치에 놓여있는 숫자와 그 숫자를 포함하여 뒤에 놓여 있는 숫자들 중 최솟 값을 곱한 값이 최대가 되도록 프로그램을 작성하시오.  [ 해결책(1) - O(N^2) ]1번째 위치를 선택하게 되면, 1이 최솟값이므로 4*1 = 4 가 된다.5번째 위치를 선택하게 되면, 3이 최솟값이므로 7*3 = 21 이 된다.그러므로, 5번째 위치가 나오도록 하면 된다.무작정 코드를 작성하게 되면, 각 위치를 한번 씩 잡아보면서 그 뒤에 있는 숫자 전부를확인하면 O(N^2)이 된다.  [ 해결책(2) - O(N) ] 그러나, 만약 R이라는 배열을 R(i) = i 번째부터 N 번째까지 미..