[코드트리] 1 - 완전 탐색, 최적화에 대한 고찰 및 공부 후기

상세 학습 계획

매일 문제를 시간나는데로 풀고 정리할 토픽이 있으면 문제 - 내 코드 - 풀이 과정 및 배운점을 정리, 요약해서 나중에 다시 볼 수 있도록 했다. 풀이 코드에는 편의상 import문은 생략했다.

 

 갭 체크상 내 부족한 지식은 완전탐색 분류 아래에 있는 것들이고 막상 챕터 로드맵을 열어보니 풀 문제가 많고 개념 확장에 포커싱되어 있었다. 계획은 최대한 많이 풀고 만약 입력 제한이 커진다면 어떻게 해야 하고 발상을 전환하는 연습에 집중할 것이다.

브루트 포스가 메인 주제이긴 하지만 그것을 적절히 가지치기하고 최적화한 노력의 흔적을 담고자 했다.

 

그리고 풀긴 했어도 본인이 다른 사람에게 설명할 수 없다면 모르는 거라 생각해서 그런 문제들은 (다시 보기) 태그를 달아 밥먹거나 짜투리 시간마다 빠르게 다시 훑어보며 읽기로 했다. 

---

문제 - 최고의 13위치

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-best-place-of-13/description

최고의 13위치 설명 | 코드트리

슬라이딩 윈도우 풀이

public class Main {
    static int[][] board;
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = board[0][0] + board[0][1] + board[0][2];
        for(int i = 0; i<N; i++){
            int curSum = board[i][0] + board[i][1] + board[i][2];
            ans = Math.max(ans, curSum);
            for(int j = 3; j<N; j++){
                curSum -= board[i][j-3];
                curSum += board[i][j];
                ans = Math.max(ans, curSum);
            }
        }
        System.out.print(ans);
    }
}

누적합 최적화 풀이

public class Main {
    static int[][] board;
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N+1][N+1];
        int[][] ps = new int[N+1][N+1];

        for(int i = 1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                // 현재값 + 같은 열에서 위에까지 누적된거 + 같은 행에서 왼쪽에서 누적된거 
                // 격자니까 왼쪽위가 겹치니까 ps[i-1][j-1]를 한번 빼 줌.
                ps[i][j] = board[i][j] + ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
            }
        }

        // 슬라이딩 윈도우 구간 크기(2차원)
        int r = 1;
        int c = 3;

        int ans = 0;
        for(int i = 1; i<=N-(r-1); i++){
            for(int j = 1; j<=N-(c-1); j++){
                int si = i;
                int sj = j;
                int ei = i+r-1;
                int ej = j+c-1;
                
                // ei,ej까지 전체에서 si 전에 오는 위쪽 사각형을 빼고 
                // sj 전까지 오는 왼쪽 사각형을 빼면
                // 왼쪽 위 사각형이 겹쳐져서 두번 빠졌으니
                // si-1 sj-1을 마지막에 한번 더해줌
                int curSum = ps[ei][ej] - ps[si-1][ej] - ps[ei][sj-1] + ps[si-1][sj-1];
                ans = Math.max(ans, curSum);
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

그냥 봤을땐 완전탐색하라는거 같긴 한데 1*3이라서 row 마다 슬라이딩 윈도우를 해줄수도 있고 

확장해서 보면 결국 직사각형 모양의 구간에서 최대 합의 값을 구하는 것이라고 생각이 들었음. 

그리고 실전에서는 이렇게 제한이 작은 문제는 나오지 않으니 큰 값으로 제한을 상상하고 직사각형도 엄청 크다고 생각해보면

그 구간 안에서 또 직사각형 내의 값들을 다 더하거나 해서 연산하는건 그만큼 곱해져 시간복잡도에 악영향을 끼친다.

 

현재 문제에서는 구간이 작아서 O(N^2 * 3) = O(N^2)지만 직사각형이 엄청 크고 직사각형 넓이가 K*K라면

O(N^2 * K^2)가 되는 문제가 발생한다. 이를 해결하기 위해 누적합 전처리를 하게 되면 이게 O(1)이 되므로 상수화되어 전체 시간복잡도는 O(N^2)가 된다. 

-> 직사각형 구간의 크기가 매우 클 때 시도해볼 것

---

문제 - 마라톤 중간에 택시타기

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-taking-a-taxi-in-the-middle-of-the-marathon-2/description

마라톤 중간에 택시타기 2 설명 | 코드트리

public class Main {
    static int N;
    static int[][] A;
    // A의 인덱스 번호
    static ArrayList<Integer>[] g;
    static int getDist(int[] a, int[] b){
        return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
    }

    // 0번에서 시작
    static long getTot(int invalid){
        // 시작 번호, 거리
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0,0});

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int ci = cur[0];
            int cd = cur[1];

            if(ci == N-1)
                return cd;

            if(ci == N-2)
                q.add(new int[]{ci+1, cd + getDist(A[ci], A[ci+1])});
            else{
                int ni, nd;
                if(ci + 1 == invalid)
                    ni = ci + 2;
                else
                    ni = ci + 1;
                nd = cd + getDist(A[ci], A[ni]);
                q.add(new int[]{ni,nd});
            }
        }
        return -1;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N][2];
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            A[i] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
        }

        // 매번 전체 연산하는 대신 선택하거나 말거나니까 누적합 해보는건 어떨지
        long ans = 100 * 1_000_000 + 1;
        // for(int i = 1; i<N-1; i++){
        //     ans = Math.min(ans, getTot(i));
        // }
        long total = 0;
        for(int i = 0; i<N-1; i++){
            total += getDist(A[i], A[i+1]);
        }

        for(int k = 1; k<N-1; k++){
            long cur = total - getDist(A[k-1], A[k]) - getDist(A[k],A[k+1]) + getDist(A[k-1],A[k+1]);
            ans = Math.min(ans, cur);
        }

        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

일단 경로가 1가지로 고정되어 있으나 A[i]를 한 정점으로 보면 그래프로 나타낼 수 있고, 이는 건너뛸 정점 K를 하나 설정해서 매번 전체 경로를 다시 bfs로 재탐색하는 것으로 처음에 풀었었다. 그러나 bfs는 어떤 경로가 많을때 최단경로를 구하거나 뭐 그런게 있을때 쓰는것이지 굳이 필요 없을것 같았다. 

 

문제 조건을 다시 확인해보면 하나의 정점만 스킵 이라고 되어있다. 그러면 원래 전체 경로를 구해놓고 해당 지점만 빠졌을 때 전체 합을 O(1)로 계산할 수 있을 것이다. 먼저 전체 합을 total로 거리를 계산해놓고 빼야 할 후보 지점 (인덱스상 [1, N-2]) 을 순회하며 구한다. 

 

기존 시간 복잡도 O(N^2) -> 누적합 버전 O(N)

뭔가 완탐 공부 과정에서 자꾸 누적합이 나오는거 같다..

---

문제 - 원 모양으로 되어있는 방

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-a-room-in-a-circle/description

원 모양으로 되어있는 방 설명 | 코드트리

public class Main {
    static int N;
    static int[] A;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        A = new int[N];

        int total = 0;
        // 계속 미는거라서 거리가 각각 1씩 줄어들어서 
        // 전체 사람 수만큼 다음거 계산할때 빼줘야함
        int sum = 0;
        for(int i = 0; i<N; i++){
            A[i] = Integer.parseInt(br.readLine());
            total += i * A[i];
            sum += A[i];
        }

        int ans = total;
        int prev = total;
        for(int s = 1; s<N; s++){
            int next = prev - sum + N*A[s-1];
            prev = next;
            ans = Math.min(ans, next);
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

일단 원형으로 들어온다 하니 직접 구현한다 하면 2배로 늘리거나 나머지연산 써야 하겠는데 그렇게 하면 O(N^2) 풀이 일 것이고 문제의 초점도 인원 * 각 거리의 합이 중요한거라 초기 합 구해주고 시작점을 한칸 밀면 초기 합에 무슨 상태 변화가 일어나는지에 포커싱을 둬서 O(N)으로 접근하기로 했다. 

 

Rolling Sum : 점화식 유도

주어진 예제를 보면 N = 5일때 거리만 보자.

0 1 2 3 N-1 임

근데 시작점을 index 1로 밀게 되면 거리 cost는 다음과 같음

N-1 0 1 2 3임

index 1의 경우 거리가 1->0으로 1 줄어들고 다른 index들도 마찬가지임 

-> 사람 총 인원수만큼 previous에서 빼줌 

-> ? 0 1 2 3

시작점 바로 앞에 있던건 N-1만큼 이동했으나 아까 sum을 빼면서 이미 -1이 들어가 있음.

-> (-1 + N) 0 1 2 3

-> N * A[ start - 1] 을 마지막에 더해줘야 함

점화식

-> newCost = prevCost - sum + N * A[ startPos - 1 ]

이제 이 rolling sum을 매번 ans에 최소값으로 갱신하고 출력하면 끝

 

---

문제 - COW 2

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-c-o-w-2/description

씨 오 더블유 2 설명 | 코드트리

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String in = br.readLine();
        char[] t = in.toCharArray();
        
        int ans = 0;
        // for(int i = 0; i<N-2; i++){
        //     if(t[i] != 'C')
        //         continue;
        //     for(int j = i+1; j<N-1; j++){
        //         if(t[j] != 'O')
        //             continue;
        //         for(int k = j+1; k<N; k++){
        //             if(t[k] == 'W')
        //                 ans++;
        //         }
        //     }
        // }
        int cc = 0;
        int co = 0;
        int cw = 0;
        for(int i = 0; i<N; i++){
            if(t[i] =='C')
                cc++;
            if(t[i] == 'O')
                co += cc;
            if(t[i] == 'W')
                ans += co;
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

단순하게 조건에 맞춰서 O(N^3) 풀이도 맞긴 한데 실전에서 세제곱 시간복잡도가 통과하는걸 본적이 없다.

-> counting DP 느낌으로 O(N)으로 최적화하는 기법이 있다.

Counting DP : 부분수열 경우의 수 세기

여기서 COW는 원본 문자열의 부분수열이다. C다음에 O를 붙이고 O다음에 W를 붙여서 만드는 부분수열.

문자열을 왼쪽부터 보면서 A[0 , i] 까지 보면서 누적하는 방식이고 dp배열은 생략하고 경우의 수만 누적해서 구현했다.

각 문자열의 경우의 수에 대한 점화식은 아래와 같다.

C(i)   = i번째까지 봤을 때 "C" 부분수열 개수
CO(i)  = i번째까지 봤을 때 "CO" 부분수열 개수
COW(i) = i번째까지 봤을 때 "COW" 부분수열 개수

 

즉, COW( i ) = CO( i-1 ) + W( i-1 ) 이라는 것이다.

부분수열 DP의 점화식은 보통 dp[next] += dp[prev]로 나타내고 지금 문제의 경우 현재까지 가능한 경우의 수만 기억하면 된다.

---

문제 : 최고의 13위치 2

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-best-place-of-13-2/description

최고의 13위치 2 설명 | 코드트리

import java.util.*;
import java.io.*;

/*
2차원 슬라이딩 윈도 합 
= ps[시작점+i크기-1][시작점+j크기-1] - ps[i시작점-1][j끝점] - ps[i끝점][j시작점-1] + ps[i시작점-1][j시작점-1]
*/

public class Main {
    static int N;
    static int[][] board;
    static int[][] ps;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        board = new int[N+1][N+1];
        ps = new int[N+1][N+1];

        for(int i = 1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=N; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1*3 전처리
        for(int i = 1; i<=N; i++){
            int cur = board[i][1] + board[i][2] + board[i][3];
            ps[i][1] = cur;
            for(int j = 2; j<=N-2; j++){
                cur -= board[i][j-1];
                cur += board[i][j+2];                
                ps[i][j] = cur;
            }
        }

        int ans = 0;
        // 다른행, 위쪽에서의 최대
        int upMax = 0;
        for(int i = 1; i<=N; i++){
            // 같은행, 왼쪽에서부터의 최대
            int[] leftMax = new int[N+1];
            for(int j= 1; j<=N-2; j++){
                leftMax[j] = Math.max(j>=2 ? leftMax[j-1] : 0, ps[i][j]);
            }

            for(int j = 1; j<=N-2; j++){
                // 1. 두 윈도가 서로 다른 행에 있을땐 위쪽기준 max값에 현재값 더한거 비교
                ans = Math.max(ans, upMax + ps[i][j]);
                // 2. 두 윈도가 같은 행에 있을땐 왼쪽기준 max값에 현재값 더한 거 비교
                if(j >= 4){
                    ans = Math.max(ans, leftMax[j-3] + ps[i][j]);
                }
            }

            // 행이 다를때 쓸 위쪽기준 최대값 갱신
            // -> 한 행 통째로 sum값 죄다넣고 최대로
            for(int j = 1; j<=N-2; j++){
                upMax = Math.max(upMax, ps[i][j]);
            }
        }
        
        System.out.print(ans);
    }
}

사고의 흐름 및 문제 정리

처음에는 두개의 슬라이딩 윈도니까 그냥 2차원 누적합 구한다음에 적당히 시작위치 찾아가지고 비교하면 되겠다고 생각했다.

근데 문제를 오해를 해서 무조건 2번째가 다른 행에 있다고 착각해서 WA 났고, 같은 행에 있다고 하고 대충 abs로 서로 시작점 위치 비교해서 3칸 확보 안되면 스킵하게 하니까 되긴되는데 시간복잡도가 사실상 O(N^4)라서 AC긴 하지만 납득할 수 없었다.

 

누적합의 누적을 하던지 아니면 덱같은거 크기 고정해놓고 최대값, 최소값 유지하면서 갱신시키는거처럼 현재 max값을 저장해서 유지하면서 갱신하기?? 어차피 최대를 구하는 거고 단조적이니까 괜찮을 거 같았다.

-> 두번째 직사각형 관점에서는 첫번째의 최적값만 보면 된다는 느낌?

 

풀이 : Prefix max 활용

그러면 이걸 어떻게 압축하느냐?? 일단 다행히도 윈도 크기는 1*3이다. 

머리아픈 2차원 누적합이나 각 축을 기준으로 해서 2개의 deque를 사용한 슬라이딩 윈도 이런건 안해도 될 거 같다..

따라서 행단위로 3칸짜리 합을 계산한 prefix sum 배열을 구해놓는다. 시작점이 4 넘어가면 (1-based) 이므로 슬라이딩 윈도로 빠르게 구하는 방식으로 일단 전처리를 한다.

 

문제의 목표는 두 구간의 합이 최대로 되는 값을 찾는 것이고 그 전꺼의 최대 + 현재값을 한게 최대라면 갱신하면 된다는 것이다.

이 문제에서는 가능한 상태의 경우가 2개이다.

 

1) 같은 행 안에서의 구간 2개 

-> 이는 이전 열 idx까지의 최대값을 저장하는 leftMax 배열을 생성해서 미리 계산한다. 

-> 그리고 시작점 기준이므로 j-3 인덱스의 leftMax 값에 현재 위치 합을 더하면 현재까지의 최대 합이 된다.

 

2) 다른 행 안에서의 구간 2개

-> 이건 어차피 다른 행이라서 이전 행까지의 최대값(upMax)을 가져오면 되니까

한 행의 prefix sum 배열값을 다 보면서 갱신한다. 

 

upMax는 그냥 int 변수로 유지하고 순차 DP 구조를 유지하기 위해 제일 마지막에 계산한다.

-> 왜냐하면 마지막에 계산해야 첫번째 행을 연산할때 0으로 유지되어 올바른 값을 띄게 된다.

---

문제 - 아름다운 수열 2

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-beautiful-sequence-2/description

아름다운 수열 2 설명 | 코드트리

public class Main {
    static int N,M;
    static int[] A,B;

    static boolean isSame(int[] a, int[] b){
        for(int i = 0; i<a.length; i++){
            if(a[i] != b[i])
                return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        if(M>N){
            System.out.print(0);
            return;
        }

        A = new int[N];
        B = new int[M];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int[] countA = new int[101];
        int[] countB = new int[101];
        for(int i = 0; i<M; i++){
            B[i] = Integer.parseInt(st.nextToken());
            countA[A[i]]++;
            countB[B[i]]++;
        }

        int ans = 0;
        //초기 윈도 검사
        if(isSame(countA, countB))
            ans++;

        for(int i = M; i<N; i++){
            countA[A[i-M]]--;
            countA[A[i]]++;
            if(isSame(countA, countB))
                ans++;
        }

        System.out.print(ans);
    }
}

사고의 흐름 

일단 A에서 M크기의 연속된 구간을 잡고 문제의 아름다운 수열 정의에 따르면 B를 재배열한 모든 가능한 경우가 아름다운 수열이라 하고 이는 결국 순서는 달라도 조합은 같으므로 빈도수로 나타내면 하나의 정보로 압축된다. 

조건 비교용으로 countB를 해 두고 countA는 M크기의 슬라이딩 윈도로 한다.

 

풀이 : 슬라이딩 윈도 + 빈도수 배열

여기서 만약 M이 N보다 커버리면 어떻게 해도 B의 빈도수랑 A의 빈도수가 같을 수 없으므로 

바로 0을 출력하고 끝낸다. 

 

초기에 M크기의 구간 빈도를 B를 입력받으면서 같이 갱신해주고 슬라이딩 윈도를 들어가기 전에 

isSame 함수로 조건체킹해서 두 빈도수 배열이 일치하는지 본다. 

 

그리고 구간의 끝 부분을 잡고 N-1까지 돌리면서

빈도수 배열 [ 현재 끝점 - 구간크기(M) ] -1 을 해주고 [ 현재 끝점 ] + 1을 해준다.

그렇게 업데이트된 빈도수 배열이 정확히 일치하면 정답 +1 해주면 끝.

---

문제 - 바구니 안의 사탕 2

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-candy-in-the-basket-2/description

바구니 안의 사탕 2 설명 | 코드트리

public class Main {
    static int N, K;
    static int[] A;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        A = new int[101];
        int[] ps= new int[102];
        int minIdx = 102;
        int maxIdx = -1;

        // 유효한 idx가 중앙값으로 잡혀야될듯
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int candy = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken());
            minIdx = Math.min(minIdx, idx);
            maxIdx = Math.max(maxIdx, idx);
            // 같은 위치에 여러 바구니 가능!!!!
            A[idx] += candy;
        }

        for(int i = 0; i<101; i++){
            ps[i+1] = A[i] + ps[i];
        }
        
        int ans = 0;
        for(int s = minIdx; s<=maxIdx; s++){
            // 이상 이하라서 끝점에 +1
            int curSum = ps[Math.min(100, s+K)+1] - ps[Math.max(0, s-K)];
            ans = Math.max(ans, curSum);
        }    
        System.out.print(ans);
    }
}

사고의 흐름

일단 위치가 0~100이라 각 위치마다 사탕 갯수를 누적해서 입력받는 배열을 만들었음.

그리고 입력 순서가 idx - candy가 아니고 candy - idx이고 중복된 위치가 있어서 사탕 갯수 입력시 누적해줘야한다. 

일단 위치 범위가 적으니 모든 위치를 따라가면서 prefix sum을 구해둔다. 이러면 O(1)에 구간합을 구할 수 있다.

 

풀이

일단 모든 구간을 보는건 비효율적이고 입력받을때 valid한 위치 최소 최대값을 구해서 그걸 탐색 최소, 최대값으로 잡는다.

-> 왜냐하면 사탕바구니가 없는 구간은 어차피 0이라서 볼 필요도 없고 시간복잡도 낭비다.

여기서 구간은 끝점을 모두 포함하므로 prefix sum 기준 [ right + 1 ] - [ left ] 가 해당 구간합이 된다. 

구간합 최대로 갱신하면 끝

 

주의점 : prefix sum기준으로 돌땐 1-based라서 N까지 다 돌아야 끝까지 다 볼 수 있음

---

문제 - G or H 2 (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-G-or-H-2/description

G or H 2 설명 | 코드트리

public class Main {
    static int N;
    // 위치 저장
    static int[] pos;
    // 해당 위치에 각 알파벳 몇개 있는지
    static int[] g = new int[101];
    static int[] h = new int[101]; 

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        pos = new int[N];
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            pos[i] = idx;
            char c = st.nextToken().charAt(0);
            if(c == 'G')
                g[idx]++;
            else
                h[idx]++;
        }

        Arrays.sort(pos);
        // 위치 종류 갯수만큼 해야함 + 1
        int[] psG = new int[N+1];
        int[] psH = new int[N+1];

        for(int i = 0; i<N; i++){
            psG[i+1] = psG[i] + g[pos[i]];
            psH[i+1] = psH[i] + h[pos[i]];
        }

        int ans = 0;
        for(int i = 0; i<N-1; i++){
            for(int j= i; j<N; j++){
                int countG = psG[j+1] - psG[i];
                int countH = psH[j+1] - psH[i];
                if((countH == 0 && countG != 0) || (countH != 0 && countG == 0) || (countH == countG && countH != 0))
                    ans = Math.max(ans, pos[j]-pos[i]);   
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름

문제를 보고 h와 g를 위치별로 쭉 놓고 계산하는 누적합 배열 각자 한개씩 놓고 각자 세서 조건에 맞는지 보기??

아니면 파라메트릭 서치를 써서 조건에 맞으면 갱신하는 방식으로 해도 될거 같긴 했는데 당장 떠오르는 구현도 없고 누적합 풀이는 O(N^2)인데 파라메트릭 서치는 O(N^2 * log (가능한 diff) ) 이므로 더 느리니까 고려하지 않았다.

 

풀이 : 누적합 배열 2개 + 위치 배열 정렬

일단 누적합 배열을 g와 h를 따로 관리하고 입력이 위치 오름차순으로 들어오지 않고, valid 한 위치에서 사람간 간격으로 최대 사진 크기를 최대값으로 갱신해야 하므로 pos 배열을 둬서 위치를 입력받고 정렬한다.

입력받을 때 g와 h를 위치에 존재하는지를 int로 저장해서 prefix sum을 계산할때 용이하도록 했다.

 

그리고 prefix sum 배열은 각자 쓰고 1-based 이므로 j+1 - i를 하면 현재 구간에서의 각 G와 H의 갯수를 구할 수 있다. 

문제 조건에 맞으면 j와 i는 인덱스일 뿐 실제 위치가 아니므로 pos[ j ] - pos [ i ] 를 최댓값으로 갱신한다.

---

문제 - 한 가지로 풀리는 자물쇠

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-one-way-lock/description

한 가지로 열리는 자물쇠 설명 | 코드트리

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long ans = 1;
        for(int i = 0; i<3; i++){
            int cur = Integer.parseInt(st.nextToken());
            int a = (Math.min(N, cur+2) - Math.max(1, cur-2)+1);
            ans *= (N-a);
        }
        System.out.print(N*N*N - ans);
    }
}

사고의 흐름 

쉬운 문제지만 공식 에디토리얼보다 시간 복잡도상 효율적인 풀이가 나와 정리한다. 

문제에서 주어진 건 어느 자리라도 원래 숫자와 차이가 2 이내인 아무 숫자가 들어가면 풀리는 조합이라 정의하고 이러한 조합의 모든 경우의 수를 구하는 것이다. 

러프하게 생각하면 자릿수만큼 for문 돌려서 해결하면 된다. 그런데 자릿수가 100이라면?? 이런건 될리가 없다.

 

풀이 : 여집합 발상

지금 제시된 문제의 조건을 정리하면 되는 경우는 자리마다 or 조건이다.

즉, 한 자리라도 조건을 만족하면 열린다. -> K라고 하자 

이를 뒤집어 생각하면,

모든 자리가 조건을 만족하지 않으면 열리지 않는다. 

전체 조합의 수는 N ^ 자릿수 이다. 이걸 total이라 하자.

그리고 이건 독립 사건이므로 곱셈 원리를 사용해 곱셈의 항등원인 1에 누적 곱을 하고 total에서 이걸 빼 주면 된다.

-> total - (N - K1 * N-K2 * N-K3 * ... * N-Km) (여기서는 자릿수가 3이라 3까지)

간단하게 O(자릿수) 로 풀 수 있다. 

---

문제 - 두 가지로 열리는 자물쇠

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-a-two-way-lock/description

두 가지로 열리는 자물쇠 설명 | 코드트리

public class Main {
    static int N;
    static int M = 3;
    // 자리마다 가능한 숫자 pool list배열
    static Set<Integer>[][] pool = new Set[2][3];
    static Set<String> ss = new HashSet<>();

    // 3자리 set에 넣을때 파싱하는거
    static String parser(int a, int b, int c){
        return a + "," + b + "," + c;
    }
    static int[] A,B;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i =0; i<2; i++){
            for(int j = 0; j<3; j++){
                pool[i][j] = new HashSet<>();
            }
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<3; i++){
            int cur = Integer.parseInt(st.nextToken());
            for(int d=-2; d<=2; d++){
                int nc = cur+d;
                nc = ((nc -1 + N) % N)+1;
                pool[0][i].add(nc);
            }
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<3; i++){
            int cur = Integer.parseInt(st.nextToken());
            for(int d=-2; d<=2; d++){
                int nc = cur+d;
                nc = ((nc -1 + N) % N)+1;
                pool[1][i].add(nc);
            }
        }

        for(int i = 0; i<2; i++){
            for(int a : pool[i][0]){
                for(int b : pool[i][1]){
                    for(int c : pool[i][2]){
                        ss.add(parser(a,b,c));
                    }
                }
            }
        }

        System.out.print(ss.size());
    }
}

사고의 흐름 

이게 왜 대체 easy임????? 

일단 이번에는 두개의 자물쇠가 주어지고 원형 자물쇠라 원형도 처리해야 한다. 

Set은 중복 원소를 허용하지 않으니 String으로 parsing을 해서 거기다가 넣고 크기를 세면 중복 없이 모든 경우의 수가 나올거다.

일단 각 자물쇠에 대해 2 차이가 나는 가능한 조합을 자릿수별로 저장해놓고 실제 조합을 만들어서 set 에 넣는다.

 

풀이 : 빡구현

1) 파싱 함수가 필요

-> 후보 숫자로 구성한 조건을 만족하는 숫자를 표현할 때 자물쇠에 1자리 숫자만 들어오는 것이 아니므로 이에 주의해야 한다.

따라서, 파싱할때 중간에 구분자를 넣어서 String으로 넣는다.

-> 없이 넣으면 11, 2, 3이 1, 12, 3도 되고 1, 1, 23도 되는 문제가 발생한다.

 

2) 후보 저장 배열 관리

이게 N이 5 이상이면 후보 조합에 5개가 들어가는데 그 이하면 나머지연산으로 잡아주더라도 중복해서 들어가기 때문에 

후보 리스트를 관리하는 2차원 배열은 Set 배열로 설정한다.

그리고 현재 자물쇠의 숫자가 중앙값이 되고 절댓값으로 2 차이가 나는 모든 숫자를 후보 Set에 넣어줘야 한다.

따라서, diff를 -2~+2까지 증가시키면서 연산해준다.

 

3) 1-based number의 원형 처리

지금 자물쇠 문제 조건에 보면 1 ~ 100이다. 나머지 연산은 기본적으로 0-based number에서 동작하므로

1.  nc -1 -> 0-based로 전환
2. 1을 뺏으니까 음수가 될 수 있어서 N을 더해주고 나머지 연산을 진행한다.
3.  +1 -> 다시 1-based로 전환

for(int d=-2; d<=2; d++){
    int nc = cur+d;
    nc = ((nc -1 + N) % N)+1;
    pool[1][i].add(nc);
}

코드로 나타내면 이렇게 갱신한다.

 

토론에 보니까 나랑 비슷하게 풀고 질문글을 올리신 분이 계셨다.

공식 답글을 보니 이게 더 좋은 풀이라고 되어있어서 다행이다..

---

문제 - 숫자 카운트 (숫자야구)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-numeric-count/description

숫자 카운트 설명 | 코드트리

public class Main {
    // B의 각 자릿수 0:100, 1:10, 2:1
    static int[] B;
    // 쿼리마다 각 자릿수 여기다가 넣고 ball 비교함
    static Set<Integer> bs;

    static int strikeCount(int a, int b, int c){
        int rst = 0;
        if(B[0] == a)
            rst++;
        if(B[1] == b)
            rst++;
        if(B[2] == c)
            rst++;
        return rst;
    }

    // 후보 숫자 abc의 구성요소가 A에 있지만 다른 자리의 수
    static int ballCount(int a, int b, int c){
        int rst = 0;
        if(bs.contains(a) && B[0] != a)
            rst++;
        if(bs.contains(b) && B[1] != b)
            rst++;
        if(bs.contains(c) && B[2] != c)
            rst++;
        return rst;
    }

    static boolean check(int strike, int ball, int a, int b, int c){
        return (strikeCount(a,b,c) == strike) && (ballCount(a,b,c) == ball);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] queries = new int[N][3];
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int curB = Integer.parseInt(st.nextToken());
            int curStrike = Integer.parseInt(st.nextToken());
            int curBall = Integer.parseInt(st.nextToken());
            queries[i] = new int[]{curB, curStrike, curBall};
        }

        int ans = 0;
        for(int a = 1; a<=9; a++){
            for(int b= 1; b<=9; b++){
                if(a == b)
                    continue;
                for(int c = 1; c<=9; c++){
                    if(b == c || a == c)
                        continue;
                    boolean ok = true;

                    // 지금 뽑은 서로다른숫자로 이루어진 abc가 
                    // 쿼리를 모두 만족해야 후보 조건이 성립함.
                    for(int[] q : queries){
                        int cur = q[0];
                        int cs = q[1];
                        int cb = q[2];

                        B = new int[3];
                        B[0] = (cur/100) %10;
                        B[1] = (cur/10) % 10;
                        B[2] = cur % 10;

                        bs = new HashSet<>();
                        for(int bb : B)
                            bs.add(bb);

                        if(!check(cs,cb,a,b,c)){
                            ok = false;
                            break;
                        }
                    }
                    if(ok)
                        ans++;
                }
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 

숫자 야구 게임류의 문제. 숫자 야구란 정확한 숫자가 정확한 자리에 있는건 strike라 하고 정확한 숫자가 다른 자리에 있는걸 ball이라 한다. 여기서는 N개의 query가 주어지고 가능한 모든 3자리가 서로 다른 숫자 중에서 N개의 query를 모두 만족할때의 경우의 수를 구하는 문제이다.

풀이

일단 필요한 함수 두 개를 골라줬다. ballCount랑 strikeCount인데 일단 구성요소를 나타내는 bs, 정확한 자리의 숫자를 나타내는 B 배열로 입력받은 현재의 B 값을 전처리한다. 그리고 strike는 그냥 B배열이랑 a,b,c 대조해보면 되고 ball은 a,b,c가 현재 A의 구성요소이면서 B배열의 각 자리의 값과는 다를때만 카운팅해줬다. 

---

문제 - 개발팀의 능력 (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/test-the-capabilities-of-the-development-team/description

개발팀의 능력 설명 | 코드트리

public class Main {
    // 2명, 2명 합 
    static int[] rst;
    static int N;
    static int[] skill;
    static boolean[] visited;
    static final int INF = 5*1000+1;
    static int ans = INF;

    static void dfs(int depth, int base){
        if(depth == 2){
            int min = base;
            int max = base;
            
            // 모든팀 능력치 달라야함
            if(base == rst[0]) 
                return;
            if(base == rst[1]) 
                return;
            if(rst[0] == rst[1]) 
                return;
            
            for(int n : rst){
                min = Math.min(min, n);
                max = Math.max(max, n);
            }
            ans = Math.min(ans, max - min);
            return;
        }

        for(int i = 0; i<N; i++){
            if(visited[i])
                continue;

            visited[i] = true;

            for(int j = i+1; j<N; j++){
                if(visited[j])
                    continue;

                visited[j] = true;

                rst[depth] = skill[i] + skill[j];
                dfs(depth+1, base);

                visited[j] = false;
            }
            
            visited[i] = false;

            break;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = 5;
        skill = new int[N];
        visited = new boolean[N];
        rst= new int[(N-1) / 2];
        for(int i = 0 ; i<N; i++){
            skill[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i<N; i++){
            visited[i] = true;
            dfs(0, skill[i]);
            visited[i] = false;
        }

        System.out.print(ans == INF ? -1 : ans);
    }
}

사고의 흐름

개발자의 능력 2랑 비슷한데 추가 조건문이 더 많이 달린 개발자의 능력 만 정리하기로 했다. 

둘다 백트래킹으로 풀이했다. 나와야 할 결과물은 1명/2명/2명으로 이루어진 skill [i] 의 값의 합이다.

 

풀이 : 백트래킹

1명 / 2명 / 2명이 필요하므로 1명을 미리 고정해서 잡고 파라미터로 넘겨서 나머지 두 팀을 완성했을때 max, min 값의 초기값으로 쓴다. 왜냐하면 그 1명의 값은 어차피 비교 대상에 들어가니까 

그리고 중복 방지를 위해서 Visited 배열을 사용하고 dfs 호출 전에 기준이 되는 1명을 미리 visited 처리를 한다. 

-> 이것도 백트래킹 느낌으로 들어가기 전에 체킹하고 끝나면 풀어준다.

-> 그래야 다음 dfs 호출에서 재사용 가능하니까

 

DFS

depth가 2가 될 때, 즉 두개의 나머지 팀이 모두 배정되었을 때 max, min, base 가 서로 distinct 한지에 대해서 체크한다.

여기서는 아이템이 3개 뿐이므로 그냥 if문 3개 썼지만 양이 많아지면 Set을 써서 size를 비교하는 것이 적합해 보였다. 

또한 내부 반복문에서는 첫번째 원소는 [ 0, N-1 ] 이고 두번째 원소는 [ i+1, N-1 ] 로 돌아야 중복을 피할 수 있다. 

똑같이 visited 체킹하고 할거하고 풀어주고 구조를 유지한다. -> 백트래킹

 

최적화

그리고 2중 for문 끝에 break문을 달아서 백트래킹 순회를 최적화했다. 

물론 break문이 없어도 답은 나오는데 break문을 달면 팀의 생성 순서를 고정시키는 역할을 한다.

-> 대표 원소 고정 역할, 왜냐면 팀 구성 요소가 중요하지 그 팀 자체가 분포되어있는 순서는 중요하지 않기 때문이다.

-> 결과적으로 전체 탐색 횟수가 줄어듬 

---

해당 챕터를 마무리하며

추천받은 챕터 중 첫번째 챕터를 완료했다. 총 4일 걸린 것 같다.

확실히 랜덤하게 골~플 백준 문제를 한 두 문제씩 풀고 정리하던 때보다는 피곤하지만 루틴으로 잡게 되면 괜찮아질 것 같다.

 

코드트리의 커리큘럼 구조는 기본 문제 - 설명을 보고 관련된 개념 문제, 확장된 응용 문제, 테스트 (응용 문제에서 약간 꼰 문제)로 이루어져 있어 자신이 학습하고 싶은 게 뭔지 안다면 알아서 스텝을 정리해 두어 여러 사이트를 돌아다니며 문제집 수집을 할 필요가 없다는 점이 장점이다.

 

전체적으로 문제 난이도는 적당한데 내 학습 패턴 상 제한을 더 늘리고 그 제한에서 최적화된 풀이는 무엇인지에 대해서 고찰하는 과정이 포함되어 배운 점이 꽤 있었고 누적합과 활용에 대한 이해, 슬라이딩 윈도와 더 나아가 순열과 조합, 수학적인 점화식 도출, 상태 압축에 대해 개념적으로 다시 훑어보고 적용하는 연습을 할 수 있었다. 

 

공식 에디토리얼(해설)의 경우에는 챕터 기본 내용에 적합한 설명을 담고 있었다. 기본에 충실한 느낌이었다. 

다만 세부 관찰이나 수학적인 특성, 가지치기를 통해 더 나은 시간 복잡도를 달성할 수 있을 것 같은데 아마도 챕터 내용에서 벗어나는 내용이라 담지 않은 것 같았다. 좀 더 난이도가 높은 챕터를 공부하게 되면 내가 고민한 풀이 방향들에 대해서 정리가 될 것 같다.

 

 

#코드트리 #코딩테스트 #코테공부 #알고리즘 기초