[삼성SW테스트 준비] 4. 순열과 조합

학습자료: 알파카고수님의 블로그(https://m.blog.naver.com/wpghks7/221585604878)

[파이썬으로 시작하는 삼성 SW역량테스트] - 4. 순열과 조합

---

파이썬에서는 itertools를 이용해 순열과 조합을 쉽게 찾아낼 수 있지만, 이 모듈은 실제 시험장에서 못 쓰게 할 확률이 높으므로 dfs를 이용해 순열과 조합을 찾을 수 있어야 한다.

아래의 블로그 글들을 참고하여 파이썬 상에서 dfs를 이용해 순열과 조합을 만드는 연습을 하자!

순열, 조합 with dfs

[파이썬 python] 순열, 조합 코드로 구현하기

---

1-1. 순열과 조합의 개념

순열이란, 순서를 신경쓰며 뽑는 방식.
조합이란, 순서에 상관 없이 뽑는 방식

1-2. 파이썬의 순열과 조합 모듈

파이썬에는 순열과 조합 모듈이 있다. itertools를 사용하면 간단히 구할 수 있다(그러나 삼성 역량테스트에서는 이 모듈의 사용을 안할 가능성 높다.)

1. 중복 없는 순열
from itertools import permutations
2. 중복 없는 조합
from itertools import combinations
3. 중복 있는 순열 / 각 집단에서 추출
from itertools import product
4. 중복 있는 조합
from itertools import combinations_with_replacement as com

---

2-1. 중복 없는 순열 구현

# 예시 : 1,2,3 중 3개를 중복 없이 뽑는 순열
from itertools import permutations
print(list(permutations([1, 2, 3], 3)))

연습문제: 백준 10974 모든 순열 (https://www.acmicpc.net/problem/10974)

10974번: 모든 순열

# 10974 모든 순열 268ms
from itertools import permutations
n = int(input())
arr = []
for i in range(1, n+1):
    arr.append(i)
result = (list(permutations(arr, n)))
for r in result:
    for d in range(n):
        if d == n-1:
            print(r[d])
        else:
            print(r[d], end=' ')


# 10974 모든 순열 모범답안 180ms
from itertools import permutations
n = int(input())
result = (list(permutations(range(1, n+1))))
# *r => 튜플 언패킹
for r in result:
    print(*r)

---

연습문제: 백준 10819 차이를 최대로 (https://www.acmicpc.net/problem/10819)

10819번: 차이를 최대로

# 10819 차이를 최대로 184ms
from itertools import permutations
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
pms = list(permutations(list(map(int, input().split())), n))
max_cnt = 0
for pm in pms:
    cnt = 0
    for i in range(1, n):
        cnt += abs(pm[i-1] - pm[i])
    if cnt > max_cnt:
        max_cnt = cnt
print(max_cnt)

---

2-2. 중복 없는 조합 구현

연습문제: 백준 15650 N과 M(2) (https://www.acmicpc.net/problem/15650)

15650번: N과 M (2)

# 15650 N과 M(2) 72ms
import sys
from itertools import combinations
N, M = map(int, input().split())
comb = (list(combinations(range(1, N+1), M)))
for c in comb:
    print(*c)

---

연습문제: 백준 6603 로또 (https://www.acmicpc.net/problem/6603)

6603번: 로또

# 6603 로또 72ms
import sys
from itertools import combinations
while True:
    k, *S = map(int, input().split())
    if k == 0:
        break
    comb = list(combinations(S, 6))
    for c in comb:
        print(*c)
    print()

---

연습문제: 백준 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (https://www.acmicpc.net/problem/2422)

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

import sys
from itertools import combinations
input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, input().split())
all_comb = list(combinations(range(1, N+1), 3))
no_mat = [[0 for _ in range(N+1)] for z in range(N+1)]
for _ in range(M):
    y, x = map(int, input().split())
    no_mat[y][x] = 1
    no_mat[x][y] = 1
cnt = 0
for c in all_comb:
    if no_mat[c[0]][c[1]] or no_mat[c[1]][c[2]] or no_mat[c[2]][c[0]]:
        continue
    cnt += 1
print(cnt)

---

3-1. 중복 있는 순열 구현

연습문제: 백준 15651 N과 M(3) (https://www.acmicpc.net/problem/15651)

15651번: N과 M (3)

# 15651 N과 M(3) 2060ms
import sys
from itertools import product
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
ret = list(product(range(1, N+1), repeat=M))
for r in ret:
    print(*r)

---

연습문제: 백준 15656 N과 M(7) (https://www.acmicpc.net/problem/15656)

15656번: N과 M (7)

import sys
from itertools import product
input = lambda :sys.stdin.readline().rstrip()

N, M = map(int, input().split())
arr = list(map(int, input().split()))
ret = list(product(arr, repeat=M))
for r in sorted(ret):
    print(*r)

---

3-2. 중복 있는 조합 구현

연습문제: 백준 15652 N과 M(4) (https://www.acmicpc.net/problem/15654)

15654번: N과 M (5)

# 15652 N과 M (4) 88ms
# 비내림차순 => (1,4)는 되고 (4,1)은 안됨 => 중복 허용 조합
from itertools import combinations_with_replacement as combr
import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
arr = list(combr(range(1, N+1), M))
for a in arr:
    print(*a)