백준 | 11438번. LCA 2 - 최소 공통 조상 문풀
⬛ 백준 11438번. LCA 2 - 최소공통조상 문풀 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 11437번. LCA 1 - 최소 공통 조상 문풀
⬛ 백준 11437번. LCA 1 - 최소 공통 조상 문풀 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 11505번. 구간 곱 구하기 - 세그먼트 트리 문풀
⬛ 백준 11505번. 구간 곱 구하기 - 세그먼트 트리 문풀 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다...
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀
⬛ 백준 10868번. 최솟값 찾기 2 - 세그먼트 트리 문풀 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
백준 | 2042번. 구간합 구하기 3 - 세그먼트 트리 문풀
⬛ 백준 2042번. 구간합 구하기 3 - 세그먼트 트리 문풀 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 ..
- 코딩 테스트 [준비]/[문풀] Baekjoon_백준 문풀_조지기
- · 2024. 2. 14.
![트리(Tree) | 세그먼트 트리 Segment Tree (알고리즘) 정리](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/GeYSC/btsETjyKfYw/xYKxpoVWxefeXeALkAfDak/img.png)
트리(Tree) | 세그먼트 트리 Segment Tree (알고리즘) 정리
세그먼트 트리 (Segment Tree) | 인덱스 트리 (Index Tree) 세그먼트 트리 주어진 데이터들의 (구간 합) (데이터 업데이트) 가 함께 일어나거나, (최대, 최소) 를 구할 때 빠르게 수행하도록 고안해낸 자료구조이다. → 더 큰 범위를 ‘인덱스 트리’ 라고 말하기도 한다. [1] 세그먼트 핵심 1) 데이터 초기화하기 a) tree 배열 크기 선언 b) 단말 노드에 arr 원본 배열 초기화 c) setTree로 단말노드 위의 부모노드들을 자식 노드 활용해 세팅 2) 질의값 계산하기 | 구간합, 구간 곱, (구간 안의 최소값, 최대값), 데이터 갱신 등의 질의 질의는 보통 여러 가지가 있는데, 구간 합부터 들어보겠다. 질의값 계산 시에는 원본 idx를 트리의 idx로 맞춰주는 게 중요하다...
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 14.
![트리(Tree) | 트리, 트라이, 이진트리 비교](http://i1.daumcdn.net/thumb/C120x120/?fname=https://blog.kakaocdn.net/dn/1kt3d/btsEHHGmAlq/8Y47vcSdqKcLZS7EykENQ0/img.png)
트리(Tree) | 트리, 트라이, 이진트리 비교
코딩테스트에서의 Tree 문제 분류 1) 그래프로 푸는 Tree 트리도 특수한 그래프 형태의 하나이기 때문에 노드, 간선 정보가 주어질 수 있다. 이 경우, 인접리스트 형태로 트리를 표현하고, 그에 맞는 그래프 처리 (ex. DFS/BFS) 풀이 2) Tree 만을 위한 문제 보통 1차원 배열로 트리를 표현한다. 이진트리, 세그먼트 트리, LCA(최소 공통 조상) 1. 트리 (Tree) (1) 트리 Tree : 노드-에지로 연결된 그래프의 특수한 형태 (2) 특징 사이클 X, 루트 노드 1개 루트노드 제외한 모든 노드들은 단 1개의 부모 노드만 갖는다. 트리의 부분 트리(=서브트리) 역시 같은 특징을 따른다. (3) 트리의 구성 요소 2. 트라이 (Trie) (1) 트라이 (Trie) ; 문자열 검색 빠..
- 코딩 테스트 [준비]/[개념] 알고리즘 추가 정리 _ 2024
- · 2024. 2. 9.