# LCA

53개의 포스트

[BOJ]11437 - LCA (G3)

11437-LCA

2023년 2월 27일
·
0개의 댓글
·
post-thumbnail

BOJ 11437 : LCA

BOJ 11437 : LCA

2023년 2월 10일
·
0개의 댓글
·

SWEA 1855 영준이의 진짜 BFS

SWEA 1855 <-클릭LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다.아이디어를 간단하게 요약하면 다음과 같다 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 d

2023년 2월 2일
·
0개의 댓글
·
post-thumbnail

가장 가까운 공통 조상 3584

깊이를 맞추어주고 같이 올라가다보면 같은 값이 나오는 구간이 있다. 그것이 최소 공통 조상이다.더 깊은 곳을 찾아낸 뒤 깊이를 얕은 곳과 맞추어준다. 그 후 같이 올라가다 보면 값이 같아지는데 그것은 조상이 같다는 의미이다.다른 풀이가 있나 해서 찾아보니 한쪽에서 끝까

2023년 1월 29일
·
0개의 댓글
·
post-thumbnail

[ 백준 / Python3 ][골드3] 11437 - LCA

https://www.acmicpc.net/problem/11437LCA 알고리즘을 사용하기 위해서는 노드마다 깊이와 부모노드가 정해져 있어야 한다.하지만 이 문제에서는 루트노드가 1인 그래프로 주어졌기 때문에 루트노드가 1이라는 것 하나로 트리의 구조를 파악

2023년 1월 22일
·
0개의 댓글
·
post-thumbnail

[ SWEA / Python3 ] 1855 - 영준이의 진짜 bfs

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc

2023년 1월 22일
·
0개의 댓글
·
post-thumbnail

[알고리즘] LCA 응용 - 세그먼트트리, DP (Java)

[알고리즘] LCA 응용 - 세그먼트트리, DP (Java)

2022년 12월 28일
·
0개의 댓글
·
post-thumbnail

최소 공통조상 알고리즘

너무 어려웠음. lca

2022년 12월 19일
·
0개의 댓글
·

Leetcode - 1644. Lowest Common Ancestor of a Binary Tree II

기본적으로 236. Lowest Common Ancestor of a Binary Tree 와 코드는 동일. 하지만 q, p노드를 실제로 방문했는지 체크했는지 여부 추가. 따라서 모든 노드를 방문해야함. 그래서 아래 (1) 코드는 양쪽 자식노드 재귀 호출을 마친 이후

2022년 11월 25일
·
0개의 댓글
·

Leetcode - 235. Lowest Common Ancestor of a Binary Search Tree

주어진 Binary Search Tree 에서 두 노드의 가장 가까운 공통 부모 (LCA)를 찾아라.현재 노드의 값이 p, q보다 작다면 LCA는 우측 자식노드에 존재. 이를 재귀적으로 반복.종료조건(base case) 현재 노드 값이 p, q보다 작지도 않고, p,

2022년 11월 25일
·
0개의 댓글
·

Leetcode - 236. Lowest Common Ancestor of a Binary Tree

binary tree에서 두 노드의 가장 가까운 공통 부모를 찾아라. 재귀함수는 자식노드에 q, p노드가 존재하면 해당 노드를 리턴, 아니라면 NULL리턴. left, right에 노드가 NULL인지 아닌지로 현재 노드가 LCA인지 아닌지 판단 가능.재귀 호출 이후 논

2022년 11월 25일
·
0개의 댓글
·

[CS 공부] 22.10.05

MSD(Most-Significant Digit) 가 아닌 LSD(Least-Significant Digit) 부터 비교해야함 찾는 방법두 정점에 대해 루트 노드 부터 본인의 부모까지 정점을 각각 리스트로 저장한다.리스트에서 정점을 하나씩 꺼내서 같은 지 확인한다.(리

2022년 10월 5일
·
0개의 댓글
·
post-thumbnail

백준 2233 사과나무

문제 풀이 두 썩은 사과를 잘라내기 위해 가지를 잘라내되, 떨어지는 사과의 개수를 최소로 한다는 것은 두 썩은 사과의 최소 공통 조상을 찾아내라는 의미이다. 즉, LCA 알고리즘을 적용시키면 된다. 단, 이 문제에서는 문자열을 가지고 Tree를 생성하는 과정을 요구하고 있다. Tree 생성 1) 스택 사용 0인 경우 level이 더 높아지고, 1인 ...

2022년 9월 12일
·
0개의 댓글
·
post-thumbnail

<Baekjoon> #3584_LCA, DFS 가장 가까운 공통 조상 java

\[BOJ 참고로 이 문제도 예전에 C++로 풀었는데 그땐 Heap으로 풀었었다. 하지만 문제에서 의도한 알고리즘은 아닌 것 같아서 JAVA 문법 익힐 겸 다른 풀이를 참고하며 풀었다. (JAVA로 알고리즘 푸는 거 고역이다..) 문제 제목에서도 주어진대로 가장 가까운

2022년 7월 17일
·
0개의 댓글
·
post-thumbnail

[백준]3176 도로 네트워크

N개의 도시가 N-1개의 간선으로 두 도시간 경로가 유일하게 연결되어있다. 두 도시쌍이 여러개 들어올 때 두 도시를 연결하는 도로중 가장 긴 도로와 가장 짧은 도로를 구하시오

2022년 4월 18일
·
0개의 댓글
·

Lowest Common Ancestor (LCA)

Tree에서 u, v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다. 그렇다면 어떻게 LCA를 구할 수 있을까? Method 1 Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다. root에서 u, v까지의 경로를

2022년 4월 15일
·
0개의 댓글
·

3176. 도로 네트워크

시간 제한: 1초메모리 제한: 256MB먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이

2022년 4월 13일
·
0개의 댓글
·

15480. LCA와 쿼리

시간 제한: 2초메모리 제한: 512MBroot가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능 하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 1을 root로

2022년 4월 12일
·
0개의 댓글
·

1761. 정점들의 거리

시간 제한: 2초메모리 제한: 128MB두 정점을 잇는 경로를 찾아내야 한다. 이때, 두 정점을 잇는 최상단 node인 Lowest common ancestor(LCA)를 찾으면 경로를 쉽게 이을 수 있을 것이다.1번 node를 root로 하여, DFS를 진행하여 다음

2022년 4월 11일
·
0개의 댓글
·

백준 11438 LCA2

https&#x3A;//www.acmicpc.net/problem/11438LCA는 Lowest Common Ancestor로 최소공통조상을 찾는 알고리즘이다. 두 노드의 최소공통조상을 찾는 방법은1\. 두 노드의 높이를 맞춘다.2\. 노드를 올려보면서 부모가 같은지

2022년 4월 6일
·
0개의 댓글
·