백준 6603 로또 (재귀로 부분집합/순열/조합 구현 연습)

 

더 많은 풀이

Algorithms & Data structures

 

(문제 이외에 재귀 기법으로 배열의 모든 부분집합 구하기 / 순열 구하기 / 조합을 구하는 코드를 하단에 작성해보았습니다)

💡 재귀 팁!
완료되는 시점을 꼭 명시해주기
트리구조 그려보면 패턴이 더 가시적으로 보임 

 

📐 문제

---

로또 뽑기 문제.

• 숫자 {1, 2, ..., 49} 중 6개를 고름
• 로또 번호를 선택 시 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 → 집합 S를 만든 다음 → 그 수만 가지고 번호를 선택하는 것이다.
• 예시) k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
• 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

 

📐 접근법

---

k개의 수 중에서 6개 수를 구하도록 : 조합문제

 

 

📐 풀이

---

(외부 라이브러리 미사용 조합 직접 구현)

def combinations(nums, k, ans=[]):
    if len(ans) == k:
        res.append(ans)
        return
    for num in nums:
        newAns = ans + [num]
        newNums = [x for x in nums if x > num]
        combinations(newNums, k, newAns)

res = [] # 모든 조합이 담기는 부분. 전역적으로 접근 가능하도록 이곳에 위치.
while True: 
    nums = list(map(int, input().split()))
    if len(nums) == 1:
        break
    k = nums[0]
    s = nums[1:]   
    
    combinations(s, 6, []) 
    for subset in res:
        print(*subset)
    res = [] # 테스트 케이스 한번 실행 시 초기화
    print()

(외부 라이브러리 사용)

from itertools import combinations

while True: 
    nums = list(map(int, input().split()))
    if not len(nums):
        break
    k = nums[0]
    s = nums[1:]   
    
    subsets = sorted(list(combinations(s, 6)))
    for subset in subsets:
        print(*subset)
    print()

 

 

📐 [추가공부] 재귀로 부분 집합 구하기

---

💡아이디어

[1,2,3]의 부분집합을 구할 때, 각 원소를 순회하며 다음과 같은 과정을 거친다.

1. 초기화
2. [[]]
3. 1일 때, 이전 조합을 iterate하며 1을 더한 조합을 추가.⇒ [[],[1]]
4. [] + [1] = [1]
5. 2일 때, 같은 로직[1] + [2] = [1,2]
6. ⇒ [[],[1],[2],[1,2]]
7. [] + [2] = [2]
8. 3일 때 같은 로직[1] + [3] = [1,3][1,2] + [3] = [1,2,3]
9. ⇒ [[],[1],[2],[1,2], [3], [1,3], [2,3], [1,2,3]]
10. [2] + [3] = [2,3]
11. [] + [3] = [3]

재귀를 사용한다고 했을 때,

이전 조합 + 이전 조합에 새로운 원소를 추가한 조합을 반환하는 재귀 로직을 짤 수 있겠다.

def subsets(nums): 
    if not nums:
        return [[]] 
    old_subset = subsets(nums[:-1]) # 이전 조합
    return old_subset + [num + [nums[-1]] for num in old_subset] # nums[-1] 새로운 원소

subsets([1,2,3]) # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

📐 재귀로 순열/조합 만들기

---

위 로직을 확장하여 재귀로 순열/조합을 만들 수 있다. 로직은 동일하다. 대표적으로 [1,2,3,4,5] 중 3개의 원소를 뽑는 순열, 조합을 구한다고 해보자.

리스트 내 원소 내 하나를 뽑고 → 뽑은 원소를 제외한 나머지 리스트 중 하나의 원소를 뽑고 → 이 과정을 원소 3개를 뽑을 때까지 반복(재귀)한다.

모든 조합을 고려해야하기에 [1,2,3,4,5] 원소를 반복하여 첫 원소를 뽑는다.

순열의 경우 >

def permutation(nums, k, ans=[]):
		"""
		nums: 배열
		k: 뽑을 개수
		ans: 뽑은 원소
		"""
    if len(ans) == k:
        res.append(ans)
        return
    for num in nums:
        newAns = ans + [num]
        newNums = [x for x in nums if x != num]
        combinations(newNums, k, newAns)

res = [] # 정담이 담기는 곳
combinations([1,2,3,4,5], 2, []) 
print(res) # [[1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4]]

조합의 경우 >

조합의 경우, 전체적인 로직은 동일하다. 차이점이 있다면 하나의 원소를 뽑고, 그 다음 그것을 제외한 또 다른 원소를 뽑을 때 이전 뽑은 원소보다 더 큰 원소 (혹은 더 큰 작은 원소)만 뽑도록 하여 한방향으로 뽑기를 제한하여 [1,2]와 [2,1]를 같은 경우로 여기지 않을 수 있다.

def combinations(nums, k, ans=[]):
		"""
		nums: 배열
		k: 뽑을 개수
		ans: 뽑은 원소
		"""
    if len(ans) == k:
        res.append(ans)
        return
    for num in nums:
        newAns = ans + [num]
        newNums = [x for x in nums if x > num]
        combinations(newNums, k, newAns)

res = []
combinations([1,2,3,4,5], 2, []) 
print(res) # [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]