완전탐색-순열과 조합

이 글은 완전 탐색의 개념과 완전 탐색 기법을 활용한 알고리즘의 종류들을 간략하게 정리하고, 순열과 조합을 메인으로 설명한다.

01 경우의 수 Number of Cases

경우의 수(境遇─數, number of cases)란, 어떤 사건(일)이 일어날 수 있는 경우의 가짓수(outcomes)를 수로 표현한 것이다.

1회의 시행에서 일어날 수 있는 사건의 가짓수를 n이라고 할 때 이 때의 경우의 수를 n이라고 한다. 각 사건이 일어날 확률들의 관계를 알 수 있다면 경우의 수를 통해 각 확률을 구할 수 있기 때문에 완전탐색 알고리즘에서 사용된다.

 

02 완전 탐색 Exhaustive search

완전 탐색이란 모든 경우의 수를 나열하는 방식으로 답을 구하는 방법이다. '무식하게 푼다'라는 의미인 Brute-Force 라고도 한다.

모든 경우의 수를 다 찾아보는 만큼 답은 확실히 찾을 수 있으나, 경우의 수가 많을 시 활용하기 어렵다.

 

03 완전 탐색 기법

완전 탐색을 활용한 알고리즘의 종류들이다.

간단하게 전반적인 종류와 정의만 살펴보고 이후에는 순열과 조합에 대해 설명한다.

 

단순 Brute-force

단순히 for문과 if문 등으로 모든 경우를 만들어 답을 구하는 방법으로, 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용된다. (=이 방법만을 사용하는 문제는 거의 없음)

 

비트마스크 Bitmask

2진수를 이용하는 컴퓨터의 연산을 활용하는 방식으로, 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용 가능하다.

ex) '원소가 n개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있음

재귀함수 Recursive

함수 스스로 자신을 참조(=재참조)해 호출하면서 동일한 코드가 계속적으로 수행되는 함수 호출 방법이다.

특정 조건이 됐을 때 호출을 멈추도록 제한하는 exit code가 반드시 필요하다(없을 시 프로그램이 영원히 돌면서 stack overflow 발생).

각 원소가 두 가지 선택지를 가질 때 유용하게 사용된다. 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식으로 활용된다. 시간복잡도는 O(N)이다.

대표적인 재귀함수 예시로는 피보나치 수열이 있다.

 

조합 Combination

서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수(nCr)로, 순서를 고려하지 않는 점이 순열과 차이가 있다.

 

순열 Permutation

완전 탐색의 대표적인 유형으로, 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수(nPr)이다. 조합에서 순서라는 요소를 넣어 변형한 형태이다. 순서를 고려해 나열하는 부분이 중요하다.

시간복잡도는 O(N!)이다.

 

너비 우선 탐색(BFS)/깊이 우선 탐색(DFS)

너비 우선 탐색(BFS, Bread-First Search)

: 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식으로, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다. 재귀 방식이 아닌 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐를 사용(FIFO)를 활용한다.

 

깊이 우선 탐색(DFS, Depth-First Search)

: 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식으로, 모든 노드를 방문하고자 할 때 사용된다. 재귀와 스택을 활용한다.

 

주로 길 찾기 등에 주로 사용되는 알고리즘이다. 추가적인 연산이 필요할 때는 완전탐색과 병행한다.

 

 

04  조합

조합의 원리 설명 이미지

서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수(nCr)이다.

순열과의 제일 중요한 차이점인 순서를 고려하지 않기 때문에 순열보다 상대적으로 간단하다.

 

*조합을 구하는 방식*

Input: [1, 2, 3, 4] 시작
> 1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
[1, 2, 3] [1, 2, 4] [1, 3, 4]
2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
[2, 3, 4]
3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[]
4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
[]
> 종료 Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]

/*forEach*/
function combination(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((item) => [item]);

  arr.forEach((item, index, array) => {
    const fixed = item; // 1개씩 요소를 고정
    const restArr = array.slice(index + 1); 
// 고정시킨 요소를 제외하고 다 새로운 배열
    const restCombination = combination(restArr, selectNum - 1); 
// 새로운 배열로 다시 조합 제작
    const fixedCombination = restCombination.map((item) => [fixed, ...item]); 
// 새로운 조합 요소들을 고정된 요소와 결합 
    result.push(...fixedCombination);
  });

  return result;
}
//코드 출처 https://intrepidgeeks.com/tutorial/javascript-sequence-to-realize-combination

 

05 순열

순열의 원리 설명 이미지

서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수(nPr)이다.

조합은 순서에 상관없이 선택한 것이라면, 순열은 순서가 중요하다. 실질적으로는 조합에서 확장된 개념이 순열이라 할 수 있다.

 

nPr = nCr × r!
조합을 구한 후, 선택하려는 수의 factorial 을 곱하면 순열 구하는 식이 됨
[1, 2, 3] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[1, 2, 4] => 이 안에서 순서를 바꾸는 경우의 수=> 3!
[1, 3. 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!
[2, 3, 4] => 이 안에서 순서를 바꾸는 경우의 수 => 3!

/*forEach*/
function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((item) => [item]);

  arr.forEach((item, index, array) => {
    const fixed = item;
    const restArr = array.filter((item, arrIndex) => arrIndex !== index); 
    // 달라지는 부분(중복방지)
    const restCombination = combination(restArr, selectNum - 1);
    const fixedCombination = restCombination.map((item) => [fixed, ...item]);
    result.push(...fixedCombination);
  });

  return result;
}
//코드 출처 https://intrepidgeeks.com/tutorial/javascript-sequence-to-realize-combination

---

참고자료

https://velog.io/@hyehyes/알고리즘-완전탐색

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations

https://jun-choi-4928.medium.com/javascript로-순열과-조합-알고리즘-구현하기-21df4b536349

제로베이스 <이론부터 실전까지 모든 것을 담은 자료구조 알고리즘> 강의 내용