[Python] itertools 라이브러리 (순열, 조합)

Changh2·2024년 8월 15일
0

Python 백준

목록 보기
3/5
post-thumbnail

브루트포스 알고리즘 문제 중 하나인
백준 2798번 '블랙잭' 문제를 풀고 기록을 남긴다. 문제 링크


📚 itertools

파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리로,
주로 순열과 조합을 간단히 얻기 위해 쓰인다.

from itertools import * 	# 내부 모듈을 모두 import

순열 (permutations)

num_list 에서 2개의 항목을 "순서있게" 나열
--> 같은 값들이 뽑히더라도 순서가 다르면 다른 경우의 수로 판단

from itertools import permutations

num_list = [1,5,3]
permutations_list = list(permutations(num_list,2))


print(permutations_list)
>>> [(1, 5), (1, 3), (5, 1), (5, 3), (3, 1), (3, 5)]

중복 순열 (product)

"중복을 허용하는" 순열

from itertools import product

num_list = [1,5,3]
product_list = list(product(num_list,repeat=2))

print(product_list)
>>> [(1, 1), (1, 5), (1, 3), (5, 1), (5, 5), (5, 3), (3, 1), (3, 5), (3, 3)]

조합 (combinations)

num_list 에서 2개의 항목을 "순서없이" 나열
--> 같은 값들이 뽑히면 같은 경우의 수로 판단

from itertools import combinations

num_list = [1,5,3]
combination_list = list(combinations(num_list,2))


print(combination_list)
>>> [(1, 5), (1, 3), (5, 3)]

중복 조합 (combinations_with_replacement)

"중복을 허용하는" 조합

from itertools import combinations_with_replacement

num_list = [1,5,3]
cwr_list = list(combinations_with_replacement(num_list,2))

print(cwr_list)
>>> [(1, 1), (1, 5), (1, 3), (5, 5), (5, 3), (3, 3)]

문제 풀이 예시

아래는 백준 2798번 '블랙잭' 문제의 정답 코드이다. 문제 링크

from itertools import *

N, M = map(int, input().split())
card_list = list(map(int, input().split()))
combination_list = list(combinations(card_list,3))
sum_list = []

for combination in combination_list:
    sum_list.append(sum(combination))

sum_list.sort()

for sum in sum_list:
    if sum <= M:
        res = sum

print(res)
profile
Shoot for the moon!

0개의 댓글