본문 바로가기

15649

[파이썬] 백준 연습문제 #15549. N과 M 완벽해설
알고리즘/백준 2024. 1. 23. [파이썬] 백준 연습문제 #15549. N과 M 완벽해설 문제 해설 이 문제는 백트래킹(Backtracking)을 사용해서 푸는 가장 기본적인 문제이다. 백트래킹은 재귀적 방법을 통해 모든 경우의 수를 탐색하는 알고리즘으로, 알고리즘 문제에서 정말 자주 출제가 되는 유형이다. 백트래킹을 부르는 다른 용어로는 깊이 우선 탐색 (DFS: Depth First Search), 재귀 함수 등이 있다. 백트래킹, 즉 깊이 우선 탐색은 위의 사진과 같이 모든 경우의 수를 깊게 들어갔다가 나오는 방식으로 진행이 되는 알고리즘이다. 즉 이 문제의 경우는 1에서 4까지의 수열을 구한다고 치면 1이라는 값을 처음으로 넣었을 때 다음 깊이의 탐색에서는 2, 3, 4 중 하나를 넣고, 만약 3을 넣었다고 한다면 다음 깊이에서는 2, 4 중 하나를 넣고, 여기서 4를 골랐다면 마지막..

티스토리툴바