[삼성SW테스트 준비] 순열과 조합 연습 문제-1 (백준 15649, 15654, 15655, 15657, 15663, 15664, 15665, 15666)

문제 출처: 알파카고수님(https://m.blog.naver.com/wpghks7/221585604878)의 블로그

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

DFS로 순열과 조합을 직접 구현하며 정리해보았다. (DFS로 순열 구현하기는 사과농장님의 블로그를 참고했다!)

순열, 조합 with dfs

---

1. 중복 없는 순열

중복X = chk(혹은 visited) 배열을 둬서 다른 depth에 같은 수가 두번 들어가게 하지 않는다.
순열 = DFS에 인자로 begin(반복문을 시작하는 수)를 넣어주지 않아도 된다.

예시 문제: 15649 N과 M(1) https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

# 15649 N과 M(1) 320ms
def DFS(depth, chk, result):
    if depth == M:
        permutations.append(result[:]) # 그냥 result를 넣으면 안된다!(배열의 복사 참고)
        return

    for i in range(1, N+1):
        if chk[i]: continue
        chk[i] = True
        result[depth] = i
        DFS(depth+1, chk, result)
        chk[i] = False			  # chk를 풀어줘야 (1, 3) 이후 (3, 1) 같은 순열 만들 수 있다.

N, M = map(int, input().split())
chk = [False for _ in range(N+1)]
result = [0 for _ in range(M)]    # M개의 숫자들이 각각 담길 배열이다.
permutations = []                 # 모든 순열을 담을 빈 배열을 만든다. 
DFS(0, chk, result)

for p in permutations:
    for m in range(M):
        print(p[m], end=' ')
    print()

---

예시 문제: 15654 N과 M(5) https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

# 15654 N과 M(5)
# DFS로 수열 구현
import sys
input= lambda : sys.stdin.readline().rstrip()

def DFS(depth, result):
    if depth == M:
        # print(result) # 디버깅용
        permutations.append(result[:])
        return

    for i in range(N):
        if chk[i]: continue
        chk[i] = True
        result[depth] = arr[i]
        DFS(depth+1, result)
        chk[i] = False

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
result = [0 for _ in range(M)]
chk = [False for _ in range(N)]
permutations = []
DFS(0, result)

for p in permutations:
    for m in range(M):
        print(p[m], end=' ')
    print()

하지만 입력받은 숫자 중 중복되는 숫자가 있을 수 있다. 예를 들어 (1, 7 9, 9)를 입력받았다고 했을 때 기존의 중복 없는 순열의 방식대로 하게 되면 (1, 9(index==3)) 와 (1, 9(index==4)) 가 모두 다르게 처리되어 순열에 들어가게 된다. 하지만 이렇게 되면 중복된 수열을 출력하게 되는 것이라 안된다. 또 (9, 9)는 중복 없는 수열에 해당하는데, 왜냐하면 둘의 인덱스가 다르기 때문이다. 하지만 (9(3), 9(4)), (9(4), 9(3)) 이라는 내용물이 똑같은 순열이 서로 다른 순열로 들어가게 된다.

이걸 DFS에서 막을 수 있는 방법은 "같은 위치(depth)에는 인덱스가 달라도 value가 똑같은 수가 올 수 없도록 하는 것"이다. 자세한 방법은 아래의 블로그에 적혀있다. 처음에는 이걸 모르고 아래의 예시문제를 풀었는데, depth == M인 시점에서 'if result not in permutations' 일 때 result를 추가하는 방식으로 썼다가 시간 초과가 났다. in / not in 을 사용할 때 반복을 하게 돼서 그만큼 시간이 많이 소모되는 것이다.

N과 M -(9) [문제번호 : 15663] (Python 파이썬 풀이)

예시 문제: 15663 N과 M(8) https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

# 15663 N과 M (9) => 처음에 시간초과, 이후 184ms
# 입력
# 중복 허용 X, 같은 순열 허용 X 순열
def DFS(depth, result):
    if depth == M:
        # print(result) # 디버깅용
        permutations.append(result[:])
        return
    last = 0                        # depth 달라지면 0으로 last 초기화
    for i in range(N):
        if chk[i] : continue
        if last == arr[i] : continue
        chk[i] = True
        last = arr[i]               # 같은 자리(depth)에 오는 애가 같지 않게 하기.
        result[depth] = arr[i]
        DFS(depth + 1, result)
        chk[i] = False

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

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

# DFS
result = [0 for _ in range(M)]
chk = [False for _ in range(N)]
permutations = []
DFS(0, result)

for p in permutations:
    for m in range(M):
        print(p[m], end=' ')
    print()

 

---

2. 중복 없는 조합

조합 = DFS에 인자로 begin을 넣고 재귀할 때마다 i+1을 begin 위치에 넣어 (1, 7)은 가능하나 (7,1)은 불가능하게 만든다. (문제에서 '비내림차순' 이라는 단어로 표현이 된다)
(조합은 어차피 자기보다 큰 수가 다음 depth 자리에 오기 때문에 chk가 필요 없다.)

예시 문제: 15655 N과 M(6) https://www.acmicpc.net/problem/15655

15655번: N과 M (6)

# 15655 N과 M (6) 68ms
# 중복되지 않는 조합
def DFS(begin, depth, result):
    if depth == M:
        # print(result) # 디버깅용
        combinations.append(result[:])
        return

    for i in range(begin, N):
        result[depth] = arr[i]
        DFS(i+1, depth+1, result)   # 조합은 i+1을 재귀하여 나보다 큰 숫자가 앞에 오지 못함.

import sys
input = lambda : sys.stdin.readline().rstrip()
#입력
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort() 	# 오름차순으로 수열 만들기 위해

# DFS(중복X조합)
result = [0 for _ in range(M)]
combinations = []
DFS(0, 0, result)

for c in combinations:
    for m in range(M):
        print(c[m], end=' ')
    print()

순열과 마찬가지로 이것도 입력 값에 같은 수가 있을 경우, "같은 위치(depth)에는 인덱스가 달라도 value가 똑같은 수가 올 수 없도록 하는 것" 이 중요하다. 아래 예시 문제 참조.

예시 문제: 15664 N과 M(10) https://www.acmicpc.net/problem/15664

15664번: N과 M (10)

# 15664 N과 M (10) 68ms
def DFS(begin, depth, result):
    if depth == M:
        # print(result)       # 디버깅용
        combinations.append(result[:])
        return
    last = 0
    for i in range(begin, N):
        if last == arr[i] : continue
        last = arr[i]
        result[depth] = arr[i]
        DFS(i + 1, depth + 1, result)
# 입력
import sys
input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

#DFS - 중복 X 조합(depth 다르면 같은 수 상관X)
result = [0 for _ in range(M)]
combinations = []
DFS(0, 0, result)

for c in combinations:
    for m in range(M):
        print(c[m], end=' ')
    print()

---

3. 중복 있는 순열

중복O = chk 배열이 필요하지 않다.
순열 = DFS에 인자로 begin(반복문을 시작하는 수)를 넣어주지 않아도 된다.

앞서 입력받은 숫자 중 중복되는 숫자가 있는 경우, 예를 들어 (1, 7, 9, 9)를 입력받았다고 했을 때, 헷갈리면 안되는 부분이여기서 허용되는 중복은 (7, 7) 이런 식으로 같은 인덱스가 다른 위치(depth)에 두번 들어가도 된다는 거지, (9(3),9(4)), (9(4),9(3))으로 (9,9)라는 순열이  2개 이상 존재해도 된다는 의미는 아니다.
(문제에도 중복된 조합이 출력되지 않도록 하라고 나와있다.)

예시 문제: 15665 N과 M(11) https://www.acmicpc.net/problem/15665

15665번: N과 M (11)

# 15665 N과 M (11) 1488ms
def DFS(depth, result):
    if depth == M:
        # print(result)   # 디버깅용
        permutations.append(result[:])
        return
    last = 0
    for i in range(N):
        if last == arr[i]: continue
        last = arr[i]
        result[depth] = arr[i]
        DFS(depth+1, result)

#입력
import sys
input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

#DFS(중복 허용하는 수열. 깊이 다르면 같은 값 ok)
result = [0 for _ in range(M)]
permutations = []
DFS(0, result)

for p in permutations:
    for m in range(M):
        print(p[m], end=' ')
    print()

---

4. 중복 있는 조합

중복O =그리고 재귀 시 begin 위치에 i+1이 아니라 i가 들어간다.
조합 = DFS에 인자로 begin을 넣고 재귀할 때마다 i+1을 begin 위치에 넣어 (1, 7)은 가능하나 (7,1)은 불가능하게 만든다. (문제에서 '비내림차순' 이라는 단어로 표현이 된다)
(조합은 어차피 자기보다 큰 수가 다음 depth 자리에 오기 때문에 chk가 필요 없다.)

입력받는 수가 모두 다를 경우는 아래와 같이 풀면 된다.

예시 문제: 15657 N과 M(8) https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

# 15657 N과 M (8) #108ms
# 중복 허용 조합 만들기 => chk 배열 필요 X
def DFS(begin, depth, result):
    if depth == M:
        # print(result) #디버깅용
        combinations.append(result[:])
        return

    for i in range(begin, N):
        result[depth] = arr[i]
        DFS(i, depth+1, result) # 중복가능이니 i+1부터 말고 i부터 올라가도록

#입력
import sys
input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

# DFS
result = [0 for _ in range(M)]
combinations = []
DFS(0, 0, result)

for c in combinations:
    for m in range(M):
        print(c[m], end=' ')
    print()

입력받는 수에 중복되는 값이 있을 경우, 아래와 같이 풀 수 있다.

예시 문제: 15666 N과 M(12) https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

# 15666 N과 M (12) 84ms
def DFS(begin, depth, result):
    if depth == M:
        combinations.append(result[:])
        return
    last = 0
    for i in range(begin, N):
        if last == arr[i]: continue
        last = arr[i]
        result[depth] = arr[i]
        DFS(i, depth+1, result) # 중복 허용하므로 i+1 대신 i
# 입력
import sys
input = lambda : sys.stdin.readline().rstrip()
N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

# DFS(중복 허용하는 조합, depth 다르면 같은 값O)
result = [0 for _ in range(M)]
combinations = []
DFS(0, 0, result)

for c in combinations:
    for m in range(M):
        print(c[m], end=' ')
    print()