중복순열

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..

[백준] N과 M (자바/Java) 순열, 조합, 중복순열, 중복조합

N과 M은 순열, 조합, 중복순열, 중복조합을 연습할 수 있는 문제이다. 순열과 조합은 재귀를 사용하여 풀 수 있다. 1. 순열 순열에서 nPr은, N개의 수에서 가능한 r개의 수를, 순서대로 나열하는 것이다. 순열에는 순서가 존재하기 때문에 1 2 3과 3 2 1은 다른 경우로 취급한다. 이를 재귀와 dfs를 활용하여 풀면 다음과 같다. cnt는 dfs의 깊이를 의미한다. cnt가 M이 되면 M개의 순열이 완성되었다는 의미이므로 함수를 return 한다. 또한 순열은 중복을 허용하지 않기 때문에 순열에 포함되었는지 여부를 확인할 boolean check 배열이 필요하다. 배열의 처음부터 for문을 돌며 방문하지 않은 노드일 경우 check를 true로 바꾸고, 다시 깊이 cnt를 +1 한 다음, 재귀적..