[알고리즘] 멱집합에 대해서 (DFS)

설명

앞선 게시물에서는 순열, 중복순열에서 다루었는데 멱집합과 유사하지만 멱집합은 다른 조건이 붙습니다.

순열, 중복순열의 출력값의 길이가 전부 동일하지만 멱집합은 그렇지 않다는 점이며, 선택의 유무가 자유롭습니다.

 

멱집합

S={a, b}라 하면, P(S)={ ∅, {a}, {b}, S } 이다.
원소의 개수가 n개인 집합의 부분집합의 개수는 2^n(2의 n승)개이므로, 멱집합의 원소의 개수 또한 2^n(2의 n승)개가 된다. 멱집합은 위상 공간 등의 개념에 사용된다.

(n승 맥북으로 어떻게 쓰나요..ㅠ 알려주실분..)

 

어찌되었든 순열, 중복순열은 n의 r 승의 경우의 수가 나오는 반면에, 멱집합은 2의 n승의 경우의 수가 나온다.

여기서만 보아도 멱집합의 특징을 볼 수있다. 좀 더 작은 경우의 수가 나올 수 밖에 없는 이유는, 내가 이 값을 넣을지 넣지 않을지 요소 선택의 자유로움이 포함 되었기 때문이다. 4개를 꼭 넣어야 하는게 아니기 때문에 그만큼 경우의 수가 줄어 들 수 밖에없다.

 

그렇기 때문에 재귀함수를 사용할 때에 값을 선택해주지 않게 만드는 방법이다.

여기서 나오는 코드는 재귀함수를 두번 사용하여 요소를 선택을 할지 안할지에 대한 부분을 만들어 준다.

 

문제

김코딩은 몇 년의 해외 출장 끝에 본가에 내려왔습니다. 오랜만에 보는 김코딩의 얼굴에 반가웠던 부모님은 상다리가 부러질 정도로 음식을 만들었습니다. 감동의 재회도 잠시, 의자에 앉아 식사를 하려던 김코딩은 무엇부터 먹어야 될지 깊은 생각에 빠졌습니다. 정성스럽게 차려 주신 만큼, 최대한 많은 방법으로 다양하게 먹고 싶었기 때문입니다.

밥은 한 가지이며 반찬은 다수일 때, 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수를 배열에 담아 리턴하세요.

입력

인자 1: sideDishes

• String 타입의 영문으로 된 반찬이 나열되어 있는 배열

출력

• Array 타입을 리턴해야 합니다.
• 밥과 함께 먹을 수 있는 반찬의 모든 경우의 수가 담긴 배열

주의사항

• 반찬은 영문으로 작성이 되어 있습니다.
• 반찬은 중복되지 않습니다.
• 반찬을 먹지 않는 것도 포함됩니다. (출력되는 2차원 배열은 빈 배열을 포함합니다.)
• 반찬은 3개 이상 99개 이하입니다.
• 출력되는 배열은 전부 사전식 순서(lexical order)로 정렬되어야 합니다. ex)

 

코드

 

function missHouseMeal(sideDishes) {

  // 결과를 담을 배열을 선언합니다.
  let result = [];
  // sideDishes를 사전식 순서로 정렬합니다.
  sideDishes.sort();

  // 모든 조합을 검사하는 재귀 함수를 작성합니다.
  const sidePowerSet = (idx, sideDish) => {

    // 재귀 함수이기 때문에 탈출 조건을 만듭니다.
    if (idx === sideDishes.length) {
      // 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push합니다.
      result.push(sideDish);
      return;
    }

    // idx번째 요소가 포함되지 않는 경우
    sidePowerSet(idx + 1, sideDish);

    // idx번째 요소가 포함되는 경우
    sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
  };

  // 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행합니다.
  sidePowerSet(0, []);

  // 결과를 사전식 순서로 정렬합니다.
  return result.sort();
}

 

sidePowerSet(idx + 1, sideDish);

sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);

 

첫 번째 코드는 요소를 선택을 하지 않고 넘어가는 부분

두 번째 코드는 요소를 선택을 하고 넘어가는 부분 입니다.

코드의 순서는 상관 없습니다. 

 

이것만 보고 재귀가 2번이나 붙었는데 순열보다 경우의 수가 왜 작지 라고 생각 할 수 있는데

반복문을 통한 재귀를 사용하지 않고 오직 재귀만 사용하여서 경우의 수가 작습니다.

 

멱집합이 2의 n승의 경우의 수를 나타내는데

재귀가 2개의 코드가 2를 담당하고, n이 요소(sideDishes 갯수)를 담당한다고 생각하면 쉽습니다.

 

수학적인 개념도 분명 필요하지만 굳이 몰라도 된다는 느낌을 받았습니다. 코드를 짜는 스킬은 또 다른 세계..?