백준: 15649 N과 M (1)

N과 M 시리즈

• 원소가 1에서 N인 경우
  • 15649 N과 M (1)
  • 15650 N과 M (2)
  • 15651 N과 M (3)
  • 15652 N과 M (4)

• 원소가 주어지는 경우
  • N과 M (5 ~ 8)
  • N과 M (1 ~ 4)에서 원소에 대한 처리만 추가하면 된다.

• 중복 원소가 존재하는 경우
  • 15663 N과 M (9)
  • N과 M (10 ~ 12)는 (9)와 같이 set을 활용하며 로직은 N과 M 2 - 4와 동일하다.

 

문제

15649번: N과 M (1)

 

문제 풀이

 N개의 자연수에서 길이가 M인 수열을 구하는 문제이다. 이는 DFS를 통해 쉽게 풀 수 있으며, 파이썬의 경우 itertools를 이용해 풀 수 있다. 하지만 삼성 코딩 테스트에서는 itertools를 사용할 수 없다고 들었다. 따라서 단순히 라이브러리를 이용하는 것이 아닌, 어떤 원리로 답을 구할 수 있는가에 대해 이해하는 것이 중요하다.

 DFS를 통해 순열을 구하게 되면 depth 0 부터 시작해 그림과 같이 동작하게 된다. 순열은 각 원소의 중복을 허용하지 않기에, 하나의 원소를 선택할 때 중복으로 선택되지 않도록 체크해주어야 한다. 즉, DFS depth는 선택한 원소의 수를 의미하게 되며, DFS 내부에서 N만큼의 반복을 통해 DFS를 호출하게 되면 위의 그림과 같이 가지를 뻣으며 경우의 수를 찾을 수 있다.

 

코드

DFS를 사용한 문제 풀이

from sys import stdin


def dfs(depth):
    global answer
    # 재귀 종료 조건 → 선택하고자 하는 수
    if depth == m:
        answer.append([*check])
    else:
        for i in range(n):
            # 숫자는 1부터 시작하므로 + 1
            # 중복 선택을 방지하기 위해 체크함
            if i + 1 in check:
                continue
            # 중복 체크 방지
            check[depth] = i + 1
            dfs(depth + 1)
            # 호출 후 다시 해제
            check[depth] = 0

if __name__ == '__main__':
    answer = []
    n, m = map(int, stdin.readline().split())
    check = [0] * m
    dfs(0)

    for num in answer:
        print(*num)

 

itertools permutation을 활용한 풀이

from itertools import permutations

N, M = map(int, input().split())
nums = [num + 1 for num in range(N)]
for cases in permutations(nums, M):
    for case in cases:
        print(case, end=' ')
    print()