순열과 조합

  • 2022 카카오 코딩 테스트에서 중복 조합 문제가 나와서 중복 조합 추가

순열과 조합

시뮬레이션

우리가 고등학생때 배웠던 순열, 조합과 똑같은 내용입니다. 하지만 수학이랑 다르게 직접 경우의 수를 계산하면서 확인하는 구현 문제를 풀을 예정입니다.

C++ 사용자는 next_permutaion을 이용하여 조합도 구할 수 있다고 합니다.

순열과 조합

사용법

우리는 6주차 자주 사용하는 모듈에서 잠깐 itertools 모듈에 있는 순열과 조합 방법을 읽었을 것입니다.

from itertools import permutations as pm # 순열
from itertools import combinations as cb # 조합

사용법은 pm, cb 둘 다 (순열/조합을 뽑아낼 자료형), (뽑아낼 길이)를 입력하면 됩니다.

# 순열
from itertools import permutations as pm

a = [1, 2, 3, 4]

for t in pm(a, 2):
    print(t)

# (1, 2)
# (1, 3)
# (1, 4)
# (2, 1)
# (2, 3)
# (2, 4)
# (3, 1)
# (3, 2)
# (3, 4)
# (4, 1)
# (4, 2)
# (4, 3)

# 혹은 길이가 2이므로 변수를 2개로 해서 각각 출력할 수 있음

for x, y in pm(a,2):
    print(x, y)

# 출력은 위에 괄호만 제거하면 같음
#조합
from itertools import combinations as cb

a = [4, 3, 2, 1]

for t in cb(a, 2):
    print(t)

# (4, 3)
# (4, 2)
# (4, 1)
# (3, 2)
# (3, 1)
# (2, 1)

# 조합도 마찬가지로 길이가 2이므로 for문에 변수를 2개 넣어 각각 출력 가능 

for x, y in cb(a, 2):
    print(x, y)

우리는 이미 고등학생때 순열이 무엇인지, 조합이 무엇인지 배웠기 때문에 따로 설명할 필요가 없을 것 같습니다.

바로 문제를 풀어보겠습니다.

연습 문제

연습 문제는 N과 M 시리즈 문제를 2문제 풀겠습니다. 참고로 모든 N과 M 문제들은 다음에 배울 재귀 함수로 전부 풀 수 있습니다.

BOJ 10974

순열을 사전 순으로 출력하라고 합니다.

일단 단순히 순열만 사용하면 정렬이 되지 않기 때문에 우리는 정렬된 값을 permuations에 넣고, for문과 join을 이용해 출력하면 될 것 같습니다.

아니면 따로 permutations를 구한 값을 리스트에 저장한 다음 정렬하고 출력해도 됩니다.

# 방법 1
from itertools import permutations as pm

n = int(input())
arr = [i for i in range(1, n+1)]

for t in pm(arr, n):
    print(' '.join(map(str,t))) # 튜플안의 값이 int이므로 str로 바꿈


# 방법 2
from itertools import permutations as pm

n = int(input())
arr = [i for i in range(n, 0, -1)] # 배열을 아무렇게나 넣음

ans = list(pm(arr, n))
ans.sort()

for i in range(len(ans)):
    print(' '.join(map(str,ans[i])))

BOJ 2798

N개의 카드중에서 3장을 골라 합이 M을 넘지 않으면서도 가장 큰 값을 구하라고 합니다. 넘지 않은 것이라면 3장의 합이 M이여도 된다는 뜻이네요.

이 문제는 순열, 조합 모두 풀 수 있습니다. 순열은 카드를 뽑는 순서까지 고려해서 경우의 수를 모두 뽑아내는 것이고, 조합은 카드를 뽑는 순서는 고려하지 않아서 순열보다 더 적은 경우의 수를 뽑아낼 수 있습니다.

그래서 우리는 조합을 이용하여 풀어보겠습니다. 일단 입력값을 받는 코드를 만들어줍시다.

from itertools import combinations as cb

n, m = map(int,input().split())
arr = list(map(int,input().split()))

여기서 답을 출력할 변수 ans을 만들어주고, for문과 cb()를 이용하여 ans의 값을 업데이트하면 됩니다.

from itertools import combinations as cb

n, m = map(int,input().split())
arr = list(map(int,input().split()))

ans = 0
for t in cb(arr, 3):
    if sum(t) <= m:
        ans = max(ans, sum(t))
print(ans)

풀어볼 문제

참고로 N과 M 시리즈는 다음에 배울 재귀 함수를 통해 모든 문제를 풀 수 있습니다.

중복 조합

2022 KAKAO BLINE RECRUITMENT에서 4번 문제로 중복 조합 문제가 출제되었습니다. 백트래킹으로도 풀 수 있었지만, 중복 조합인 것을 파악할 수 있으면 이 방법이 구현이 더 쉽습니다.

단순 조합을 사용할 때는 from itertools import combination이라면 중복 조합은 아래 코드를 사용하면 됩니다.

# 중복 조합
from itertools import combination_with_replacement as cbwr

for arr in cbwr([1, 2, 3, 4], 2): #cbwr(선택할 배열, 뽑는 갯수)
    print(arr)
    # 중복을 포함하여 [1, 2, 3, 4]에서 원소 2개를 포함하여 출력

문제를 풀어봅시다.

1부터 N에서 숫자를 M개 뽑는데, 같은 수를 여러 번 뽑아도 된다고 합니다. 같은 수를 여러 번 뽑을 수 있으면 중복 조합을 통해 문제를 풀 수 있습니다.

일단 n과 m을 입력 받아 봅시다.

n, m = map(int, input().split())

그리고 1부터 n까지의 배열을 만들어야 하니 배열을 만들어봅시다.

n, m = map(int, input().split())
arr = [i for i in range(1, n+1)]

이제 중복 조합 함수를 불러와서 출력을 해주면 됩니다.

from itertools import combinations_with_replacement as cbwr
n, m = map(int, input().split())
arr = [i for i in range(1, n+1)]
for x in cbwr(arr, m):
    print(' '.join(map(str, x)))
Previous카이사르 암호Next큐(queue), 덱(deque)

Last updated