완전탐색 - 순열, 조합

수학은 참 낯선 학문입니다. 고등학교 때부터 수학을 잘 하지 못했습니다. 못했다는 말 보다는 안 했다는 말이 더 적절한 것 같습니다.

남들이 수학을 3년 이상 공부할 때 3달을 속성으로 공부하고 수능을 응시하게 됐는데, 아는 문제만 다 풀고 휴식 시간을 가진 덕분에 남들보다 여유롭게 시험을 마무리할 수 있었습니다.

단기적인 공부는 뇌에 깊게 남지 않습니다. 그렇기 때문인지 순열과 조합 또한 배운 적이 있지만 정확한 공식은 기억나지 않습니다.

돌아가는 원리는 알고 있으니 스스로의 힘으로 한번 구현해보겠습니다.

작동

const arr = [1, 2, 3, 4];

위의 배열에서 3가지 원소를 뽑는 순열과 조합을 구현합니다. 조합은 순서를 고려하지 않고 뽑는 경우의 수이고, 순열은 순서까지 고려하여 경우의 수를 추출합니다.

조합에서 [1,2,3]과 [1,3,2]은 같은 경우의 수지만 순열에서는 각각을 독립적인 경우의 수로 판단합니다.

1. 조합

const arr = [1, 2, 3, 4];
const combAnswer = [];

function getCombination(fixed, select, index) {
  if (select === 0) {
    combAnswer.push(fixed);
    return;
  }

  for (let i = index; i < arr.length; i++) {
    if (arr.length - i < select) break; // 남은 원소의 개수가 선택해야할 원소의 개수보다 적을 때
    getCombination([...fixed, arr[i]], select - 1, i + 1);
  }

  return;
}

getCombination([], 3, 0);
console.log(combAnswer);

함수의 매개변수는 fix된 숫자, 더 넣어야 할 수의 개수, 시작 인덱스 총 3가지 입니다.

첫 시작은 fix된 게 없으니 빈 배열, 3가지를 뽑기 때문에 3, 0번 인덱스부터 시작하라는 의미로 0을 넣습니다.

조합을 접근할 때 앞자리부터 채워나간다는 식으로 생각했습니다.

첫 자리에 올 수 있는 경우의 수는 [1,2,3,4] 다 가능하지만 [3,4]는 남은 원소의개수가 부족하기 때문에 제외합니다. 그 조건을 반복분 안에 넣었습니다.

그 조건을 탈출하는 원소들은 재귀적으로 다시 함수를 호출합니다.

getCombination([...fixed, arr[i]], select - 1, i + 1);

이때 fix될 원소를 추가하고, 하나를 추가했으니 넣어야 할 수의 개수 - 1, 현 원소는 제외해야하니 i + 1로 설정합니다.

fixed.concat(arr[i])도 새로운 배열을 반환하기 때문에 무방합니다.

  if (select === 0) {
    combAnswer.push(fixed);
    return;
  }

재귀 함수의 탈출 조건입니다. 결과를 저장하는 상위 스코프 변수에 현재까지 fix된 값들을 넣고 함수를 종료합니다.

상위 스코프가 아닌 재귀함수 내부에서 결과를 return하고 싶었지만, 너무 복잡해져서 방식을 이렇게 바꿨습니다. 아직 역량이 많이 부족합니다... 😥

[ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

다음과 같이 결과들이 출력됩니다.

2. 순열

const arr = [1, 2, 3, 4];
const permAnswer = [];

function getPermutation(fixed, select, visited) {
  if (select === 0) {
    permAnswer.push(fixed);
    return;
  }

  for (let i = 0; i < arr.length; i++) {
    if (visited.includes(i)) continue;
    getPermutation([...fixed, arr[i]], select - 1, [...visited, i]);
  }

  return;
}

getPermutation([], 3, []);
console.log(permAnswer);

순열도 조합과 방식은 비슷합니다. 다만 들어가야 할 원소의 유효성을 판단하는 방식이 조금 다릅니다.

조합은 시작 인덱스를 바꿔 간편하게 처리했지만, 순열은 이미 방문한 원소라는 걸 판단해야 했습니다.

내부에 visited라는 배열 변수를 선언해 방문했던 index들을 포함하도록 만들었습니다.

그 외에는 조합과 똑같습니다. 더 선택할 수가 없다면 상위 스코프 변수에 push하고 그렇지 않다면 재귀호출을 합니다.

[
  [ 1, 2, 3 ], [ 1, 2, 4 ],
  [ 1, 3, 2 ], [ 1, 3, 4 ],
  [ 1, 4, 2 ], [ 1, 4, 3 ],
  [ 2, 1, 3 ], [ 2, 1, 4 ],
  [ 2, 3, 1 ], [ 2, 3, 4 ],
  [ 2, 4, 1 ], [ 2, 4, 3 ],
  [ 3, 1, 2 ], [ 3, 1, 4 ],
  [ 3, 2, 1 ], [ 3, 2, 4 ],
  [ 3, 4, 1 ], [ 3, 4, 2 ],
  [ 4, 1, 2 ], [ 4, 1, 3 ],
  [ 4, 2, 1 ], [ 4, 2, 3 ],
  [ 4, 3, 1 ], [ 4, 3, 2 ]
]

다음과 같은 결과가 출력됩니다.

후기

다른 사람의 코드를 참고하며 만들까 고민하다 혼자서 구현해보겠다는 도전의식을 갖고 부딪쳤습니다.

참 간단한 알고리즘 같은데 직접 구현하려니 까다로운 점들이 많았습니다. 아직 재귀에 대해 완벽하게 이해하지 않아서 그런 것 같습니다.

다양한 문제들을 접해보며 숙련도를 쌓아야겠습니다.