2. 재귀

권오흠 교수님 유튜브 강의

4. 멱집합

• {1,2,3,4} 모든 부분집합

  • 1을 포함하지 않는 모든 부분집합

  • 1을 포함하는 모든 부분집합

  • 위 2개 재귀

  public void powerSet(int[] P, int[] S) {
    if (S.length == 0) {
      System.out.println(Arrays.toString(P));
    } else {
      int t = S[0];
      int[] ints = Arrays.copyOf(P, P.length + 1);
      ints[ints.length - 1] = t;

      powerSet(P, Arrays.copyOfRange(S,1, S.length));             // t를 포함하지 않은 집합 모두 출력
      powerSet(ints, Arrays.copyOfRange(S,1, S.length));     // t를 반드시 포함하는 부분 집합들
    }
  }

• 상태공간트리 활용

  • k = 트리 레벨 (위치, 노드 깊이)

    • ex) k=2 -> 2번째 위치 값까지 포함 여부에 대한 집합

  • k == 집합 길이 -> 모든 집합 (마지막 리프노드)

  private char data[] = {'a', 'b', 'c', 'd'};
  private int n = data.length;
  private boolean[] include = new boolean[n];
  
  // k-> 트리상 현재 나의 위치 표현
  public void powerSet2(int k) {
    if (k == n) { // 내 위치가 리프노드 라면
      for (int i = 0; i < n; i++) {
        if (include[i]) {
          System.out.print(data[i] + " ");
        }
      }
      System.out.println();
      return;
    }

    // 왼쪽 (포함하지 않는)
    include[k] = false;
    powerSet2(k + 1);
     
    // 오른쪽 (포함하는)
    include[k] = true;
    powerSet2(k + 1);
  }

5. 순열

• data = {1,2,3,4} -> 4! = 24 (1234의 모든순열 가지수)

  • 1234, 1243 ... 4321

  • 1 -> 234 의 모든 순열

    • 12 -> 34 의 모든 순열

    • 13 -> 24 의 모든 순열

    • 14 -> 23 의 모든 순열

      • 하위 반

  • 2 -> 134 의 모든 순열

  • 3 -> 124 의 모든 순열

  • 4 -> 123 의 모든 순열

• 상태공간트리

• 멱집합(조합, 순서 상관x) 과 순열(순서상관) 나열의 응용

  • 배낭문제(Knapsack)

    • 무게와 가격이 정해진 N개의 아이템과 용량이 W인 배낭이 있다. 배낭의 용량을 초과하지 않으면서 가격의 합이 최대가 되도록 아이템을 배낭에 넣으려면??

    • 시간복잡도 : O(2^n)..... 최적화 필요

    • 멱집합 -> 무게 > W 무시하고, W<= 무게 필터링 -> 최대인거 구하기

  • TSP

    • 모든 도시 출장 -> 원점 복귀 -> 가장 짧은 투어 경로 구하기