본문 바로가기

분류 전체보기

 (145)
백준 14180 - 배열의 특징 (C++) 문제 문제 링크 BOJ 14180 - 배열의 특징 문제 요약 배열의 특징이 $C = ΣAi·i (1 ≤ i ≤ n)$로 정의된다. 배열에서 수 하나를 아무 위치로 이동시킬 수 있을 때, 가능한 $C$의 최댓값을 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 200,000$ $|A_i| ≤ 1,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 누적 합(prefix_sum) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 임의의 인덱스 $i$를 기점으로 배열을 나눠 왼 쪽, 오른 쪽 인덱스로 이동한다고 생각해보자. 왼 쪽으로 이동 한다고 할 때. 이동 시 변화를 파악하기 위해 간단한 예를 하나 들겠다. 배열 $a_n$ = { $a_1, a_2, a..
백준 12795 - 반평면 땅따먹기 (C++) 문제 문제 링크 BOJ 12795 - 반평면 땅따먹기 문제 요약 $Li-Chao$ $Tree$ 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ Q ≤ 200,000$ $|a| ≤ 1,000,000$ $|b|, |x| ≤ 1,000,000,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 자료 구조(data structures) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 리차오 트리 그 자체인 문제다. 나는 jhnah917님의 글 에서 리차오 트리를 공부했는데, 되게 참신한 자료 구조라고 생각한다. 노드마다 직선의 방정식을 박을 줄이야.. 여튼 $f(x) = ax + b$의 형태에서 $a$와 $b$가 직접적으로 주어진다. 따라서, 동적 노드마다 절반 이상에서 ..
백준 21033 - Sending Blessings (C++) 문제 문제 링크 BOJ 21033 - Sending Blessings 문제 요약 $N$개의 정점과 이들을 잇는 $N$개의 간선이 주어진다. $Q$개의 쿼리에 대해 알맞는 답을 출력해보자. 제한 TL : $2$ sec, ML : $512$ MB $3 ≤ N ≤ 10^5$ $1 ≤ Q, C_i ≤ 10^5$ 알고리즘 분류 자료 구조(data structures) 트리(trees) 구현(implementation) 세그먼트 트리(segment tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse table) 풀이 $N$개의 간선으로 이루어진 그래프 즉, 사이클이 내포된 $Unicycle$ $Graph$ 에서 사이클을 분리하는 방법을 아는가? 이에 익숙치 않다면 다음 두 ..
백준 25430 - 다이제스타 (C++) 문제 문제 링크 BOJ 25430 - 다이제스타 문제 요약 $N$개의 정점으로 이루어진 그래프의 간선과 시작점, 도착점 정보가 주어진다. 항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 할 때, 운반을 완료하는 최소 이동 거리를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 50,000$ $1 ≤ M ≤ 100,000$ $1 ≤ E_i ≤ 10,000,000$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 자료 구조(data structures) 트리를 사용한 집합과 맵(tree _ set / map) 풀이 다익스트라 냄새가 물씬 나는 문제지만, 그동안 알고 있던 다익 문제들과 살짝 궤를 달리하는 신선한 문제다. 핵심은 문제에..
백준 27896 - 특별한 서빙 (C++) 문제 문제 링크 BOJ 27896 - 특별한 서빙 문제 요약 $N$명의 학생들의 불만도가 주어진다. $M$을 넘지 않도록 급식을 분배할 때 필요한 최소 가지의 개수를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 200,000$ $1 ≤ M ≤ 10^9$ $0 ≤ x_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 그리디 알고리즘(greedy) 우선순위 큐(priority_queue) 풀이 우선 보면 주어진 순서를 유지해야 한다고 한다. 그렇다면 일단 파묻튀를 먹이다가, 불만도의 합이 $M$ 을 넘는 순간이 온다면 그동안의 $x_i$ 중 가장 큰 녀석에게 가지를 주는 것이 이득이지 않겠는가? 이러한 상황에 더없이 편한 녀석이 우선순위 큐다. 이..
백준 23354 - 군탈체포조 (C++) 문제 문제 링크 BOJ 23354 - 군탈체포조 문제 요약 격자의 정보가 주어진다. 탈영병을 모두 잡고 부대로 복귀하는 최소 비용을 구해보자. 제한 TL : $3$ sec, ML : $512$ MB $5 ≤ N ≤ 1,000 $1 ≤ N_{i,j} ≤ 1,000$ 탈영병의 수는 $5$ 이하 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 브루트포스 알고리즘(bruteforcing) 풀이 탈영병의 수만큼 다익스트라를 돌려 임의의 탈영병 위치에서 다른 탈영병 위치로의 최단 거리를 모두 구해주자. 그럼 답은 (탈영병을 최소로 순회하는 비용) + (첫번째 탈영병과 부대와의 거리) + (마지막 탈영병과 부대와의 거리) 이 된다. 탈영병의 수가 $5$로 굉장히 작아 모든 경우를 돌려보면 된다...
백준 16302 - Jurassic Jigsaw (C++) 문제 문제 링크 BOJ 16302 - Jurassic Jigsaw 문제 요약 mst 역추적 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 1,000$ $1 ≤ k ≤ 10$ 알고리즘 분류 그래프 이론(graphs) 최소 스패닝 트리(mst) 풀이 그냥 기본 mst 문제다. 임의의 문자열 쌍마다 서로 다른 문자 수 만큼 가중치를 메긴 뒤 mst를 돌려주면 된다. 전체 코드 123456789101112131415161718192021222324252627282930313233343536373839404142#includeusing namespace std; struct E{ int x, y, w; bool operator n >> k; for (vector V(n); n--; i++..
백준 1823 - 수확 (C++) 문제 문제 링크 BOJ 1823 - 수확 문제 요약 $N$개의 벼와 그 가치가 주어진다. 문제에 정의된 규칙대로 벼를 수확할 때 얻을 수 있는 최대 이익을 구해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 2,000$ $1 ≤ N_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 결국 양 끝 점에서만 상태가 변화 한다는 것에 주목하면 이미 문제를 푼 것이나 다름 없다. 다음과 같이 점화식을 정의하자. $dp[p][q]$ : 현재 구간 $[p, q]$를 보고 있을 때 얻을 수 있는 최대 이익. 만약 왼 쪽 점을 취한다면 $a[p] * (n - (q - p))$ 의 이득이 발생하고, 오른 쪽 점을 취한다면 $a[q] * (n - (q - p))$ 의 이득이 발..

티스토리툴바