알고리즘 문제 풀이

11 / 16

순열, 조합 문제 정복

알고리즘

순열과 조합을 구하는 알고리즘을 제대로 공부해보고 싶었다. 모두 DFS로 직접 구현해서 정리해보았다.


N과 M (1) - 순열

문제 링크


코드

N, M = map(int, input().split())

tmp = []


def dfs():
    if len(tmp) == M:
        print(*tmp)
        return

    for i in range(1, N + 1):
        if i not in tmp:
            tmp.append(i)
            dfs()
            tmp.pop()

dfs()

설명

순열을 구하는 문제이므로 1,2가 있다면 2,1도 있다. 따라서 for문에 따로 제약 없이 1부터 N까지를 범위로 설정한다.

다만 같은 숫자는 들어가면 안되므로 i가 tmp에 있는지 검사한다.

이제 i를 포함한 순열을 모두 구하고 이후에 다시 i를 제거해준다.


N과 M (2) - 조합

문제 링크


코드

N, M = map(int, input().split())

tmp = []


def dfs(idx):
    if len(tmp) == M:
        print(*tmp)
        return

    for i in range(idx, N + 1):
        if i not in tmp:
            tmp.append(i)
            dfs(i)
            tmp.pop()

dfs(1)

설명

조합을 구하는 문제이므로 순서를 고려하지 않는다. 또한 사전순으로 정렬해야 하므로 앞의 숫자가 뒤의 숫자보다 무조건 작다.

따라서 dfs 함수의 매개변수로 idx를 받아서 for문의 범위를 idx ~ N+1로 설정한다. (이렇게 하면 순서만 다르고 내용은 같은 조합을 배제할 수 있다)

순열 문제와 마찬가지로 같은 숫자는 들어가면 안되므로 i가 tmp에 있는지 검사한다.

이제 i를 포함한 조합을 모두 구하고 이후에 다시 i를 제거해준다.


N과 M (3) - 중복 순열

문제 링크


코드

N, M = map(int, input().split())

tmp = []


def dfs():
    if len(tmp) == M:
        print(*tmp)
        return

    for i in range(1, N + 1):
        tmp.append(i)
        dfs()
        tmp.pop()

dfs()

설명

순열 문제(1번)에서 i가 중복되는지 검사하는 코드만 제거해주면 된다.

if i not in tmp: # 이 부분을 제거

N과 M (4) - 중복 조합

문제 링크


코드

N, M = map(int, input().split())

tmp = []


def dfs(idx):
    if len(tmp) == M:
        print(*tmp)
        return

    for i in range(idx, N + 1):
        tmp.append(i)
        dfs(i)
        tmp.pop()

dfs(1)

설명

조합 문제(2번)에서 i가 중복되는지 검사하는 코드만 제거해주면 된다.

if i not in tmp: # 이 부분을 제거

N과 M (5) - 순열 응용

문제 링크


지금까지의 문제는 1부터 N까지의 순열/조합을 찾는 문제였다. 응용 문제는 주어진 숫자 중에서 순열/조합을 찾아야 한다.

코드

N, M = map(int, input().split())

nums = list(map(int, input().split()))
nums.sort()

tmp = []


def dfs():
    if len(tmp) == M:
        print(*[nums[x] for x in tmp])
        return

    for i in range(N):
        if i not in tmp:
            tmp.append(i)
            dfs()
            tmp.pop()

dfs()

설명

단순히 tmp를 출력하는 대신, 입력받은 숫자 중 인덱스가 tmp와 매칭되는 숫자를 출력한다.


N과 M (10) - 조합 응용

문제 링크


조합 응용 문제. 순열 응용 문제인 N과 M(5)와 같이 주어진 숫자 속에서 조합을 찾는다는 것은 같지만 주어진 숫자 중에 서로 중복되는 숫자가 있다는 점이 다르다.

코드

N, M = map(int, input().split())

nums = list(map(int, input().split()))
nums.sort()

tmp = []
s = set()


def dfs(idx):
    if len(tmp) == M:
        s.add(tuple([nums[x] for x in tmp]))
        return
    for i in range(idx, N):
        if i not in tmp:
            tmp.append(i)
            dfs(i)
            tmp.pop()

dfs(0)

for n in sorted(list(s)):
    print(*n)

설명

집합 연산을 활용해서 중복되는 출력을 방지한다.