SegmentTree Dot Algo∙ DS/PS 2021. 8. 17. [BOJ] 백준 1275 커피숍2 (Java) #1275 커피숍2 난이도 : 골드 1 유형 : 자료 구조 / 세그먼트 트리 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net ▸ 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느 날 커피숍의 손님 A씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도.. Dot Algo∙ DS/알고리즘 개념 2021. 8. 4. [알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java) 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a,b의 최소 공통 조상을 찾는 알고리즘이다. 예를들어 아래의 트리에서 5번과 6번노드의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장해준다. LCA를 구하기 위한 a,b번 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다 (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게되면 엄청나게 많은 반복을 돌려.. 이전 1 다음
![[BOJ] 백준 1275 커피숍2 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bv7atk/btrcgOIhh7U/yZt4uwKZkQ57ohgkuPttqk/img.png)
![[알고리즘] 최소 공통 조상 LCA 트리 - DP & 세그먼트 트리 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bfTER3/btra33TUw28/JOW83oaGdTLVeKAwuML2VK/img.png)