N과 M (3) ( 15651 번 )

15651번: N과 M (3)

 

---

🧠 알고리즘

• 백트래킹 (Backtracking)

 

✔️ 동작 방식

• 문제 핵심 아이디어
  • 1부터 N까지의 자연수 중에서 길이가 M인 중복 가능 수열을 모두 생성하는 문제이다.
  • 현재 선택된 수열(now_lst)을 기준으로 재귀적으로 탐색한다.
• 재귀 구조
  1. 현재 수열(now_lst)의 길이가 M이면, 즉시 출력하고 재귀 종료.
  2. 아직 길이가 M보다 짧다면, 1부터 N까지 반복
     • num을 수열에 추가(append)
     • _dfs(now_lst) 재귀 호출 (같은 수 포함 가능)
     • 재귀 종료 후 pop()으로 수열 상태 복원 (백트래킹)
• 최종 출력
  • 길이가 M인 모든 수열을 탐색 과정에서 즉시 출력하며, 반복문이 1→N 순으로 진행되어 사전 순으로 출력됨.

---

 

🧾 코드

import sys
# 필요 파라미터
# 1) 현재 배열
def _dfs(now_lst):
    if len(now_lst) == m:
        print(*now_lst)
        return

    for num in range(1, n + 1):
        now_lst.append(num) # 수 추가
        _dfs(now_lst) # 재귀 호출
        now_lst.pop() # 백트래킹


n, m = map(int, sys.stdin.readline().rstrip().split())
_dfs([])

---

 

⏱️ 시간 복잡도

_dfs(now_lst) : 단계마다 n개의 가지가 생김.. ( 지수형 )

해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O(n ** m) )