목록중복조합 (1)

늘 겸손하게

Algorithm - 순열, 조합, 중복순열, 중복조합 (Java)

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