본문 바로가기

Problem Solving

 (145)
백준 17429 - 국제 메시 기구 (C++) 문제 문제 링크 BOJ 17429 - 국제 메시 기구 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 처리를 진행하자. 제한 TL : $3$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ Q ≤ 100,000$ 모든 출력에 있어서 $2^{32}$로 나눈 나머지 값을 출력 한다. 알고리즘 분류 자료구조(data structures) 트리(trees) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) heavy-light 분할(heavy-light decomposition) 오일러 경로 테크닉(euler_tour_technique) 풀이 이 문제 를 풀어 보았는가 ? 이번 문제는 위 ..
백준 20501 - Facebook (C++) 문제 문제 링크 BOJ 20501 - Facebook 문제 요약 $N$명의 친구 관계 정보가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 답을 출력하자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 2,000$ $1 ≤ Q ≤ 500,000$ 알고리즘 분류 비트 집합(bit set) 비트마스킹(bitmask) 풀이 $B[2000][2000]$의 배열에 담아 쿼리 당 $N$번의 연산을 수행하면 $O(NQ)$로 시간 초과를 피할 수 없다. 친구 관계를 이진수로 간단히 표현할 수 있으므로 $B[2000][⌈2000 / 64⌉]$를 가지고 mask로 처리하면 $O(NQ / 64)$ 의 복잡도로 해결할 수 있다. 아래 코드는 직접 mask로 구현한 것과 C++ STL의 bitset 을..
백준 13701 - 중복 제거 (C++) 문제 문제 링크 BOJ 13701 - 중복 제거 문제 요약 $N$개의 수가 주어진다. 이들 중 반복되는 수를 제외하고 남은 수들을 모두 출력해보자. 제한 TL : $5$ sec, ML : $8$ MB $1 ≤ N ≤ 5,000,000$ $0 ≤ A_i < 2^{25}$ 알고리즘 분류 비트 집합(bit set) 비트 마스킹(bitmask) 풀이 메모리 제한과, 주어지는 수의 개수 및 범위가 아주 인상적인 문제이다. $⌈5,000,000 / 64⌉$ 개의 long long 변수를 가지고 mask를 해도 좋지만, C++ STL의 bitset을 이용하면 더욱 간단히 처리할 수 있다. 자세한 정보는 아래를 링크를 참고하자. std::bitset 전체 코드 1234567891011#includeusing names..
백준 12970 - AB (C++) 문제 문제 링크 BOJ 12970 - AB 문제 요약 정수 $N$과 $K$가 주어진다. 문제에 정의된 두 조건을 만족하는 문자열 $S$를 찾아보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 50$ $0 ≤ K ≤ N(N-1)/2$ 알고리즘 분류 수학(math) 그리디 알고리즘(greedy) 구성적(constructive) 풀이 나는 우선 $A$로만 이루어진 길이 $N$의 문자열을 시작으로 잡았다. 이후 다음 두 값을 비교해 최솟값을 찾아 문자열을 맞춰 나갔다. $B$가 가장 처음 등장하기 전 인덱스.(맨 처음엔 당연히 맨 끝) 남은 $K$와 $B$ 가 가장 처음 등장한 인덱스로부터 맨 끝까지 등장하는 '$B$'의 개수의 합 두번째 값을 저렇게 추린 이유는, 기존 $A$를 $..
백준 13519 - 트리와 쿼리 10 (C++) 문제 문제 링크 BOJ 13519 - 트리와 쿼리 10 문제 요약 금광 세그를 선형 구조가 아닌 트리 위에서 한다면? 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 100,000$ $w_i ≤ |10,000|$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) 풀이 여기 서 다룬 문제에서 이미 대차게 얻어 맞았었기 때문에 , 사실상 복기하는 느낌으로 코드를 작성했다. 풀이는 저기서 다룬 내용과 99% 동일하니 간략하게 차이점만 짚고 넘어 가겠다. 그나..
백준 17526 - Star Trek (C++) 문제 문제 링크 BOJ 17526 - Star Trek 문제 요약 1에서 $n$으로 이동하려고 한다. 문제에 정의된 비용을 따를 때, 가장 최소의 비용으로 이동하는 경우를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $3 ≤ n ≤ 100,000$ $1 ≤ s ≤ 100,000$ $0 ≤ p ≤ 1,000,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 누적 합(prefix sum) 풀이 임의의 지점으로 가는 데엔 결국 그 이전 지점들 중에 어디에서 환승하냐가 관건이다. 두 지점 간 거리를 빠르게 계산하기 위해 누적 합( $p[]$ )을 이용하자. 이후, 간단하게 점화식을 만들어 볼 수 있다. $dp[i]$ : $..
백준 6171 - 땅따먹기 (C++) 문제 문제 링크 BOJ 6171 - 땅따먹기 문제 요약 $N$개의 땅의 $W_i, H_i$가 주어진다. 문제에 정의된 구매 규칙을 따를 때, 모든 땅을 사는 최소 비용을 구해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 50,000$ $1 ≤ W_i, H_i ≤ 1,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 문제의 규칙을 따르면 임의의 부분 집합 땅(k개)을 살 때 $max(W_1, W_2, ... W_k) * max(H_1, H_2, ... H_k)$ 의 비용이 발생 한다고 한다. 이는 결국 부분 집합에서 $W_1 >= W_2$ && $H_1 ≥ H_2$ 이면 2번 땅은 애초에 고려될 필요가..
백준 15249 - Building Bridges (C++) 문제 문제 링크 BOJ 15249 - Building Bridges 문제 요약 $1$에서 $n$을 잇는 다리를 지어보려 한다. 문제의 비용 발생 정의를 따를 때, 최소로 연결하는 비용을 구해보자. 제한 TL : $3$ sec, ML : $128$ MB $2 ≤ n ≤ 10^5$ $0 ≤ h_i ≤ 10^6$ $0 ≤ |w_i| ≤ 10^6$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 결국 임의의 위치 $i$까지 다리를 지으려면 $1$에서 바로 짓냐, $1$에서 중간 지점 $j$를 거치고 $j$에서 오냐 로 구분해 볼 수 있다. (단, $j$까지의 최소 비용이 계산 됐다는 가정 하에.) $j$ ~ $i$에 존재하는 기둥들의 $Σw$ 만큼 비용..

티스토리툴바