dh_0e

교수님은 기다리지 않는다 (백준 3830번) 분리 집합을 떠올리는데는 큰 어려움은 없었지만 가중치 관리하는 수식을 세우기가 조금 힘들었던 문제 풀이 과정 분리 집합 알고리즘을 구현한 뒤 경로 압축을 해준다(find_root() 함수). _union() 함수에 알맞은 수식을 넣어 가중치를 갱신하게끔 하면 된다. find_root(node): node의 최종 root를 찾은 뒤, 경로 압축으로 최적화 실행_union(a, b, w): a에서 b로 가는 가중치가 w라고 했을 때, a의 최종 root(pa_a)와 b의 최종 root(pa_b)를 각각 구하여 가중치를 갱신parent[pa_a.first] = pa_b.first; // a의 최종 root(pa_a.first)의 최종 root(parent[pa_a...

컨닝 (백준 1014번) dfs로 풀면 시간 초과 이므로, 다른 풀이를 떠올려야 하는데 그 부분이 너무 막막했던 문제. 풀이과정 비트필드를 이용한 dp로 풀면 된다.m(가로) 길이에 맞게 자리에 앉을 수 있는 모든 경우의 수를 비트 마스크로 생성한다.{0, 1}, {0, 1, 10}, {0, 1, 10, 100, 101}, {0, 1, 10, 100, 101, 1000, 1001, 1010}과 같이 피포나치 수열로 증가세를 띄며, 가로 길이가 최대인 10일 경우 144가지 경우의 수가 있다.이를 b_mask에 저장하고 점화식을 'dp[i][j]=i번째 줄에서 b_mask[j]의 비트 값으로 앉을 때, 최대로 앉을 수 있는 인원'으로 세운다.첫 줄의 dp 값은 b_mask의 1의 개수로 저장한다.두 번째 ..

콘서트 (백준 34056번) UCPC 예선 E번 문제로 느린 세그먼트 트리로 풀어야할 것 같은데 남은 시간 안에 구현할 엄두가 안 났던 문제. 풀고 나서야 O(NQ)는 절대 시간초과라는 편견을 안 하게 되었던 교훈적인 문제였다. 풀이과정놀랍게도 N, Q가 200,000이지만 $O(NQ)$만에 해결이 가능하다. 방음벽이 소음을 모두 흡수하지 못하면 방음벽의 성능이 2배가 된다. 하지만 소음의 최대 크기가 $10^9$이기 때문에, 어림잡아 $2^{30}$ 이하라는 소린데 이는 한 방음벽이 30번 정도만 흡수를 못 해도 이후엔 모든 소음을 흡수할 수 있게 된다는 소리이다. Q가 200,000이라 평균적으로 탐색 로직이 500번 이하로 나오면 시간안에 Ac가 나올 수 있는데, 이 문제에선 평균 탐색 길이가 지수..

연산 추가하기 (백준 34055번) UCPC 예선에서 팀원이 푼 문제로 당시 팀원이 설명한 발상을 그대로 가져갔고, 마지막에 누적합, 이진 탐색 처리식을 다르게 풀었다. 풀이 과정각 구간들을 제외한, 연산이 추가될 수 있는 연속된 사이클 수를 모두 구해놓고 이를 정렬한 뒤, 누적합을 구해놓는다. 예제 1을 예로 들면 연산이 추가될 수 있는 부분은 (1~4), (9~11), (24~30) 3구간이며 각각 4, 3, 7 사이클이다. 이를 정렬한 뒤, 누적합을 구하면 3, 7, 14가 된다. 각 시나리오에 대한 정답은 정렬한 배열에서 이분 탐색으로 Qi 이상의 값이 처음 나오는 index를 구해서(lower_bound) 다음 식을 사용하면 구할 수 있다. cy[i]: 구간별 연속된 사이클들을 정렬한 배열v[i..

로봇 청소기 (백준 34060번) UCPC 예선에서 발상을 잘못해서 다 구현해놓고 실수로 분리 집합을 빼먹어서 시간 내에 풀지 못했던 문제.대회 끝나고 처음부터 다시 풀어보는데 union-find를 함수 없이 구현해보려다 몇 번 틀렸다. 풀이 과정 오염 영역의 최댓값은 n이 200,000까지이고 격자의 크기가 $10^9$x$10^9$이기 때문에 n값을 그대로 출력해주면 되며, 오염 영역의 최솟값만 구하면 되는 문제이다. 최솟값을 구하는 로직을 greedy하게 생각하면, d[i]가 d[i-1]보다 크다면 다음 줄로 넘기지 않고, d[i-1]보다 작거나 같을 때만 다음 줄로 넘기게끔 하면 항상 오염 영역을 가장 많이 줄일 수 있다. prevQue: 이전 줄의 index들 저장하는 QueuerecQue: 현..

1의 개수 세기 (백준 9527번) A, B가 $10^{16}$까지 이므로 $O(logn)$에 해결해야 한다.$O(n)$은 무조건 시간초과. 풀이 과정2진수에 나타나는 1의 개수를 구해보면 패턴을 찾을 수 있다.1{1}, 2~3{1, 2}, 4~7{1, 2, 2, 3}, 8~15{1, 2, 2, 3, 2, 3, 3, 4} 까지만 봐도 패턴이 보인다.d[i] = $2^i$ ~ $2^{i+1}-1$에서 1의 개수라고 했을 때 점화식은 $d[i]=d[i-1]*2+2^{i-1}$로 구할 수 있으며 이를 각 구역으로 봤을 때, 각 구역별로 절반씩 나눠보면 똑같은 패턴인 것이 확인된다.8~15{1, 2, 2, 3, 2, 3, 3, 4}를 반으로 나누면 8~11{1, 2, 2, 3}, 12~15{2, 3, 3, 4}..