목록Algorithm/N과M (2)
HANCO
N과M(2) 문제는 자칫 1번 문제와 매우 유사해 보일 수 있다. 하지만 차이점은 기존 solve(idx, cnt+1)을 이용해 재귀를 돌린 것과 다르게 solve(i, cnt+1)을 이용해 재귀를 돌린다. 첫번째 코드에서는 idx는 한 분기가 끝나고 증가는 재귀문이기 때문에 1과의 조합을 전부 선택한후 2와의 조합들을 선택하지만 두번째 코드는 i의 값으로 인자를 받기때문에 (1, 2), (1, 3), (1, 4) 이후에 (2, 1)이 아니라 무조건 뒤 숫자가 앞 숫자보다 큰 (2, 3)이 나오게 된다. #include #include #include using namespace std; int N, M; int arr[8]; vector v; bool sel[8]; void solve(int idx, ..
N과M 문제집은 순열과 조합등의 기본 지식을 연습해 볼 수 있는 좋은 예제가 된다. N과M(1) 문제는 nCm 조합문제이다. N개의 수열중에서 M개를 선택했을하는 수열을 구하는 문제이다. 간단한 재귀문으로 구현이 가능하다. 구현시 bool sel[8]; 코드를 이용하여 자기자신을 선택한 상태이면 고르지 않는 과정을 넣어주어야한다. 11, 22, 33, 44 등의 자기 수가 연달아서 삽입되는 것을 막아준다. #include #include #include using namespace std; int N, M; int arr[8]; vector v; bool sel[8]; void solve(int idx, int cnt){ if(cnt == M){ for(int i=0;i