[자료구조] JS로 구현하는 순열과 조합

KG·2021년 4월 30일

자료구조 with JS

목록 보기

3/4

Intro

알고리즘 문제를 풀다보면 종종 순열이나 조합을 이용해 문제를 풀어야 할 때가 있다. 다른 언어의 경우엔 기본 라이브러리에 관련 함수가 이미 내장되어 있어 대부분의 코딩테스트에서 이를 사용할 수가 있지만 JS 에서는 아니나 다를까 이와 관련된 기본으로 내장된 라이브러리가 존재하지 않는다. 따라서 JS로 순열(Permutation)과 조합(Combination)을 구하는 함수를 직접 구현해보고 익힌다면 문제 풀이에 많은 도움이 될 것 이다.

조합 (Combination)

조합은 순서에 구애받지 않는다. 따라서 동일한 데이터가 주어졌을 때 순열 보다 시간복잡도가 더 낮다. 때문에 조합을 구현하는 코드를 먼저 살펴보자.

만약 [1, 2, 3, 4]이 데이터로 주어졌을 때 이 중에 3개를 뽑아 만들 수 있는 조합(= 4C3)은 다음과 같다.

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

이때 위에서 이야기 했듯이 순서는 상관없다. 즉 [1, 2, 3]과 [3, 2, 1]은 조합에서 동일한 값으로 인식한다.

위에서 4C3을 구하는 과정을 하나씩 살펴보면 다음과 같이 구분할 수 있다.

1을 고정하고 나머지 [2, 3, 4] 중에 2개 선택
2를 고정하고 나머지 [3, 4] 중에 2개 선택
3를 고정하고 나머지 [4] 중에 2개 선택
4를 고정하고 나머지 [] 중에 2개 선택

여기서 다음 과정으로 넘어갈 때 기존에 고정한 값은 나머지에 포함되지 않는 것이 조합에서 가장 중요한 점이다. 기존값을 나머지에 포함시키는 것은 이미 사용한 값을 다시 고려하여 순서를 결정하는 것이기 때문에 조합에서 순서를 고려하지 않는다는 점과 상반되는 부분이기 때문이다.

위의 구조를 살펴보면 재귀적으로 이를 구현할 수 있음을 떠올릴 수 있다. 만약 위의 예시처럼 4C3을 구해야 하는 경우엔 4에 해당하는 값을 가지고 있는 배열 arr과 그 중에서 몇 개를 선택해야 하는지에 대한 정보 n을 인자로 전달 받도록 하자. 전달받은 배열 arr에서 원소를 하나씩 선택(고정)하고 해당 원소의 인덱스 이후에 있는 나머지 배열과 n-1 을 인자로 하여 다시 자기 자신을 (재귀)호출하는 로직이 될 것 이다.

const getCombination = (arr, n) => {
  // n이 1이 되는 경우는 현재값을 선택하는 것과 동일
  // 따라서 각각의 원소를 바로 배열 형태로 리턴
  // 재귀호출에서 n이 1이 되는 순간부터 배열 데이터 생성
  // 즉 1부터 역으로 다시 거슬러 올라가 n이 될때까지
  // 선택된 원소들로 배열(조합)을 구성
  if(n === 1) return arr.map(el => [el]);
  // 최종 결과를 담을 배열
  const result = [];
  
  // fixed : 고정할 원소, origin : 원본 배열
  arr.forEach((fixed, idx, origin) => {
    // 현재 고정한 원소 이후의 배열을 나머지로 선언
    const rest = origin.slice(idx+1);
    // 나머지와 n-1을 다시 전달하여 재귀호출
    const combis = getCombination(rest, n-1);
    // 재귀호출이 끝나고 돌아오는 시점은
    // 처음 고정한 fixed로 구성 가능한 모든 조합을 리턴받은 이후
    // 따라서 리턴받은 값과 fixed를 다시 합쳐주어 조합 구성
    const attached = combis.map(combi => [fixed, ...combi]);
    // 구성된 조합 배열을 결과에 푸시
    result.push(...attached);
  });
  
  // 위에서 모든 재귀호출이 종료되면 저장된 조합 경우의 수 리턴
  return result;
}

순열 (Permutation)

순열은 조합과 달리 순서의 영향을 받는다. 따라서 기존에 구현한 조합에서 순서를 고려해주는 설계만 추가해주면 될 것 이다. 위의 [1, 2, 3, 4] 에서 똑같이 4P3을 구하는 경우의 수는 4 X 3 X 2로 총 24가지의 경우의 수가 있다. 순열을 구하는 공식은 조합을 구하는 공식을 이용할 수도 있는데 그 공식은 다음과 같다.

nPr = nCr * r!

따라서 이를 위에서 구한 조합에 그대로 대입하면 다음과 같다.

[1, 2, 3] 에서 순서 고려 => 3!
[1, 2, 4] 에서 순서 고려 => 3!
[1, 3, 4] 에서 순서 고려 => 3!
[2, 3, 4] 에서 순서 고려 => 3!

따라서 3! * 4 는 총 24의 경우의 수임을 알 수 있다. 때문에 우리는 순서를 고려해 3! 의 경우의 수를 도출하는 부분만 추가로 구현해준다면 기존에 이미 구현한 조합 함수를 활용할 수 있을 것 이다.

조합에서는 순서를 고려하지 않기 때문에 기존에 선택된 원소는 제외하고 나머지 rest를 구해주었다. 그렇다면 순서를 고려해 주기 위해서는 기존에 선택이 되었더라도 해당 원소를 다시 나머지 rest에 포함시켜주면 될 것이다. 즉 결과적으로 위에서 구현한 조합을 구하는 함수에서 rest를 구하는 부분만 차이가 있을 뿐 나머지는 모두 동일하다.

const getPermutaion = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    // 고정한 원소 fixed를 제외한 나머지 모든 배열이 나머지가 되어야 한다
    // 따라서 기존에 선택이 되었다고 할 지라도
    // 해당 원소를 다시 포함시켜 줌으로써 순서가 달라지는 경우까지
    // 모두 고려하여 경우의 수를 구성할 수 있다.
    const rest = [ ...origin.slice(0, idx), ...origin.slice(idx+1) ];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

심화

순열의 경우 시간복잡도는 nPr 일때 아무리 작게 잡아도 주어진 r 값의 팩토리얼 값과 같다. 따라서 r이 10만 되어도 이는 300만이 넘어가는 경우의 수가 된다. 더구나 n의 값이 커지면 커질 수록 그 값은 더욱 기하급수적으로 상승한다. 조합 역시 순열 보다야 상황이 나은 편이지만 큰 규모의 데이터에 대한 모든 순열을 구하는 것은 역시 막대한 시간복잡도가 소요될 수 있다.

또한 자바스크립트의 재귀호출과 콜스택에 관련된 이슈 역시 주의깊게 생각해야 할 필요가 있다. 관련된 이야기는 해당 포스트에 자세히 소개했으니 궁금하면 참고하도록 하자. 결론은 10만이 넘어가는 재귀호출은 자바스크립트 런타임 환경에서 스택 오버플로우로 인한 런타임 에러가 발생할 확률이 굉장히 높다는 것이다.

하지만 보통 엄청난 크기의 데이터를 주고, 이에 대한 모든 순열 또는 조합의 경우의 수를 구하여라라는 식의 문제는 출제되지 않는다. 카카오에서 출제된 문제를 보면 최대 n의 값을 8로 주었기 때문에 제한시간 내에 해당 순열 알고리즘을 이용하여 문제를 통과할 수 있음을 확인할 수 있다.

또는 데이터의 크기가 매우 큰 경우에는 모든 경우의 수를 구하는 것이 아닌 특정 위치에 있는 값을 리턴하라고 하는 경우가 있을 수 있다. 이 경우에는 위의 함수를 사용해서 위치값을 찾는 것이 아니라 다른 방식으로 접근을 할 필요가 있다. 관련해서는 실제 문제는 다음 포스트를 참고하자.

재귀호출 하면 떠오르는 알고리즘 중에 대표적인 것중에 하나는 DFS 알고리즘이 있다. 따라서 순열 또는 조합을 DFS 알고리즘을 이용해 적절한 가지치기로 위에서 구현한 함수 보다 더 빠른 시간 내에 구할 수도 있다. 또는 스택 등을 활용한 단순 반복문으로 바꾸어 구하는 방법 역시 생각해볼 수 있다.

따라서 위에서 언급한 경우에는 순열이나 조합을 구하기 위해 다른 방법으로 접근 할 필요가 있다. 만약 전체 순열 또는 조합에 대한 경우의 수를 구해서 문제에 활용해야 하는 경우라면 위에서 구현한 함수를 사용하여 풀어보자!

전체코드

주석을 제외한 전체코드는 다음과 같다.

const getCombination = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    const rest = origin.slice(idx+1);
    const combis = getCombination(rest, n-1);
    const attached = combis.map(combi => [fixed, ...combi]);
    result.push(...attached);
  });

  return result;
}

const getPermutaion = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    const rest = [ ...origin.slice(0, idx), ...origin.slice(idx+1) ];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

참고

개발잘하고싶다

이전 포스트

[자료구조] Stack을 이용한 Iterative DFS 구현

다음 포스트