0과 1의 쉼터

LCA, (Lowest Common Ancestor, 최소 공통 조상)

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다...

재귀 호출(Recursive Call)자기 자신을 호출하는 방식왜 Recursive Call이 필요할까요?미로를 탈출한다고 생각해봅시다. 막다른 길에 도달하면 이전 갈림길로 돌아가 다른 경로를 시도해야 합니다.이처럼 여러 선택지를 모두 시도해야 할 때, 실패한 경우 이전 상태로 되돌아가는(backtracking) 과정이 필요합니다.재귀 호출은 함수가 종료되기 전까지 상태를 유지하므로, 각 단계의 상태를(스택 구조로) 자동으로 기억합니다.💡하나의 선택지가 끝나면 이전 상태로 돌아가 다른 선택지를 시도할 수 있습니다.💡하나의 큰 문제를 여러 작은 문제로 분리하거나, 반복문보다 직관적이고 간결한 코드 작성이 가능합니다. 🔄 동작 원리피보나치 수열을 통해 재귀 호출의 동작 원리를 살펴봅시다.피보나치 수열이..