# LCA
SWEA 1855 영준이의 진짜 BFS
SWEA 1855 <-클릭LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다.아이디어를 간단하게 요약하면 다음과 같다 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 d
가장 가까운 공통 조상 3584
깊이를 맞추어주고 같이 올라가다보면 같은 값이 나오는 구간이 있다. 그것이 최소 공통 조상이다.더 깊은 곳을 찾아낸 뒤 깊이를 얕은 곳과 맞추어준다. 그 후 같이 올라가다 보면 값이 같아지는데 그것은 조상이 같다는 의미이다.다른 풀이가 있나 해서 찾아보니 한쪽에서 끝까
[ 백준 / Python3 ][골드3] 11437 - LCA
https://www.acmicpc.net/problem/11437LCA 알고리즘을 사용하기 위해서는 노드마다 깊이와 부모노드가 정해져 있어야 한다.하지만 이 문제에서는 루트노드가 1인 그래프로 주어졌기 때문에 루트노드가 1이라는 것 하나로 트리의 구조를 파악
[ SWEA / Python3 ] 1855 - 영준이의 진짜 bfs
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc
Leetcode - 1644. Lowest Common Ancestor of a Binary Tree II
기본적으로 236. Lowest Common Ancestor of a Binary Tree 와 코드는 동일. 하지만 q, p노드를 실제로 방문했는지 체크했는지 여부 추가. 따라서 모든 노드를 방문해야함. 그래서 아래 (1) 코드는 양쪽 자식노드 재귀 호출을 마친 이후
Leetcode - 235. Lowest Common Ancestor of a Binary Search Tree
주어진 Binary Search Tree 에서 두 노드의 가장 가까운 공통 부모 (LCA)를 찾아라.현재 노드의 값이 p, q보다 작다면 LCA는 우측 자식노드에 존재. 이를 재귀적으로 반복.종료조건(base case) 현재 노드 값이 p, q보다 작지도 않고, p,
Leetcode - 236. Lowest Common Ancestor of a Binary Tree
binary tree에서 두 노드의 가장 가까운 공통 부모를 찾아라. 재귀함수는 자식노드에 q, p노드가 존재하면 해당 노드를 리턴, 아니라면 NULL리턴. left, right에 노드가 NULL인지 아닌지로 현재 노드가 LCA인지 아닌지 판단 가능.재귀 호출 이후 논
[CS 공부] 22.10.05
MSD(Most-Significant Digit) 가 아닌 LSD(Least-Significant Digit) 부터 비교해야함 찾는 방법두 정점에 대해 루트 노드 부터 본인의 부모까지 정점을 각각 리스트로 저장한다.리스트에서 정점을 하나씩 꺼내서 같은 지 확인한다.(리
백준 2233 사과나무
문제 풀이 두 썩은 사과를 잘라내기 위해 가지를 잘라내되, 떨어지는 사과의 개수를 최소로 한다는 것은 두 썩은 사과의 최소 공통 조상을 찾아내라는 의미이다. 즉, LCA 알고리즘을 적용시키면 된다. 단, 이 문제에서는 문자열을 가지고 Tree를 생성하는 과정을 요구하고 있다. Tree 생성 1) 스택 사용 0인 경우 level이 더 높아지고, 1인 ...
<Baekjoon> #3584_LCA, DFS 가장 가까운 공통 조상 java
\[BOJ 참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..) 문제 제목에서도 주어진대로 가장 가까운
[백준]3176 도로 네트워크
N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오
Lowest Common Ancestor (LCA)
Tree에서 u, v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다. 그렇다면 어떻게 LCA를 구할 수 있을까? Method 1 Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다. root에서 u, v까지의 경로를
3176. 도로 네트워크
시간 제한: 1초메모리 제한: 256MB먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이
15480. LCA와 쿼리
시간 제한: 2초메모리 제한: 512MBroot가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능 하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 1을 root로
1761. 정점들의 거리
시간 제한: 2초메모리 제한: 128MB두 정점을 잇는 경로를 찾아내야 한다. 이때, 두 정점을 잇는 최상단 node인 Lowest common ancestor(LCA)를 찾으면 경로를 쉽게 이을 수 있을 것이다.1번 node를 root로 하여, DFS를 진행하여 다음
백준 11438 LCA2
https://www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지