[코드트리 후기] 3회차 - 약점 극복 - Backtracking

이번에는 코드트리에서 갭체크를 통해 알게 된 나의 약점을 극복하기 위해 공부를 해 볼 것이다. 

갭체크를 통해 나온 결과 Backtracking 에 대한 지식이 부족하다고 한다. 

 

코드트리에서는 알고리즘 챕터 별로 유형을 나누어 분류를 하고 

 

 

그 유형 안에서도 난이도를 여러가지로 나누어 쉬운 문제부터 어려운 문제까지 점진적으로 난이도를 올려가며 실력 향상을 시켜주고 싶어 하는 것 같다. 

 

처음에는 하나의 레슨을 끝까지 마무리 하고 다음 레슨을 진행하려고 했다. 하지만 곰곰히 생각해보니까 무조건 한 번에 다 끝내는 방식보다 Lesson1 중간 부분까지 한 후 Lesson 2 를 진행하고 같은 방식으로 한 챕터를 진행하고 다시 처음부터 Lesson 1의 중간부터 마무리 까지 하는 것도 나쁘지 않은 방법일 수도 있겠다고 생각이 들었다. 

그 결과...

 

이렇게 생긴 끔찍한 혼종의 학습 진행 상황이 만들어 지게 되었다. 보기만 해서는 마무리가 아쉽다고 생각할 수 도 있겠지만 꾸준히 한다는 관점으로 본다면 한 번 공부했던 부분을 억지로 여러번 공부할 수 있는 방식으로 나름대로 생각하여 공부한 것이다. 

 

위 문제들을 풀면서 코드트리에서 제공해주는 해설이 굉장히 도움 되었던 적이 있었다. 바로 Backtracking 챕터의 'Lesson 3 N개 중에 M개 고르기' 문제를 처음 풀 때였다.

import java.util.*;

public class Main {
    static int k;
    static int n;
    static ArrayList<Integer> answer = new ArrayList<>();

    static void choose(int cur, int cnt){
        if(cur==n){
            for(int i=0; i<answer.size(); i++){
                System.out.print(answer.get(i) + " ");
            }
            System.out.println();
            return;
        }
        for(int i=1; i<=k; i++){
            // answer 의 마지막 원소가 i 가 아니라면
            if((answer.size()==0)||(answer.get(answer.size()-1)!=i)){
                // answer 에 i 를 더하고 cnt 를 1으로 초기화 후 
                answer.add(i);
                choose(cur+1, 1);
            }
            // answer 의 마지막 원소와 i 가 같다면
            else{
                // answer 의 마지막 두 개의 원소가 이미 i 와 같다면
                if(cnt==2){
                    // i 를 다음 수로
                    //System.out.println("cnt : 2");
                    continue;
                }
                // answer 에 i 를 더하고 cnt 를 증가 시킨 후 다음 위치로
                answer.add(i);
                choose(cur+1, cnt+1);
            }
            // 재귀 조건 복구
            answer.remove(answer.size()-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        n = sc.nextInt();
        choose(0, 0);
    }
}

원래 'Lesson 2 의 K 개 중에 하나를 N번 선택하기' 에서는 이런 식으로 choose() 함수에서 for 문을 사용하여 K개를 여러번 뽑도록 코드를 진행했었다. 

 

이 방식을 별 생각 없이  'Lesson 3 N개 중에 M개 고르기' 에서도 사용하게 되면 O(2^k) 의 시간복잡도를 가지게 되어 굉장히 오래걸리게 된다.

 

하지만 여기에서 choose() 함수에서 for 문의 i 값에 cur 를 대입하게 되면 자동으로 가지치기가 되면서 시간복잡도가  O(C(n,m) × m) 로 확연하게 줄어들게 된다. 

 

 

이번 주에는 다음에 오랜만에 JS 를 써야 할 일이 생겨 다시 JS 를 공부하게 되어 많은 진도를 나가지는 못했다.. 물론 다음주에도 JS 를 같이 공부해야 될 것 같아 많은 진도를 나가지는 못 할 것 같지만 최소한 Backtracking 은 다 끝내고 싶긴 하다. 

 

몇 주 뒤가 될 지는 모르겠지만 나중에 같은 문제를 Java 와 JS 두 언어로 모두 풀어보는 시간을 가져봐야겠다.

 

코드트리

Codetree: Master Coding Interviews - Data Structures & Algorithms