늘 겸손하게

코딩테스트 문제를 풀다보면 순열, 조합 혹은 중복순열, 중복조합을 활용해야 하는 경우가 종종 있다. 하나하나 정리해보자. 1. 순열 순열은 주어진 n개의 원소에서 순서에 상관있게 r 개를 나열하는것을 말합니다. 예로 1, 2, 3, 4 에서 2개의 원소를 뽑아 나열하는 경우 1, 3 3, 1 은 다른 경우가 됩니다. 두 경우 모두 1과 3으로만 이루어져 있지만 순서가 다르기 때문에 다른 경우로 봅니다. 경우의 수는 총 nPr = n! / (n - r)! 구현 방식 백트래킹 방식으로 구현 가능하며 한 번 방문한 요소는 다시 방문할 필요가 없으므로 visit 배열을 활용해 방문하지 않은 원소 위주로 탐색합니다. depth를 1씩 늘려가며 이전에 방문하지 않은 요소를 정답 기록용 배열 (int[] rec) 에..

출처 : https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0 JavaScript로 순열과 조합 알고리즘 구현하기 1. 조합 서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 하고, 이 조합의 수를 기호로 nCr와 같이 나타낸다. 바로 예를 살펴보도록 하자. 4Com velog.io 자바스크립트로 순열과 조합을 만드는 코드 1. 순열 ( Permutation ) 정의 : 서로 다른 n개의 원소를 가지는 집합에..