[class2]백준 10974번(모든 순열) - 코테공부 24일차(2025.02.15)

문제유형

순열 알고리즘

풀이 방법 도출 과정

1. 순열 알고리즘을 구현하는 것이 목표

시간 복잡도

최악의 순간을 생각하면 8!이기 때문에 이정도면 1억 번은 넘기지 않는 수이다. 

코드 및 간단설명

순열 알고리즘을 구현해보았다.

N = int(input())
lst = []

for i in range(1, N + 1):
    lst.append(i)

choose = []
check = [False] * N

def permutation(level):
    if level == N:
        print(*choose)
        return
    
    for i in range(0, N):
        if check[i] == True:
            continue
        
        choose.append(lst[i])
        check[i] = True
        
        permutation(level + 1)
        check[i] = False
        
        choose.pop()

permutation(0)

다른 풀이

1) 파이썬 라이브러리 사용

Python 내장 라이브러리인 itertools.permutations를 이용하여 풀어보는 방법이다. 이 방법은 C로 구현된 내장 함수이기 때문에 순열 생성에 있어서 매우 효율적이다.

from itertools import permutations

N = int(input())
numbers = list(range(1, N + 1))

for perm in permutations(numbers):
    print(*perm)