문제 https://www.acmicpc.net/problem/2934 2934번: LRH 식물 상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 느리게 갱신되는 세그먼트 트리로 풀 수 있는 문제이지만 원소를 다르게 표현하는 펜윅 트리로도 해결할 수 있다. 문제에서 식물의 높이는 항상 이전의 식물들보다 크다. 따라서 이전의 식물들의 구평 선분과 현재 식물의 수직 선분과의 교차점이 꽃이 피는 개수이다. 수평 선분을 구간이라고 생각해보자. 트리에서 해당 구간의 값들을 모두..

Fenwick Tree 펜윅 트리 기존의 펜윅 트리에 대해서는 깔끔하게 설명하신 백준님의 게시글을 보고 오자. 펜윅 트리 (바이너리 인덱스 트리) - BaekJoon 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는데 특화되었다.(이 특징이 가장 중요합니다!!!) 백준 님이 설명한 펜윅 트리에서는 점 업데이트(Point Update)와 구간 쿼리(Range query)가 가능하다. 따라서 [L,R]구간의 구간합은 [1,R]까지의 합(pSum(R) ) - [1,L-1]까지의 합( pSum(L-1) )으로 구할 수 있다. 하지만 원소의 업데이트는 한 개씩만 진행할 수 있다. 따라서 백준 - 수열과 쿼리 21(16975) 문제와 같은 구간의 업데이트를 요구하는 문제는 일일..

문제 https://www.algospot.com/judge/problem/read/MEASURETIME algospot.com :: MEASURETIME 삽입 정렬 시간 재기 문제 정보 문제 유명한 정렬 알고리즘인 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해 나가는 식으로 동작합니다. 주어진 정수 배열 A를 정렬하는 www.algospot.com 풀이 종만북 난이도: 중 세그먼트 트리와 같은 기능을 하지만 비트 연산을 이용해 좀 더 간단히 구현이 가능한 펜윅 트리(Fenwick Tree) 혹은 이진 인덱스 트리(binary indexed tree)로 해결하는 문제이다. 펜윅 트리는 세그먼트 트리와는 다르게 부분 합(첫 원소에서 부터 i개의 값)을 계산하는 데 특화되어 있다. 만..

문제 https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 세그먼트 트리에서 특정 구간의 값들이 자주 변경되어야 할 때 사용되는 Segment Tree Lazy Propagation(느리게 갱신되는 세그먼트 트리) 문제이다. Segment Tree Lazy Propagation에 대해서는 깔끔히 설명해주신 백준님의 게시글을 보고 오자. 세그먼트 트리 나중에 업데..

문제 https://algospot.com/judge/problem/read/FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 algospot.com 풀이 종만북 난이도: 상 최소 공통 조상(Lowest Common Ancestor, LCA)를 세그먼트 트리로 풀어보는 문제이다. LCA의 구현에는 단순한 구현과 최적화를 거친 구현이 존재한다. 단순 구현: 백준 - LCA(11437) - Gold 3 최적화 구현: 백준 - LCA 2(11438)★ - Platium 5 하지만 이번에는 세그먼트 트리를 이..

문제 https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 Inversion Counting 문제를 세그먼트 트리를 이용해 해결하는 문제. 해결법은 다음과 같다. 한 기계의 쌍의 A라인의 위치를 a_idx, B라인에서의 위치를 b_idx라고하자. 이 기계의 케이블과 교차되기 위해서는 해당 기계의 A라인에서의 위치(a_new)가 a_idx보다 앞에 있고 B라인에서의 위치(b_new)가 b_idx보다..

문제 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 풀이 solved.ac 난이도: Gold 1 세그먼트 트리(구간 트리)를 이용해야 제한시간 안에 풀 수 있는 문제. 세그먼트 트리를 모른다면 간단한 풀이로는 이해하기 힘드므로 백준님의 깔끔한 설명을 보고 오자. 세그먼트 트리 (Segment Tree) - Baekjoon Online Judge 세그먼트 트리는 이름처럼 노드마다 자..

문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 입력을 정렬한 후 우선순위 큐를 이용하여 처음부터 끝까지 스위핑하여 해결할 수 있는 문제. 일단 입력의 집과 사무실의 위치를 pair arr[100000] 에 저장한다. 어느 쪽이 집이고 사무실 인지는 철로에 영향이 없기 때문에 pair의 first에 더 작은 위치(선의 시작점)를 저장하자. 이제..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 백준 - 소수의 곱(2014) - Gold 2 백준 - 가운데를 말해요(1655)★ - Gold 3 백준 - 철로(13334)★ - Gold 2 백준 - 쇼핑몰(17612) - Gold 1

문제 https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 각 계산대에 줄을 세우는 우선순위 큐와 계산을 끝내고 빠져나오는 순서를 저장하는 우선순위 큐의 정렬 순서가 중요한 문제이다. 각 계산대에 줄을 세우는 우선순위 큐를 생각해보자. 고객들은 계산대의 대기 시간이 가장 작은 곳에 줄을 서고, 만약 대기 시간이 같은 계산대가 여러 개라면 번호가 작은 계산대에 줄을 선다. 따..