백준
-
WIL_03 : 삽질은 옳다 - [백준] 15649번 N과 M (1)개발자 이야기/Weekly I Learned(WIL) 2021. 3. 21. 11:44
삽질은 옳다. 삽질한 시간과 기억의 깊이는 비례한다. 이번 WIL에서는 한 주 동안 풀었던 백준 문제들 중 '삽질 TOP 5' 안에 들어간 'N과 M(1)' 문제를 리뷰해 보고자 한다. 문제 풀이 오늘의 문제는 백트래킹 전략을 이용해 문제를 해결할 수 있다. 백트래킹이란 퇴각검색이라고도 하는데 상태 공간 트리를 DFS(깊이우선탐색)의 방식으로 불필요한 경우를 배제하며 원하는 해답에 도달할 때까지 탐색하는 전략이다. 백트래킹에서 중요한 특징은 '가지치기'다. 이는 나무에서 불필요한 가지를 제거하듯 탐색 중 불필요한 경우를 제거하여 처리속도를 빠르게 향상시키는데에 도움을 준다. n, m = map(int, input().split()) stack = [] def back(): if len(stack) == ..