목록백준 15649 (1)

시작이 반

[백준] 15649번(python 파이썬)

백트래킹의 기초 문제이다. 완전탐색을 하게된다. 재귀를 이용하여 풀게되는데 이때 더이상 탐색을 할 필요가 없다면 재귀 탐색을 멈추게된다. 첫 풀이 해당 숫자에 visited를 부여하여 방문을 했는지 계속 체크하고 visited를 deepcopy하여 넘겨주는 식으로 하였다. 이렇게 하면 숫자가 많아질수록 list를 엄청나게 많이 만들게 되고 또한 deepcopy를 하는데에 시간도 길리기 때문에 메모리, 시간 둘다 비효율적이다. ....... 정답 풀이 visited라는 상태 체크를 하는 것이 아니라, 방문한 숫자를 집어넣는 list를 만들어 풀게 된다. 1. 깊이가 출력하는 숫자의 길이가 같을경우 재귀를 멈춘다. 2. i : 1 ~ n 까지 반복을 하여 list에 i에 해당하는 숫자가 없을경우 i를 app..
알고리즘/백준 2021. 1. 10. 00:09
이전 Prev 1 Next 다음