TIL 2021/06/22 16일차

백트래킹 (퇴각 검색)

• 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행
• 보통 재귀 로 구현하며 조건이 맞지 않으면 종료한다.
• DFS(깊이 우선 탐색) 기반

코드구현

n, m = list(map(int,input().split()))
stack = []

def dfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return

    for i in range(start, n+1):
        if i not in stack:
            stack.append(i)
            dfs(i + 1)
            stack.pop()

dfs(1)

• 백준 15649번 N과 M 문제의 코드이다.
• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 나타내는 문제이다.

오늘 정리

• 후반부 문제로 갈 수록 개념이 더 중요해지는것 같다.
• 아직 DFS, BFS, DP의 개념을 잘 모르니 내일 다시 한번 정리를 해야겠다.
• 알고리즘은 주특기주차가 시작해도 하루에 한 문제씩이라도 풀어봐야겠다.