15649. N과 M(1)

2주차 알고리즘 수업 과제입니다.

“알고리즘 시간 복잡도 계산하기”

문제 링크

시간 복잡도

$N$개의 자연수 중에서 서로 다른 M개의 수로 이루어진 수열을 뽑는 경우의 수는 $_NP_M$ 이다. 경우의 수가 곧 계산량 $T(N, M)$ 이 되므로, $O(_NP_M)$의 시간 복잡도를 갖게 된다.

\[\begin{align} T(N,M) & = {}_{N}P_{M} \\ \\ & = \frac{N!}{M!} \\ \\ & = N(N-1)(N-2)...(M+1) \\ \end{align}\]

문제의 조건에서 $N$과 $M$의 범위는 $1 \leq M \leq N \leq 8$ 이다. 최악의 경우는 $N=8, M=1$ 일 때인데, 이 때의 계산량을 구해보면 $T(8, 1) = 8! = 40320$ 으로, 모든 경우의 수를 하나씩 보아도 충분히 시간 내에 풀 수 있을 것으로 보인다.

DFS

완전 탐색을 위한 다양한 알고리즘이 있는데, 상대적으로 구현이 쉬운 DFS로 풀이한다.

Stack을 이용하여 수열을 구성하는 수를 순서대로 저장하고, 재귀방식으로 수열의 다음 숫자를 선택해나아간다.

from typing import List


def solve(N: int, M: int):
    _solve_w_dfs(N, M, [])


def _solve_w_dfs(N: int, M: int, stack: List[int]) -> None:
    if len(stack) == M:
        print_answer(stack)
        return
    stack.append(-1)
    for current_number in range(1, N+1):
        if current_number in stack:
            continue
        stack[-1] = current_number
        _solve_w_dfs(N, M, stack)
    stack.pop()


def print_answer(sequence: List[int]):
    print(' '.join(map(str, sequence)))


if __name__ == "__main__":
    N, M = map(int, input().split())
    solve(N, M)