의식이 흐르는대로 해보는 프로그래밍

접근 으아아아아아!!! 진짜 오래 걸렸다. 접근 자체는 너무 유명한 문제라 간단하게 했는데 최적화하는 과정에서 2일은 잡아먹었다. 외판원을 잡아다가 그냥 알아서 좀 가라고 너무 말하고싶었다... 결론은 DFS로 갈 경로를 정하고, BitMask로 지금까지 방문했던 도시를 저장한다. 또한 DP를 이용해서 해당 도시 방문의 최소비용을 저장하여, 효율성을 높인다. 앞서 해결했던, 2023.12.31 - [알고리즘(Algorithm)] - [BOJ] 1562번 : 계단 수(DP, BitMask) 문제에서 설명했듯이, BitMask 방법론은 너무 큰 N에 대해선 공간 효율면에서는 맞지않을 수 있다고 말했다. 하지만 이 문제는 N이 16정도로 별로 크지 않기 때문에 BitMask를 사용해볼 수 있다. BitMask..

접근 이진 탐색 트리의 전위 순회 결과만을 이용해서, 후위 순회 결과를 복원해내는 문제이다. 이진 탐색 트리의 전위, 중위 순회결과를 이용해서 트리를 복원해내는 방법이 있는데, 그 방법을 차용해서 해결했다. 해결 전위, 중위 순회 결과만이 있다면, 이진 탐색 트리는 복원이 가능하다. 전위 순회 결과는 항상 맨 처음의 값이 루트 노드이다. 중위 순회 결과는 `Left - Root - Right` 순서이기에, 특정 노드 기준으로 왼쪽 부분결과는 Root보다 작은 값들이고, 오른쪽 부분 결과는 큰 값들이다. 이 두가지 성질을 이용한다면, 이진 탐색 트리를 복원해낼 수 있다. 하지만 우리는 중위 순회 결과가 없기에, 중위 순회 결과를 만들어내야한다. 그냥 그건 간단하다. Root Node보다 작은 값들을 찾아서..

접근 치즈가 녹아내리는 문제다. 치즈 안쪽으로는 냉기가 있어서, 바깥쪽부터 녹는다는 아주 현실적인 문제. 중요한 포인트는 두가지다. 치즈 바깥쪽의 공기를 인식하는 것. 외부 공기와 접촉한 치즈만을 판단하는 것. 이 두가지만을 주의하고 문제를 해결하면 쉽게 해결이 가능하다. 해결 치즈 바깥쪽의 공기만을 인식하는 건 어떻게 하면될까? 치즈 내부의 공기를 생각해보자. 치즈 내부의 공기는 치즈로 둘러싸여있을 것이다. 그렇다면, 치즈인 곳은 탐색을 진행할 때 어떤 탐색(dfs, bfs)이든, 넣어주지 않게되면, 치즈 안쪽으로는 절대 탐색이 불가능하게 될 것이다. 그걸 이용해서 치즈 외부공기를 먼저 인식해주자. 그렇게 외부공기를 인식한다음, 그냥 이중 반복문으로 해결해도 되고, 또 효율적인 탐색법을 이용해도 좋으니..

접근 문제 자체는 복잡해보이지 않았다. 지나온 알파벳은 다시 들리지 않는다. 이게 이 문제의 중점이었던 것 같은데, 나는 백트래킹 최적화에 애를 먹어서 몇가지 기억하려고 남기려한다. 해결 사실 백트래킹 방법이 아니라, 충분히 BFS로 풀 수 있어보이지만 그냥 앞서서 N과M 문제 풀다보니, 백트래킹으로 해결하려고 시간을 썼다. 근데... 자꾸만 시간 초과가 나서 몇가지 최적화를 진행했다. 일단 백트래킹에 대해서 잠깐 서술해보자면, 영어 그대로 Back Tracking이다. 백트래킹은 재귀적으로 접근하는 알고리즘이다. 모든 경우를 고려하며, 재귀적으로 탐색을 진행하다가 특정 조건에 맞지않는 경우를 제외하고, 다시 탐색을 진행하는 것이다. DFS를 재귀로 구현할 때를 생각하면 형태가 거의 비슷하여 알고리즘의 ..