[백트래킹/JS] 순열/조합

이승혜·2021년 7월 31일
1

알고리즘

목록 보기
4/6

💡 순열 (nPr)

서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다(순서 상관O)

순서가 상관있다는 말이 무슨 말인지 이해가 잘 안간다면,
현관문 비밀번호를 생각하면 된다.
현관문 비밀번호가 2580일 때 정확한 순서를 지켜 2580이라고 입력해야 문이 열리지,
5820이라고 입력한다고 해서 문이 열리지는 않는다.
즉, 이렇게 순서가 있는 경우의 수를 순열이라고 한다

문제 링크

https://www.acmicpc.net/problem/15649

풀이

예를 들어, 입력으로 '4 2'를 받았다고 치자
1부터 4(N)까지의 자연수 중(서로 다른 n개)에서 중복 없이 2(M)개를 고른 수열을 출력해야 한다
예제를 출력해보면

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

다음과 같은 결과가 나와야 한다
순서가 상관이 있는 순열이기 때문에,
1 2를 뽑았다고 하더라도 2 1을 뽑아야 한다

let n, m;
let visited;
let ans = [];
let ret = [];

const input = () => {
  // n과 m 입력을 받아준다
  [n, m] = getLine().split(' ').map(Number);
  // 방문 배열을 설정 
  // why? 방문시 체크를 하고 탐색이 끝나면 방문을 초기화하여 다음 노드를 탐색하기 위해
  visited = new Array(n);
};

const permutation = () => {
  // m개를 다 뽑았다면 ret배열에 결과 값을 넣어주고 종료시킨다
  if (ans.length == m) {
    ret.push(ans.join(' '));
    return;
  }

  // 1부터 n까지의 자연수 중에서 m개를 뽑아야 하므로 
  // 1부터 n까지 반복문을 돌려준다
  for (let i = 1; i <= n; ++i) {
    if (visited[i]) {
      continue;
    }
    
    visited[i] = true;
    ans.push(i);
    permutation();
    visited[i] = false;
    ans.pop();
  }
}

const solve = () => {
  permutation();
  console.log(ret.join('\n'));
};

const main = () => {
  input();
  solve();
};

main();

👇 이 부분을 이해를 잘 못했었는데, 그림을 보면 이해가 쉽다

visited[i] = true;
ans.push(i);
permutation();
visited[i] = false;
ans.pop();


for문을 돌며 모든 index에 방문해서 ans 배열에 값을 넣는다
이미 들어간 값은 visited 값을 true로 바꾼다(중복해서 넣지 않기 위해)
ans값이 m개가 되면(m개를 뽑기로 했으므로) ret 배열에 넣어준다
재귀의 호출이 끝나면 visited 값을 false로 바꿔준 후,
ans의 마지막 값을 빼주어 새로운 값이 들어갈 수 있도록 해준다

그래도 이해가 안간다면 디버깅을 해보거나,
손으로 하나하나 함수를 따라가며 써보면 이해가 쉽다...

이런식으로.. (저만 알아볼 수 있습니다ㅠ)

출력


중복 없이 순서대로 뽑은 것을 볼 수 있다

💡 조합 (nCr)

서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다(순서 상관X)

순서가 상관없다는 말의 의미는 청소 당번을 뽑는 것과 같다
청소 당번으로 철수와 영희를 뽑든 영희와 철수를 뽑든 똑같다는 의미다

문제 링크

https://www.acmicpc.net/problem/15650

풀이

위와 같이 입력으로 '4 2'를 받았다고 치자
1부터 4(N)까지의 자연수 중(서로 다른 n개)에서 중복 없이 2(M)개를 고른 수열을 출력해야 한다는 것은 순열 문제와 같다
그 밑에 조건으로 "고른 수열은 오름차순이어야 한다."가 적혀있다
1 2, 2 1을 뽑았을 때 2 1은 제거한다 (고른 수열은 오름차순이어야 하기 때문)
이 말은 즉, 순서에 상관없는 조합을 출력하란 말이 된다
예제를 출력해보면

1 2
1 3
1 4
2 3
2 4
3 4

다음과 같다

let n, m;
let ans = [];
let ret = [];

const input = () => {
  [n, m] = getLine().split(' ').map(Number);
};

function combination(cur) {
  if (ans.length == m) {
    ret.push(ans.join(' '));
    return;
  }

  for (let i = cur + 1; i <= n; ++i) {
    ans.push(i);
    combination(i);
    ans.pop();
  }
}

const solve = () => {
  combination(0);
  console.log(ret.join('\n'));
};

const main = () => {
  input();
  solve();
};

main();

코드는 순열과 똑같다
다른 점은 매개 변수로 현재값을 받아,
현재값의 다음 수 부터 반복문을 돌려준다는 것이다
당연히 오름차순의 수열을 구해야 하기 때문에, 현재 값 이전의 값들은 볼 필요가 없기 때문!
현재 값 다음 수부터 순열과 같이 수열을 구해주면 된다

또 하나 다른 점은 visited 배열이 필요없다는 것이다
받아온 cur 값을 cur+1로 넘겨주기만 하면 되기 때문이다

profile
더 높이

0개의 댓글