중복 순열 알고리즘

주어진 아이템을들 사용해 n번의 선택으로 가능한 모든 경우의 수를 구해야 한다.

보통 주어진 아이템은 입력값에 나와 있다. 예를 들어, [1, 2, 3] 이 세 개가 주어진 아이템이 되겠다.

n번의 선택이라는 것은, 만약에 n이 3일 땐 [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 1] ... 처럼 1부터 3까지 1이 다 들어가는 것부터 3이 다 들어가는 것까지의 조합이다.

n이 3일 때 이런 식으로 가능하다.

지금 푸는 가위바위보 알고리즘(원래는 록, 시저, 페이퍼인데 헷갈리니까 1, 2, 3으로 대체합니다.) 3개의 요소 중 3개를 사용해 조합한다. 이것은 반복문으로도 가능하지만, n이 고정되어야 가능할 뿐더러 n이 3 이상일 경우엔 반복문이 4중, 5중... n중으로 늘어나기 때문에 굉장히 비효율적이다.

function forloop() {
  let result = [];
  let lookup = [1, 2, 3];

  for(let i = 0; i < 3; i++) {
    for(let j = 1; j < 3; j++) {
      result.push([lookup[i], lookup[j]]);
    }
  }
  return result;
}

그렇다면 N이 유동적으로 변한다고 가정했을 때, 반복문을 사용하지 않고 어떻게 풀 수 있을까?

3 다음인 4일 경우에는?

아래부터는 코드가 나온다. 그러나 코드만 줄줄 외우는 건 도움이 되지 않는다. 어떠한 작동 원리인지 알아야 한다. (그렇기 때문에, 다른 방법으로 풀 수 있다면, 순열을 이해한 것이고, 본인만의 방법으로 푸는 것을 추천합니다.)

이 알고리즘은 일회용 bucket을 사용하여 n의 길이에 맞게 순차적으로 수집한 다음, n에 도달하게 되면 result 배열에 넣는다.

일회용 bucket은 for문과 같은 방식으로 동작하지만 재귀를 사용한다. 반복문은 한 번만 사용하지만, 재귀함수를 사용하여 반복문 안의 반복문을 여러 겹으로 만드는 것이다. 여러 겹의 횟수는 n번이기 때문에 한 번 반복문을 사용할 때마다 1씩 차감한다.

// 재귀함수만 따로 놓고 보자면

let itemArr = [1, 2, 3];

const recursion = (count = n, bucket = []) => {
  // 탈출 조건: count가 0이 되면 n중 반복문을 만든 것이기 때문에 멈춘다
  // 3P2나 4P3이 될 수 있다. 그건 이 알고리즘을 변형(응용)시키면 되지 않을까.
  // count를 조절하는 방법으로 개수 조절이 가능하다.
  if(count === 0) {
    // 완성된 조합 1개
    // console.log에 비단 찍는 게 아니라, 출력값이 될 배열에 담을 수도 있다.
    console.log(bucket);
    return;
  };
  
  // (n중) 반복문 생성
  for(let i = 0; i < itemArr.length; i++) {
    // itemArr에서 i번째 item을 픽함 (순차적으로 넣기 위함)
    // for문의 result.push([lookup[i], lookup[j], lookup[k]]); 중 lookup[i]에 해당
    const pick = itemArr[i];
    // n중 반복문 생성 / lookup[i]번째를 담은 채로 재귀
    // n이 3이라고 가정했을 때
    // 두 번째 반복문을 생성했을 때 [1]이 들어간 상태, count는 2
    // 세 번째 반복문을 생성했을 때 [1, 1]이 들어간 상태, count는 1
    // 네 번째로 진입했을 땐 [1, 1, 1]이지만 count가 0이기 때문에 반복문에 진입하지 못하고 반환함
    // 세 번째 반복문에서 1은 종료했으니 2로 진입 => [1, 1, 2]
    // ... 반복
    
    // 반복문의 갯수는 총 3개
    // concat을 사용하는 이유는 push 같은 경우엔 반환값이 length이고, concat은 반환값이 배열이다.
    recursion(count - 1, bucket.concat(pick));
  }
};

recursion();

모든 조합을 만든 재귀함수를 활용하여 중복 순열을 구해 보자.

function rps(n) {
  let lookup = [1, 2, 3];
  let result = [];
  
  let recursion = (count = n, bucket = []) => {
    if(count === 0) {
      // result에 만든 bucket을 집어넣는다
      result.push(bucket);
      return;
    };
    
    for(let i = 0; i < lookup.length; i++) {
      let choice = lookup[i];
      recursion(count - 1, bucket.concat(choice));
    }
  }
  
  return result;
};

// pick or not 방법으로도 풀 수 있다. 한번 도전해 보는 것을 추천한다.

순열 알고리즘

중복 순열이 아닌, 중복이 허용되지 않는 순열은 어떻게 할까.

중복 순열 같은 경우엔 모든 걸 다 때려 박으면 되는데 순열은 각 하나씩밖에 들어갈 수 없다.

item이 [1, 2, 3]일 경우, 1이 들어가게 되면, 1은 들어갈 수 없다. 2나 3이 들어가야 한다. 마찬가지로, 2가 들어가게 되면 2는 들어갈 수 없다. 1이나 3이 들어가야 한다.

그렇다면, 해당 숫자가 들어갈 수 없게 아예 지워 버리는 건 어떨까? 중복 순열에서 조금만 바꾼다면 순열 알고리즘을 만들 수 있다.

기존의 중복 순열 알고리즘에서 조금만 바꿔 보기로 한다.

function rps(n) {
  let lookup = [1, 2, 3];
  let result = [];
  
  // 원소가 하나씩 들어갈 때마다 사용한 원소를 하나씩 지워야 한다. 그렇다면 count를 셀 필요는 없다.
  // arr의 length가 0이 되면 마지막까지 도달한 것이 되기 때문이다.
  // 기존의 count를 arr로 바꾸고, lookup을 넣어 준다.
  let recursion = (arr = lookup, bucket = []) => {
    // count 대신 쓸 arr의 길이가 0이 되어야 탈출 조건으로 성립한다.
    if(arr.length === 0) {
      // result에 만든 bucket을 집어넣는다
      result.push(bucket);
      return;
    };
    
    // arr의 length만큼 순환한다.
    // lookup의 길이만큼 순회하지 않는 이유는 bucket에 원소가 들어갈 때마다 배열의 원소가 하나씩 사라져야 하기 때문이다.
    for(let i = 0; i < arr.length; i++) {
      //이 부분만 수정하면 된다.
      // lookup을 사용하지 않고 arr을 사용하는 이유는, 배열의 원소를 넣고 빼기 위함이다.
      // 기존 배열은 lookup, 참고용이다. 참고용의 원소를 빼서는 안 된다.
      let clone = arr.slice();
      
      // 기존은 lookup의 i번째를 가지고 왔지만, 중복 없는 순열은 clone 배열의 원소를 splice로 뽑는다.
      // [1, 2, 3]에서 0번을 뽑으면 [2, 3]이 남을 것이고, 1번을 뽑으면 [1, 3]이 남을 것이다. 이런 식으로 중복을 제거한다.
      let choice = clone.splice(i, 1);
      // count 대신 clone을 삽입한다.
      recursion(clone, bucket.concat(choice));
    }
  }
  
  recursion();
  return result;
};

물론 이것도 응용으로 조합의 숫자를 제한할 수 있다. arr.length === 0 대신 다른 조건을 걸면 된다.

조합

[가, 나, 다, 라] 요소가 있고 2개를 뽑아서 조합을 만든다고 했을 때, 순서에 상관없이 요소를 뽑아서 조합하는 것이기 때문에, 가나, 가다, 가라, 나다, 나라, 다라가 된다.

조합은 pickOrNot 개념을 도입하면 쉽게 알고리즘에 접목할 수 있다. 기본 개념은 간단하다. 하나를 집거나, 집지 않거나. 위의 요소로 예시를 들어 보겠다. 아, 2개를 뽑기 전에 기본적으로 이 알고리즘이 어떻게 흘러가는지 알아야 하기 때문에 전부 찍어 보겠다!

pickOrNot은 항상 처음부터 시작한다. 0번 인덱스부터 들어간다는 뜻이다.

const elements = ["가", "나", "다", "라"];
// 한 요소는 최대 한번만 선택 가능한 경우의 알고리즘 (ex. 부분집합, 조합)

const pickOrNot = (idx, basket) => {
  // 이쪽에 debugger를 놓고 돌려보기를 바란다!
  if (idx === elements.length) {
    // 탈출 조건
    // 원하는 것을 쓴다. 처음엔 console.log로 요소의 흐름을 파악해 보는 걸 추천.
    console.log(basket)
    return;
  }
  // pick
  // for문을 사용하지 않아도 idx + 1 덕에, 다음 인덱스로 넘어간다.
  //       다음 인덱스, 일회용 버킷에 이번 인덱스 추가
  pickOrNot(idx + 1, basket.concat(elements[idx]));
  // 순서는 아래와 같다.
  //1 (1, [가])
  //2 (2, [가, 나])
  //3 (3, [가, 나, 다])
  //4 (4, [가, 나, 다, 라])
  //5(탈출) console.log([가, 나, 다, 라])
  console.log(basket); // 콘솔로그를 한번 살펴보면서, 손으로 풀어 보는 게 가장 효과가 좋았다.
  // 4의 인덱스 4 부분은 재귀 호출이 끝났다.
  // 3으로 돌아간다.
  
  // skip  다음 인덱스, 인덱스 추가하지 않음
  pickOrNot(idx + 1, basket);
  //6 (4, [가, 나, 다]) 라를 배열에 추가하지 않는다.
  //7(탈출) console.log([가, 나, 다])
  
  // .. 반복 ..
};

// basket을 []으로 두는 이유는 이제 알겠죠?
pickOrNot(0, []);

// 이러한 경우, 이런 식의 흐름이 전개된다.
// [가, 나, 다, 라] [가, 나, 다] [가, 나, 라] [가, 나] [가, 다, 라] [가, 다] [가, 라] [가]
// [나, 다, 라] [나, 다] [나, 라] [나] [다, 라] [다] [라] []
// 인덱스를 하나씩 옮기며 경우의 수를 계속 제거하는 방식이다.
// 이 코드는 멱집합으로 사용할 수도 있다.



// pick or not이 아닌 다른 방법으로도 풀 수 있다.
// 가나다라는 아니지만, 충분히 이해할 수 있는 영역.

// 위의 순열, 중복순열 알고리즘을 살짝만 변형했다.
    const conbination = (arr, bucket, n) => {
      if (n === 0) {
        console.log(bucket);
        return;
      }
  
      for (let i = 0; i < arr.length; i++) {
        const choice = arr[i];
        const sliceArr = arr.slice();
        // 재귀
        conbination(sliceArr.slice(i + 1), bucket.concat(choice), n - 1);
      }
    }
    conbination([1, 2, 3, 4], [], 3)


// 숫자가 정해져 있다면, 반복문으로도 물론 가능하다.
    for (let i = 0; i < length; i++) {
      for (let j = i + 1; j < length; j++) {
        for (let k = j + 1; k < length; k++) {
          const number = [arr[i], arr[j], arr[k]];
          console.log(number);
        }
      }
    }

2개만 찍는 것은 여기서 조건만 추가해 주면 된다.

const elements = ["가", "나", "다", "라"];
const pickOrNot = (idx, basket) => {
  // 원하는 조건을 추가한다. 4 개 중 2 개를 뽑는 것을 원했으니, basket에 2개가 들어오면 리턴해 준다.
  if (basket.length === 2) {
    console.log(basket);
    return;
  }
  if (idx === elements.length) return; // 재귀를 멈추게 하는 조건문이다.
  pickOrNot(idx + 1, basket.concat(elements[idx]));
  pickOrNot(idx + 1, basket);
};
pickOrNot(0, []);
// [가, 나] [가, 다] [가, 라] [나, 다] [나, 라] [다, 라]

보면 알겠지만, 하나의 로직을 두고 응용하는 것이다.

메모이제이션

재귀함수를 사용할 때, 특히, 피보나치 수열을 사용할 때의 최대 걸림돌이 있다. 바로 재귀함수를 사용한다는 것이다.(?) 무슨 뜻이냐 하면, 재귀함수를 사용하게 되면 한번 계산했던 것을 똑같이 또 연산해야 한다. 그렇기에 n이 조금이라도 높아지면 시간복잡도가 굉장히 가파르게 올라가게 된다.

무슨 말이냐 하면, 피보나치의 재귀 사용법은 보통 이러하다.

function fibo(n) {
  if(n < 2) {
    return n;
  };
  
  // 요 부분이 재귀이자, 문제이다
  return fibo(n - 1) + fibo(n - 2);
}

해당 사진에서 보는 것처럼, 같은 연산을 여러 번 해야 된다는 점에서 비효율적이라고 할 수 있다. 그렇다면 어떻게 이것을 효율적으로 바꿀 수 있을까?

지금 소개하는 메모이제이션이 같은 연산을 없애 줄 수 있다. 메모이제이션은 한 번 연산한 것을 기억하게 한다. n이 5라고 가정했을 때, 4를 만들기 위해 3과 2를, 3을 만들기 위해 2와 1을 연산했던 것을 전부 기억해서, 여러 번 연산하지 않게 할 수 있다. 그러니까, 5 + 4 + 3 + 2를 한 번 연산했다면 해당 기억을 꺼내서 쓰면 되는 것이다.

방법은 간단(?)하다. 담을 수 있는 형태의 bucket을 만들어서 연산한 값을 집어넣고, 연산을 하기 전에 bucket에서 체크하면 된다. 비단 배열만 가능한 게 아니라 객체도 가능하다.

function fiboMemo(n) {
  // 0, 1은 자기 자신을 반환하기 때문에 미리 메모를 작성한다.
  let memo = [0, 1];
  
  // 피보나치 함수
  function fibo(n) {
    // 메모에 써져 있다면 해당 수를 반환한다.
    if(memo[n] !== undefined) {
      return memo[n];
    };
    // 메모에 써져 있지 않은 경우
    // 재귀를 사용해 n부터 2까지 확인한다.
    memo[n] = fiboMemo(n - 1) + fibo(n - 2); 
    
    // n번째 수를 반환한다.
    return memo[n];
  }
  return fibo(n);
}