순열

Item: 순열
Rating: 4

Written by on 25 Feb 2021

순열

기본적인 순열의 개념

가능한 모든 조합을 순서대로 뽑아서 줄을 세우는 것!

const array = [1, 2, 3];
// array를 통한 순열은 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

N!의 경우의 수를 가진다.

코드로써의 순열

N까지의 수를 우선 배열의 형태로 만든다.

let arr = [];
let result = [];
for (let i = 1; i <= N; i += 1) {
  arr.push(i);
} //N까지의 수를 배열의 형태로 만드는 반복문

우선 배열의 형태로 만든 후에 이 배열을 이용해 재귀 함수를 구현한다.

let recursion = (arr, temp = []) => {
  if (arr.lenngth === 0) {
    result.push(temp);
  } else {
    for (let i = 0; i < arr.length; i += 1) {
      let cur = arr.slice; // arr을 복사한다. (원래의 배열이 바뀌면 안되기 때문)
      let next = cur.splice(i, 1); // 카피한 배열에서 현재 i의 값을 가져옴과 동시에 카피한 배열을 자른다.
      recursion(cur.slice(), temp.concat(next)); //N은 3이고 i가 0일 때, recursionn([2,3] , [1])
    }
  }
  recursion(arr);
  return result;
};

순열의 구분

순열은 중복순열과 순열로 구분이된다. 가장 큰 차이점은 이름에서도 알 수 있듯이, 순열내의 요소르 중복하는지 아닌지의 차이점이 될 수 있을 것 같다.

순열

발표순서(1번부터 n번까지 모든 사람이 발표 하는 경우의 수)
서로 다른 n개
중복을 허락하지 않고 r개를 순서대로 나열하는 수

중복순열

n명이서 하는 가위바위보(가위, 가위, 보 등의 경우의 수)
서로 다른 n개
중복 가능하고 r개를 순서대로 나열하는 수

업무로 알고리즘을 대하면서 왜 이런 알고리즘을 써야 하는지에 대한 의문이 조금은 풀렸던 것 같다. 수학적인 부분을 알고리즘으로 푼다는 것이 흥미로웠고, 공부해야 할 부분이 늘었음에도 하기 싫다라는 느낌은 없었던 것 같다. 하지만 아직 코드로 바로 옮겨오는것에는 약간의 어려움이 있었다. 머리로 구현한 부분을 조금 더 세분화 할 필요는 있는 것 같다. 예를 들면, 순열에서 재귀를 구현하는 부분이 아직은 많이 낯설었다. 재귀는 알고리즘을 푸는데 가장 기본적인 풀이 방법인것을 알면서 소홀히 대했는데, 목표는 for문을 쓰지 않고 재귀로만 해결하기!

Rating: