오늘은 봤던 문제중에 가장 흥미로웠던 파이썬 모듈과 백준 문제에 대해 정리하려한다.
난 접근 방법조차 난해 했지만 알고 있으면,
문제자체는 어려운 편이 아니였을 거라 생각한다.
문제 요약:
정수 n이 주어 졌을때, 1,2,3의 합으로만 이뤄진 조합으로 조합의 개수를 구하는 문제이다.
사실 문제 자체에 대한 설명과 접근 방법은 이미 뛰어난 사람들이 많이 리뷰를 해놔서 URL만 첨부한다.
그렇다. 키워드 자체가 DP로 접근하는 문제이므로 피보나치 수열과 같은 매커니즘으로 접근 한다고 한다.
그렇다면, 위 문제에 대한 결과가 n= n-3+n-2+n-1
인가?
from itertools import product
lst = [1, 2, 3]
target = 5
result = []
product_cnt = 0
# 최대 길이는 target // min(lst) → 모든 1로 채웠을 때 길이
for r in range(1, target + 1):
for comb in product(lst, repeat=r):
product_cnt +=1
if sum(comb) == target:
result.append(comb)
# 출력
for seq in result:
print(seq)
print(len(seq))
print(product_cnt)코드는 itertools 모듈에 product라는 함수를 활용했다.
product는 중복을 포함한 데카르트곱을 구현한다.
데카르트 곱은 두 집합으로부터 각각 원소를 하나씩 고른 순서쌍으로 이루어진 집합을 만들어주는 연산
[출처] 함수 (1) - 함수의 정의(데카르트 곱)|작성자 Dimen
라고 한다.
다시 코드로 돌아가서 설명하자면
for comb in product(lst, repeat=r):
product라는 함수는 이터레이터로 반복문 수행시 next()로 값을 하나씩 생성하고 있다.
이터레이터와 이터너블의 차이 설명은 생략한다.
그리고 코드를 내려가다보면
if sum(comb) == target:
result.append(comb)이 부분에서 만든 집합에서 합이 target과 같으면 리스트에 추가한다.
아래 결과를 보면 13으로 정확히 일치한다.
그렇다면
어디에 활용이 가능할까?
우선 은행 ATM기기가 비슷할 것 같다
ATM기에서 5만원권이랑 만원권 고를 수가 있는데
위 문제를 접목 시킬수 있지 않을까 싶다.
인출금액에서,
5만원권, 1만원이 각각 몇개일지 총 합 경우의 수를 세어보고
잔여 지폐로 반환이 가능한지 비교하면 되지 않을까?
무조건
if문으로 5만원권부터 인출되게하고 그담에
만원권으로 인출되게 하는 것보다.
5만원의 수량과 만원의 잔여 수량을 가지고 있다가
인출 시 경우의 수를 따져서 인출하면 되지 않을까 생각했는데
품이 너무 많이들 것 같다.
별로 적절한 예시는 아닌 것 같고
2차원, 3차원 이상인 게임에서 목적지까지의 경우에 수를 계산할 때, 활용이 될 지도 모르겠다.
근데 너무 고차원적이고 어려워 나중에 시도해 봐야겠다.
