로또

---

title: “6603 - 로또”
date: “2019-02-13”

category: “algorithm”

문제요약

1. 로또에 기입할 번호를 입력받는다.
2. 입력받는 번호는 6개 이상이며, 로또에는 6개의 숫자밖에 선택할 수 없다.
3. 입력받은 번호중 6개를 선택하여 만들수 있는 순열을 모두 출력한다. (단, 사전순으로 출력해야한다.)
4. 숫자 0을 입력받을 때까지 1 ~ 3번 과정을 반복한다.

접근법

이 문제는 다양한 방법으로 풀수 있다. 실제로 백준 사이트에서도 DFS, BFS, 백트래킹, 브루트포스등 다양한 알고리즘으로 분류되어 있다. 즉 여러가지 방법으로 풀수 있다는 말이 된다. 지금까지 BFS를 이용해서 많은 문제를 풀어봤기 때문에 이번에는 DFS를 이용해서 문제를 풀어보고자 한다. (실제로는 DFS가 아닐수도,,,) DFS와 BFS는 완전탐색을 수행하는 알고리즘이라는 점에서 목표가 같지만 BFS는 큐를 사용하는 반면, DFS는 스택을 사용한다는 차이점이 있다. 지금까지는 파이썬의 list 자료형을 큐처럼 사용하였지만 이번에는 재귀함수를 이용하여 마치 스택을 이용하는 것과 같은 효과를 주려고 한다.

문제에 나와있는 첫번째 TC를 살펴보자. 첫번째 TC에는 7 1 2 3 4 5 6 7 7개의 숫자가 주어진다. 7개의 숫자를 이용해서 만들 수 있는 조합의 개수는 7C6으로 7개가 된다. 로또에 들어가는 6개의 값을 각각 A, B, C, D, E, F라고 하면, 먼저 A에 1 ~ 7까지 선택한다. 다음 B를 선택할 때는 A에서 선택된 값 다음부터 값을 선택한다. A에 1이 선택되었다면 B에는 2 ~ 7까지 값중 1개를 선택할 수 있고 A에 2가 선택되었다면 B에는 3 ~ 7까지 값중 1개를 선택할 수 있다. 따라서 A에 3이 선택되면 마지막 F에 해당하는 값을 선택할 수 없기 때문에 A에 3이나 3 다음 값이 선택되는 경우는 고려할 필요가 없다.

위와 같은 규칙을 활용해서 백트래킹 기법을 활용하여 실행시간을 더욱 줄일 수 있지만 이번에는 간단하게 DFS를 이용하여 Combination을 만드는 방법만 사용하였다. 아마 인풋으로 올 수 있는 값이 50이 아니라 100이 되면, 경우의 수가 11억이상의 경우의 수가 되기 때문에 백트래킹을 써야할 것이다. 이문제에서는 인풋의 범위가 작으므로 백트래킹을 쓰지 않고 진행하였다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)