220628 화 Algorithms TIL

리트코드 938. Range Sum of BST Easy

• 문제
• 코드-파이썬
• 책 풀이를 보니 더이상 유효하지 않을 조건에 대해서는 탐색하지 않는 방법을 통해 시간을 단축할 수 있다.

백준 3109번 빵집 골드2

• 문제
• 코드-파이썬

Learned

• 두 가지의 최적화?를 해야 한다.
• DFS로 탐색하되, 위, 평행, 아래 순으로 탐색하게 하면 된다. 열을 0에서부터 R까지 내려오면서 탐색하므로 가장 위쪽 애들은 경로를 위쪽으로 몰아서 탐색하게 된다
• visited 체크 시에 왜, 경로가 성립된(마지막 행까지 도달한) 탐색이 아니면 visited를 해제해 줘야하는 거 아닌가 하고 처음에는 그렇게 구현했는데, 그렇게 하면 시간 초과
• 경로를 완성시키지 못해도, 위에서 이미 안된 경로라면 (다같이 오른쪽으로 이동하므로) 밑의 열에서도 탐색할 필요가 없다
• 이렇게 visited 체크를 하면 시간 초과 없이 통과된다.