#15652번 - N과 M (4) 통과 Code import sys n, m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m : return print(' '.join(map(str, a))) for i in range(1, n+1): if len(a) > 0: if i < a[-1]: continue a.append(i) solution() a.pop() solution() 시간 복잡도 : O(n^m) 공간 복잡도 : O(1)

# 15651번 - N과 M (3) 통과 Code import sys n, m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m : return print(' '.join(map(str, a))) for i in range(1, n+1): a.append(i) solution() a.pop() solution() 시간 복잡도 : O(n^m) 공간 복잡도 : O(1)

BOJ # 15650 - N과 M (2) Back Tracking 문제이다. N과 M (1) 문제에서 살짝 변형된 것으로, (1) 문제를 풀 수 있다면 쉽게 통과할 수 있다. 통과 Code import sys n,m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m: print(' '.join(map(str, a))) for i in range(1, n+1): if i in a: continue elif len(a) >= 1 and i < max(a) : continue a.append(i) solution() a.pop() solution()

Back Tracking "가능한 모든 방법을 탐색하겠다." Back Tracking 이란? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책 후보를 찾되, 가능성이 없는 경로는 사전에 차단(Purning)하여 효율을 높이는 알고리즘이다. 비슷한 알고리즘으론 DFS(완전 탐색 방법)가 있다. 하지만 이 알고리즘은 말 그대로 모든 경로를 정직하게 탐색하므로, 가능성이 없는 경로까지도 깊게 파고들어 가 효율이 떨어진다. 문제 Tip DFS로 경로를 탐색하던 과정에서, 조건문 등을 걸어 가지치기를 하는 방식으로 가야 한다. BOJ # 15649번 : N과 M (1) 백트레킹는 기본적으로 재귀 문제이다. 이를 잘 생각하며 풀어보길 바란다. 통과 예시 import sys n, m = map(int, sys..