https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 수 하나를 집어넣고 median값을 물어보는 query가 있을 때, 100000번의 query를 어떻게 0.1s(1e7번 내외의 iteration) 안에 처리할 것인가 하는 문제이다. query의 개수를 $N$이라고 하고$(N \leq 100000)$, 정수의 범위를 $M$이라고 하자. $(M \leq 20000)$ 처음에 떠올릴 수 있는 방법은 linked list로 수를 집어넣..

• segment tree with lazy propagation algorithm의 필요성segment tree는 구간에 대한 query를 O(logN)에 수행할 수 있도록 한다. 한 index에 대한 update를 수행할 경우에 update의 time complexity는 역시 recursive call에 의해서 O(logN)에 수행된다. 만약 한 index가 아니라 구간 [L, R]에 대한 update를 수행할 경우 [L, R]에 속한 모든 index에 대하여 update를 해 주어야 하므로 O((R-L+1)logN), 일반적으로 쓰면 O(NlogN)의 긴 수행 시간이 필요하게 된다. 이를 해결하기 위해서는 일종의 optimization이 필요한데, 이것이 바로 lazy propagation이다. ..

2013년도 KOI 도대회 고등부 3번 문제이다. 간단한 segment tree 문제처럼 보였는데, TLE를 3번 받았다. 해법은 간단하다. 1행의 케이블의 번호를 1, 2, 3, 4, 5의 오름차순으로 정렬하고, 2행의 케이블의 번호를 이에 맞게 다시 부여해준다. 그러면 예제의 경우 2, 4, 1, 3, 5가 되는데, 교차는 한 기계에서 그 앞에 자신보다 큰 숫자가 있을 경우에 발생한다. 예제의 경우를 보자. 2의 경우 교차는 0이다. 4의 경우도 교차가 0이고, 1의 경우 앞에 2와 4가 있으므로 교차가 2번 발생하고, 3의 경우는 4로 인해서 한 번, 5는 발생하지 않는다. 따라서 교차횟수는 총 3회이다. 따라서 https://jordano-jackson.tistory.com/33에서 다루었던 BO..

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 2012년도 정올 고등부 2번 문제다. segment tree와 좌표압축을 사용하면 된다. 실력을 기준으로 segment tree를 만들면 특정 실력의 선수를 확인할 때 O(logN)만에 최대 등수를 확인할 수 있다는 아이디어를 얻을 수 있다. 여기서 중요한 점은 앞에서부터 차례로 update를 해 주고 query를 처리하여서 i번째 선수까지만 tree에 반영이 될 수 있도록 하는 것이다. ..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net segment tree 개념 문제이다. 입력과 출력도 int 범위 내이고, update도 없으므로 크게 어려운 것 없는 문제이다. 다만 최솟값이라는 특성 상 initializing을 할 때 min(init(범위1), init(범위2)) 로 tree 값을 정해주고, query가 주어졌을 때에도 min(query(범위1), query(범위2))와 같은 형식으로 리턴..