📌 javascript 개념 #10 순열 / 수학기본이론 (2)

수학기본이론 / 경우의 수 / 순열

경우의 수

: 어떤 사건 또는 일어날 수 있는 경우의 가짓수를 숫자로 표현하는 것이며
주사위, 윷, 가위바위보, 동전 등에서 쓰인다.
--> 이러한 경우의 수에는 순열, 조합, 중복순열 등이 있으며, 완전 탐색을 이용한다.

완전 탐색이란 ?

컴퓨터의 빠른 계산 속도를 잘 이용하는 방법으로 가능한 모든 방법을 나열하며 답을 찾는 방법이다.

---

순열 (permutation) : nPr

: 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수
= for문과 재귀함수로 표현가능하다.
--> 그러나 for문은 뽑는 개수 만큼 늘어나기 때문에 보통은 재귀함수를 쓴다.

예시사진

3개의 알파벳으로 단어를 만드는 경우의 수

---

순열 예제 코드 (1) for loop

// >> for문으로 구성
let input = ["a","b","c"];
let count = 0;

function permutation(arr) {
  // i : 첫번째 위치 시킬 요소 {i, o, o}
  // j : 두번째 위치 시킬 요소 {i, j, o}
  // -> 혹시나 i랑 j가 같을 경우를 continue 이용하여 스킵 처리 해준다.
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i == j) continue;
      // k : 세번째 위치 시킬 요소 {i, j, k}
      for (let k = 0; k < arr.length; k++) {
        // i랑 k가 같을 경우 스킵 
        if (i == k) continue;
        // j랑 k가 같을 경우 스킵
        if (j == k) continue;

        console.log(arr[i], arr[j], arr[k]);
        count++;
      }
    }
  }
}

permutation(input);
console.log(count); // 6개의 경우의 수가 나온다.

/*
a b c
a c b
b a c
b c a
c a b
c b a
*/

for문으로 구현한 코드이며, input에 담긴 a, b, c 3개의 알파벳을 이용하여 만들 수 있는 단어의 경우의 수를 나타내 주어야 한다.

우선 i를 첫번째 위치 시킬 요소로 정해두고, j는 두번째 위치 시킬 요소, k는 세번째 위치 시킬 요소로 정해둔다.
여기서 3가지 경우가 발생하는데,

1. i = j
   : i와 j가 같다면 3개의 알파벳을 모두 사용한 결과가 나오지 않으므로 이 경우를 넘겨줘야 한다. 따라서, continue를 이용해서 이 부분만 무시하고 돌려준다.
2. k = i
   : k와 i가 같은 경우 역시 continue 이용
3. k = j
   : k와 j가 같은 경우 역시 continue 이용

위의 세가지를 고려하여 if문을 이용하여 코드를 짜준뒤, count++를 이용해 순서를 하나씩 늘려준다. 여기서 count는 index값을 의미

예) a 루프가 다 돌면 -> b 루프가 다 돌면 -> c 루프

for문을 쓰지 않는다는 이유

= if문이 value 개수만큼 생성
그렇기 때문에 값이 많을 수록 복잡해짐

---

순열 예제 코드 (2) 재귀함수

// >> 재귀 함수로 구성 
let Input = ["a", "b", "c"];
let Count = 0;

// 주의사항
// 1. 재귀함수를 멈춰야 할 조건
// 2. 재귀를 돌면서 변경되어야 할 부분 / 메인로직
function permutation(arr, s, r) {
  // = r은 도착해야할 인덱스
  // s가 r에 도달하면 Count 값을 증가 - 콘솔로 배열 상태 확인
    
    if (s == r) {
    Count++;
    console.log(arr.join(" ")); // join 메서드 -> 문자열로 변환
    return;
  } 
  // 1. -> 재귀에 대한 break 역할을 하는 부분
  
  
  // 선택된것을 뽑지 않으려고 0 대신 s부터로 지정
  for (let i = s; i < arr.length; i++) {
    [arr[s], arr[i]] = [arr[i], arr[s]]; // swap
    // 첫번째 요소는 선택 했으니 두번째 요소를 선택 -> s + 1
    permutation(arr, s + 1, r);
    [arr[s], arr[i]] = [arr[i], arr[s]]; // swap 원상복귀

    /*
    s = 0, r = 2  ["a", ]
    s = 1, r = 2  ["a", "b", ]
    s = 2, r = 2  ["a", "b", "c"]
    --> 위 for문과 출력되는 값은 동일함
    */

  } 
}

permutation(Input, 0, 2); // 0번부터 2번까지(3개) 뽑는다.
console.log(Count);