반응형
알고리즘 분류 : 브루트 포스
K개의 숫자 중에서 6개를 뽑아서 나열하는 문제다. 재귀 함수를 이용하여 간단히 구현할 수 있지만, 조합(Combination)을 이용한 방법으로도 구현할 수 있다.
C++의 STL에 조합(combination)이 없으므로, 순열(permutation)을 이용해야 한다.
Python은 itertools에 있는 combinations를 이용하면 간단하다.
- 순열을 응용하여 조합을 만들 수 있다.
- N 개의 숫자가 있는 리스트 A에서 K 개의 숫자를 뽑는다면, nCk 라고 표기한다.
- 1이 K 개, 0이 N-K 개로 구성된 N 사이즈의 리스트 B를 생성한다. 예를 들어 8C6이라고 했을 때, 11111100 처럼 만든다.
- 리스트 B를 prev_permutation을 통해 순열로 돌리면서 루프를 돈다.
- 그리고 N 번 반복하는 for 문을 루프 내에 구성하여 B 리스트 원소의 값이 1일 경우, 같은 인덱스의 A 리스트의 값을 출력한다.
- 내림차 순으로 출력해야 한다면, 리스트 B의 순서를 반대로 뒤집고 next_permutation를 이용하면 된다.
C++ 소스코드
#include <cstdio> #include <algorithm> using namespace std; void solve(int n) { int c[n] = {0, }; for (int i=0; i<6; i++) c[i] = 1; int a[n]; for (int i=0; i<n; i++) scanf("%d", &a[i]); do { for (int i=0; i<n; i++) { if (c[i]) printf("%d ", a[i]); } printf("\n"); } while (prev_permutation(c, c+n)); printf("\n"); } int main() { int n; while (true) { scanf("%d", &n); if (n == 0) break; solve(n); } return 0; }
✓ 재귀 함수를 이용하여 구현할 수 있다. solve() 함수 수정.
void solve(int cnt, int index, vector<int> &lotto) { if (cnt == 6) { for (auto i : lotto) printf("%d ", i); printf("\n"); return; } if (index >= n) return; lotto.push_back(a[index]); solve(cnt+1, index+1, lotto); lotto.pop_back(); solve(cnt, index+1, lotto); }
Python 3 소스코드
from itertools import combinations while True: a = input().split() if a.pop(0) == '0': break for a in combinations(a, 6): print(" ".join(a)) print()
참고
반응형