종신1재정2시경3

다들 다익스트라를 배우고 이해는 한다.

아~ 계속 간선 길이를 늘려가면서 점마다 우선순위큐로 dp를 찍어주면 되는구나~

이해는 하고 기초 문제를 풀고 나면 다익스트라를 다 아는 것 같은 착각이 든다 ㅎㅎ

근데 이제 다익스트라를 조금만 꽈서 낸 문제면 풀질 못한다 ㅜㅜ

어느 알고리즘이나 응용이 어렵지만, 내가 느끼기엔 다익스트라가 유독 까다롭더라.

그래서 이제부터 좀 다양한 다익스트라 문제들을 올리려고 한다.

이 글을 호오오오옥시 읽는 분들도 아는 문제가 있으면 추천을 부탁드립니다.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------

1) 백준 16118 달빛 여우

https://www.acmicpc.net/problem/16118

조금만 꽈서 낸 문젠데 세 번이나 틀리고 맞았다 ^^

여우의 경우 1번 정점부터 나머지 정점까지 최소경로의 길이는 순수 다익스트라로 구할 수 있다.

늑대의 경우 내가 현재 정점에 오기전에 2배 빠르게 왔는지, 느리게 왔는지 기억해야 한다.

그래서 나는 구현을 쉽게 할려고(정말?), 간선을 2배로 뿔렸다. 즉 2배 빨라지는 길, 2배 느려지는 길을 추가했다.

그러면 전에 빨라지는 길로 왔었다면, 이번엔 느려지는 길로만 갈 수 있게 된다.

dp(fox, wolf)에는 빠르게 왔는지, 느리게 왔는지를 둘 다 기록했다.

2) bitonic path

scpc 2차 예선 문제였는데 링크를 찾고 있습니다 ㅜ

https://www.acmicpc.net/problem/15957

1. 트리

트리의 루트에 쿼리가 가해지면 자식들의 점수가 모두 더해진다.

-> 트리를 dfs 돌면서 번호를 매기면, 루트 노드 부터 자식들이 연속해서 들어있는 배열을 만들 수 있다. = 트리 순회 배열이라고 한단다.

2. 쿼리

트리 순회 배열에 쿼리가 가해진다.

이제 쿼리는 배열의 일부 구간을 증가시키는 쿼리가 된다.

-> 일부 구간을 빠르게 증가시키는 방법이 필요하다.

-> 증가시켰으면 값이 얼마인지도 빠르게 알아낼 방법이 필요하다. = 펜윅트리의 ( range update & point query ) 모드를 사용하자.

3. 펜윅 트리

이 자료구조는 다음 두 기능을 로그시간에 제공하는 자료구조다.

1) update(p, v) : p번째 원소를 v만큼 증가시킨다.

2) query(p) : 첫번째 원소부터 p번째 원소까지의 합을 알려준다.

즉 point update & range query를 로그시간에 수행한다.

이를 조금만 응용하면 range update & point query 모드로 바꿀 수 있다.

원래 배열을 a라고 하고, 배열 b[x] = a[x] - a[x - 1] 이라고 정의해보자.

그러면 이제 a의 입장에서, a[x]는 b[x] + b[x - 1] + ... 즉 누적합이 된다.

이제 두 기능을 b에 대고 수행한다고 생각해보자.

1) update(p, v)

-> 예를 들어 update(3, v)라면, a[1]과 a[2]는 가만히 있고, a[3]부터 v씩 늘어난 것이다. 왜냐하면 b의 정의 때문에.

따라서 [from, to] 구간을 v만큼 증가시키고 싶다면, update(from, v) 와 update(to + 1, v) 두 번으로 배열 a를 다 조질수 있다.

2) query(p)

-> b[1] + b[2] + ... + b[p] = a[p] 이니까, a의 p번째 원소 값을 구하는 쿼리로 변경되었다.

이처럼 펜윅트리는

1) point update & range query

2) range update & point query

3) range update & range query

총 3가지 모드를 제공한다. 3번째 모드는 차후에 설명하는 것으로.. ㅎㅎ

이제 트리에 가해지는 쿼리를, 펜윅트리에서 로그시간에 수행할 수 있게 되었다.

하지만

1) 모든 쿼리를 수행해보면서 매번 모든 가수가 평균 점수를 넘는지 확인

2) 모든 가수마다 쿼릐를 수행해보면서 언제 평균 점수를 넘는지 확인

어떤 방법으로도 N * K * log(N)으로 시간이 오바된다.

4. 시간 줄이기

포인트는 가수들의 평균점수는 쿼리들이 수행되는 동안 절대 내려가지 않는다는 점이다.

따라서 단조증가하고, 이는 이분 탐색을 떠올리게 해준다.

하지만 가수마다 이분 탐색으로 조지는 것 보다, 모든 가수들의 구간을 줄여나가는 방법이 있단다. -> 병렬 이분 탐색

이 알고리즘의 구조를 보면, 가수마다 구간이 있고 구간의 중앙값은 타겟이 된다.

이제 쿼리를 순차적으로 수행할 텐데, 현재 수행하는 쿼리가 타겟과 같다면 그 가수는 구간을 반으로 줄일 수 있다.

쿼리를 전부 수행하고 나서, 구간이 변화한 가수가 있다면, 다시 처음부터 쿼리를 수행하는 짓을 반복한다.

말로는 머가 개선된건지 모르겠지만, 나중에 코드로 보면 더 빠르겠구나 할 꺼다.

A를 6분에 풀고

B에서 너무 시간을 오래 잡아먹었다.

관찰결과, (x,y)에서 |x|==|y| 이거나 절대값 차이가 홀수냐 짝수냐에 따라 다 다르길래 마음만 급해서 구현실수하구....

C에서 너무 수학적으로 생각하느라 또 시간 소비.

D는 그나마 빨리 풀었다. 그리디하게 생각한게 적중.

다시 C로 돌아와서 허어ㅓㅓㅓㅓㅓ 하다가 끝나버렸다.

문제의 C문제는 

0이 아닌 자릿수가 3개 이하인 자연수 = Classy number 가 [L, R] 구간에 몇 개나 있는지 세는 문제였다.

조합으로 수식 세우고 구현하면 되기도 하지만, 나처럼 구현상의 실수를 할 수 있다.

그래서 미리 Classy number를 다 구해놓고, (10^18 이하에서) 이분탐색으로 구간 상의 개수를 세면 되는 문제였다고 한다. ㅎㅎ

솔직히 이런 유형의 문제를 처음봤다. 미리 다 구해노코 빠박하는게 좀 더 컴퓨터적인 사고인거 같은데,

수학적으로만 접근 한걸 보면 백준만 허구헌날 해서 그런가 싶기도 하고...