순열과 조합

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

순열과 조합

• 자주 사용하는 모듈(itertools module)

• 순열과 조합 - 현재 글

시뮬레이션

• 2차원 리스트

• 자주 사용하는 모듈

• 순열과 조합 - 현재 글

• 재귀 함수 Ⅰ

• 재귀 함수 Ⅱ

• 그래프 알고리즘 소개

• 플러드 필

• 시뮬레이션 Ⅰ

• 시뮬레이션 Ⅱ

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

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

https://www.acmicpc.net/problem/10974www.acmicpc.net

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

일단 단순히 순열만 사용하면 정렬이 되지 않기 때문에 우리는 정렬된 값을 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

https://www.acmicpc.net/problem/2798www.acmicpc.net

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 시리즈는 다음에 배울 재귀 함수를 통해 모든 문제를 풀 수 있습니다.

• https://www.acmicpc.net/problem/15649

• https://www.acmicpc.net/problem/15650

• https://www.acmicpc.net/problem/1182

중복 조합

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개를 포함하여 출력

문제를 풀어봅시다.

https://www.acmicpc.net/problem/15652www.acmicpc.net

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)))