기어가더라도 제대로

ref. https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ difficult. medium time. a day hint - O gpt chance - O Answer - X 목표 루트와 임의의 두 노드 p,q가 주어질 때 p와 q의 최소 공통 조상을 골라내는 문제 처음 전략 각 노드의 직전 부모부터 root까지의 모든 계보를 딕셔너리에 수집 딕셔너리에서 q,p만 해당하는 것을 배열로 빼냄 p,q의 선조들 중에서 공통되는 것의 리스트를 골라낸 후 root에서 가장 거리가 먼 순으로 골라냄 메모리 제한 초과가 떴음 그 이유는 모든 노드마다 자기 자신부터 root까지 유전 계보를 모두 저장하다 보니 메모리 제한 초과가 발생 GPT ..

정의 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기(Pruning)라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. DFS, BFS 정말 많이 나오는데 코테를 풀 때는 꼭알고 있어야하는 개념이다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 좌우한다. 어떻게 작성할 것인가? 우선, 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머..

BFS Breadth - First - Search 너비 우선 탐색이다. 최단 거리를 구하는 알고리즘에서 사용이 된다. DFS Depth - First - Search 깊이 우선 탐색 마찬 가지로 최단 거리를 구하는 알고리즘에서 사용된다. 사용처 최단 거리를 구하는 알고리즘 그림판 알고리즘 D에서 G로 가는 최단거리는? 그래프 탐색 알고리즘 너비 우선 탐색 깊이 우선 탐색 너비 우선 탐색 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 정점, A,B,C 등 기준점 큐를 이용해 탐색한 정보를 관리 D를 먼저 탐색 -> D를 엔큐 이어서 같은 거리에 있는 E, A 등을 탐색 -> E, A를 엔큐 D를 디큐, E를 디큐하고 E에서 갈 수 있는 정점이 없으므로 엔큐는 하지 않는다. A에서 갈 수 있는 B와 C를..