N과 M (1) ( 15649 번 )

15649번: N과 M (1)

 

---

🧠 알고리즘

• 백트래킹 (Backtracking)

 

✔️ 동작 방식

• 문제 핵심 아이디어
  • 1부터 N까지의 자연수 중에서 중복 없이 M개를 선택하는 모든 수열 을 구하는 문제이다.
  • 이를 위해 현재까지 선택한 숫자(now_lst)와 이미 사용한 숫자를 기록하는 배열(check)을 함께 관리하며, 가능한 모든 경우를 재귀적으로 탐색한다.
• 재귀 구조
  1. 현재 수열(now_lst)의 길이가 M이 되면 ' '.join(map(str, now_lst)) 형태로 문자열을 만들어 즉시 출력한다.
  2. 아직 길이가 M보다 짧다면, 1부터 N까지의 숫자 중 아직 사용되지 않은 숫자(check[num] == True)를 하나 선택한다.
  3. 선택한 숫자를 now_lst에 추가하고 해당 숫자의 사용 여부를 False로 변경한 뒤, _dfs()를 재귀 호출한다.
  4. 하위 재귀 호출이 끝나면 pop()과 check[num] = True를 통해 이전 상태로 되돌린다 (백트래킹의 핵심).
• 최종 출력
  • 길이가 M인 모든 수열을 탐색 과정에서 즉시 출력

---

 

🧾 코드

import sys
# 필요한 파라미터
# 1) 현재 배열

def _dfs(now_lst):
    if len(now_lst) == m:
        print(' '.join(map(str, now_lst)))
        return

    for num in range(1, n + 1):
        if check[num]:
            check[num] = False
            now_lst.append(num)

            _dfs(now_lst)

            check[num] = True # 원복
            now_lst.pop()


n, m = map(int, sys.stdin.readline().rstrip().split())
check = [True] * (n + 1)

_dfs([])

---

 

⏱️ 시간 복잡도

_dfs(now_lst) : 백 트래킹 ( 팩토리얼 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 팩토리얼 시간 복잡도 ( O(N! / (N−M)!) )