pill27211의 티스토리 포스트 목록: 1 페이지

pill27211의 등록된 링크

키자드에 등록된 총 60개의 포스트를 확인하실 수 있습니다.

Tistory

백준 11412 - Tree of Almost Clean Money (C++)

문제 문제 링크 BOJ 11412 - Tree of Almost Clean Money 문제 요약 $N$개의 정점으로 이루어진 트리의 정보가 주어진다. 문제에 정의된 $x(i), y(i)$ 를 이용해 $Q$개의 쿼리에 대한 처리를 진행하자. 제한 TL : $4$ sec, ML : $256$ MB $1 ≤ N ≤ 500,000$ $1 ≤ Q ≤ 50,000$ $1 ≤ K ≤ 1,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 풀이 이런 모양의 쿼리를 처음 접하기도 하고 영어 이슈 때문에 문제 이해 하는 게 제일 관건이었던 것 같다. 막상 문제를 이해하고 나면 별..

원문보기 내부링크

Tistory

백준 1626 - 두 번째로 작은 스패닝 트리 (C++)

문제 문제 링크 BOJ 1626 - 두 번째로 작은 스패닝 트리 문제 요약 $V$개의 정점으로 이루어진 무향 그래프가 주어진다. 이 그래프의 '두 번째로 작은 스패닝 트리'를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ V ≤ 50,000$ $1 ≤ E ≤ 200,000$ $0 ≤ E_w ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 트리(trees) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse table) 풀이 이 문제 를 풀어 보았는가 ? 비슷하면서, 다르기도 하다. 위 문제는 $LCA$ $with$ $Sparse$ $T..

원문보기 내부링크

Tistory

백준 27501 - RGB트리 (C++)

문제 문제 링크 BOJ 27501 - RGB트리 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 인접한 정점 간 색이 겹치지 않도록 $3$가지 색을 이용해 칠할 때, 구할 수 있는 합의 최댓값과 그 과정을 구해보자. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ r_i, g_i, b_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 문제 유형 자체는 아주 친숙한 유형이다. 단지 트리 위에서 진행할 뿐이다. 임의의 정점이 가질 수 있는 상태는 결국 $3$가지 중 하나가 될테니, 다음과 같이 점화식을 정의해보자. $dp[p][q] : $ $p$번 정점을 루트로 하는..

원문보기 내부링크

Tistory

백준 25462 - Inverzije (C++)

문제 문제 링크 BOJ 25462 - Inverzije 문제 요약 길이 $N$인 수열과 $Q$개의 구간 쿼리가 주어진다. 각 쿼리에 맞는 답을 출력하자. 제한 TL : $4$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ a_i, b_i, P_i ≤ N$ 알고리즘 분류 자료 구조(data structures) 세그먼트 트리(segment tree) 오프라인 쿼리(offline_queries) mo's(mo's algorithm) 풀이 수쿼 $23$ 을 풀어 봤다면 보자마자 솔루션이 떠올랐을 것이다. 쿼리 내용 보자. $Q :$ $[a, b]$ 에 대해, $a ≤ i < j ≤ b$ 면서 $P_i > P_j$ 인 $(i, j)$ 쌍의 개수. 전형적인 $mo's$ 문제 형..

원문보기 내부링크

Tistory

백준 25545 - MMST (C++)

문제 문제 링크 BOJ 25545 - MMST 문제 요약 모든 간선의 가중치가 다른 무향 연결 그래프가 주어진다. 이 그래프의 $MMST$를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ $N - 1 ≤ M ≤ 500,000$ $-10^9 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 최소 스패닝 트리(minimum spanning tree) 풀이 얼핏 잘못 보면 삽질하기 쉬운 문제인데, $mst$의 본질을 안다면 굉장히 쉬워진다. "모든 간선의 가중치가 다른 무향 연결 그래프가 주어질 때," 위 조건을 유의한 채 얻을 수 있는 정보를 나열하면 다음과 같다. $M == N - 1$일 때는 $MMST$가 존재할 수 없다. 반대로 $N..

원문보기 내부링크

Tistory

백준 26615 - 다오의 행사 계획하기 (C++)

문제 문제 링크 BOJ 26615 - 다오의 행사 계획하기 문제 요약 $N*N$ 크기 미로 모양의 행사장이 주어진다. 이곳에서 임의로 $K$개의 행사가 발생할 때, $T$일 간의 사람 수 변화를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N, M$ $N * M ≤ 10^5$ $1 ≤ T, K ≤ 10^5$ 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 누적 합(prefix_sum) 풀이 임의의 두 칸을 잇는 경로는 정확히 1개 있음이 보장된다고 한다. 즉, 미로는 트리이다. 두 칸을 잇는 경로에 대해 $V_i$명의 사람이 증가할 때, 영향 받는 칸의 수는 $LCA$ $With$ $Sparse$ $Table$ 을 이용해 $O(lo..

원문보기 내부링크

Tistory

백준 2295 - 세 수의 합 (C++)

문제 문제 링크 BOJ 2295 - 세 수의 합 문제 요약 $N$개의 자연수로 이루어진 집합 $U$가 주어진다. 적당한 세 수를 골라 더하여 집합 내 수를 표현할 때, 표현할 수 있는 가장 큰 수를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $5 ≤ N ≤ 1,000$ $1 ≤ N_i ≤ 200,000,000$ 답이 항상 존재함이 보장된다. 알고리즘 분류 자료 구조(data strucutures) 해시를 사용한 집합과 맵(hash _ set / map) 중간에서 만나기(meet in the middle) 풀이 $w$가 $U$에 속할 때, $x + y + z = w$를 만족하는 가장 큰 $(x, y, z)$를 찾아야 한다. 삼 중 포문으로 $TLE$ 맞기 딱 좋은 발상이 떠오를 수 ..

원문보기 내부링크

Tistory

백준 20946 - 합성인수분해 (C++)

문제 문제 링크 BOJ 20946 - 합성인수분해 문제 요약 자연수 $N$이 주어진다. 이 수의 '합성인수분해' 를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^{12}$ 알고리즘 분류 수학(math) 정수론(number theory) 그리디 알고리즘(greedy) 풀이 소수로 표현하는 소인수분해가 아닌 합성인수분해라니.. 꽤 흥미로운 문제 같다. 적당한 수 몇 개를 가지고 놀아보면 알겠지만, 결국 나열되는 합성수들이 단조성을 가지려면 소인수들의 곱으로 한 쌍씩 묶어주는 것이 최적임을 알 수 있다. 단, 나열되는 소인수들은 단조 증가 하여야 한다. 이에 따라 합성인수분해가 불가능 한 경우는 소인수가 하나일 때 즉, 소수일 때가 불가능 한 경우가 되겠다. 한가지..

원문보기 내부링크

Tistory

백준 20924 - 트리의 기둥과 가지 (C++)

문제 문제 링크 BOJ 20924 - 트리의 기둥과 가지 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리의 '기둥의 길이' 와 '가장 긴 가지의 길이' 를 구해보자. 제한 TL : $2.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^6$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 깊이 우선 탐색(dfs) 풀이 별로 설명이 필요한 부분이 없다. 문제에 정의된 데로 $dfs$를 이용해 슥슥 잘 구현해 주면 된다. 예제도 친절한 편. 전체 코드 1234567891011121314151617181920212223#includeusing namespace std; vector Gr[20000..

원문보기 내부링크

Tistory

백준 2213 - 트리의 독립집합 (C++)

문제 문제 링크 BOJ 2213 - 트리의 독립집합 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리의 '최대 독립집합'의 크기와 이를 구성하는 정점들을 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ N, C_i ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 트리$dp$ 역추적의 바이블같은 문제이다. 임의의 정점이 가질 수 있는 상태는 결국 둘 중 하나다. 최대 독립집합에 포함 되었을 때( $1$ ) ? 아니었을 때( $0$ ) ? 이에 따라 다음과 같이 점화식을 정의해보자. $dp[i][j] :$ $i$번 정점을 루트로 하는 서브 트리에서, $i$번 정점의 포함 상태가 $j$일..

원문보기 내부링크

Tistory

백준 13911 - 집 구하기 (C++)

문제 문제 링크 BOJ 13911 - 집 구하기 문제 요약 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드 및 스타벅스의 위치 정보가 주어진다. 문제에 정의된 $3$가지 조건을 만족하면서, 맥도날드 및 스타벅스까지의 거리 합이 최소가 되는 집을 찾아보자. 제한 TL : $1$ sec, ML : $256$ MB $3 ≤ V ≤ 10,000$ $1 ≤ w ≤ 10,000$ $0 ≤ E ≤ 300,000$ $1 ≤ x, y ≤ 100,000,000 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 풀이 우선 다익을 이용하는 문제란 것은 쉽게 알아 챌 수 있다. 당연히 모든 집에서 다익을 돌려보는 것은 간선의 개수가 많아 $TLE$ 확정일 듯 싶다. 역으로 맥도날드, 스타벅스의 입장으로부터..

원문보기 내부링크

Tistory

백준 13518 - 트리와 쿼리 9 (C++)

문제 문제 링크 BOJ 13518 - 트리와 쿼리 9 문제 요약 N개의 정점으로 이루어진 트리가 주어진다. Q개의 쿼리에 대한 답을 출력해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 100,000$ $1 ≤ E_w ≤ 1,000,000$ 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 오일러 경로 테크닉(euler_tour_technique) 오프라인 쿼리(offline_queries) mo's(mo's algorithm) 풀이 예제를 예시로 들고, 트리를 그려보자. 그럼 대략 위와 같은 모양으로 그려볼 수 있는데, 이때 $1$부터 $ETT$를 돌려보며 기록 순서를 작성해보면 다음과같이 써볼 수 ..

원문보기 내부링크

Tistory

백준 27453 - 귀엽기만 한 게 아닌 한별 양 (C++)

문제 문제 링크 BOJ 27453 - 귀엽기만 한 게 아닌 한별 양 문제 요약 가장 최근 지나온 $3$ 개 이하 칸에 있는 불상사의 개수 합이 $K$ 이하가 되게 이동하려 한다. 학교에서 집으로 가는 최단 거리를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N, M ≤ 1,000$ $0 ≤ K ≤ 27$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 풀이 우선 불상사 합이 $K$ 를 넘는지에 대한 여부는 이전 위치의 정보를 들고 있으면 간단히 처리할 수 있다. 방문 처리에 있어서 다소 까다로워 보일 수 있는데, "방향에 대한 방문 처리를 하자" 라는 생각이 들었다면 이미 문제를 다 푼 것이나 다름 없다. 구체적으..

원문보기 내부링크

Tistory

백준 2618 - 경찰차 (C++)

문제 문제 링크 BOJ 2618 - 경찰차 문제 요약 $2$차원 맵에서 $w$개의 사건이 발생한다. 두 대의 경찰차가 사건을 순차적으로 해결할 때, 두 대의 경찰차가 이동하는 거리의 합을 최소로 하는 경로를 찾아보자. 제한 TL : $1$ sec, ML : $128$ MB $5 ≤ N ≤ 1,000$ $1 ≤ W ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 플래티넘 $dp$계의 수문장같은 바이블 문제이다. 결국 매 시점마다 변하는 상태는 경찰차들의 위치 뿐이다. 이에 따라 다음과 같이 정의를 내려보자. $dp[p][q]$ : 각 경찰차의 마지막으로 해결한 사건 번호가 각각 $p, q$일 때 이동하는 거리 합의 최솟값. 이런 문제는 사실 위처럼 점화식 정의를 내리기까지가 문제이지 막상 정..

원문보기 내부링크

Tistory

백준 27953 - 공룡 게임 (C++)

문제 문제 링크 BOJ 27953 - 공룡 게임 문제 요약 $N$개의 장애물을 $2$가지 행동을 이용해 넘어야 한다. 각 행동마다 그에 따른 패널티를 받을 때, 모든 장애물을 넘기 위한 최소 패널티를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 5,000$ $1 ≤ A, B, X, Y, T_i ≤ 10^9$ $S_i ∈ {1, 2, 3}$ $T_i < T_j$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 만약 이 문제 의 향기를 맡았다면 정답이다. $dp[p][q]$ : 마지막으로 점프, 슬라이딩을 한 장애물이 각각 $p, q$ 일 때 남은 장애물들을 넘기 위한 최소 패널티. 구체적으로, 임의의 장애물 $k$를 점프로 극복 하려면 $S[k]$ 가 홀수이고 $T[k..

원문보기 내부링크

Tistory

백준 20183 - 골목 대장 호석 - 효율성 2 (C++)

문제 문제 링크 BOJ 20183 - 골목 대장 호석 - 효율성 2 문제 요약 $N$개의 정점으로 이루어진 그래프 및 출발점, 도착점, 가진 돈이 주어진다. 가진 돈으로 도착점까지 가는 데에 지나는 골목 요금의 최댓값의 최솟값을 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N ≤ 100,000$ $1 ≤ M ≤ 500,000$ $1 ≤ C ≤ 10^{14}$ $1 ≤ E_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 매개 변수 탐색(parametric search) 이분 탐색(binary search) 풀이 이 정도 범위에 지문에선 "최댓값의 최솟값"을 구하라고 한다.. 전형적인 파라 매트릭 문제 꼴이다. 다음과 같이 결정 문제를 정..

원문보기 내부링크

Tistory

백준 16453 - Linhas de Metrô (C++)

문제 문제 링크 BOJ 16453 - Linhas de Metrô 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리에 대해 그에 맞는 답을 출력하자. 제한 TL : $2$ sec, ML : $512$ MB $5 ≤ N ≤ 100,000$ $1 ≤ Q ≤ 20,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) 풀이 쿼리 내용은 간단하다. $Q : $ 트리 위 두 가지 경로가 주어질 때, 겹치는 정점의 수 ? 이는 $LCA$ $+$ $case$ $work$ 로 해결 하거나, 트리..

원문보기 내부링크

Tistory

백준 27945 - 슬슬 가지를 먹지 않으면 죽는다 (C++)

문제 문제 링크 BOJ 27945 - 슬슬 가지를 먹지 않으면 죽는다 문제 요약 $N$개의 정점을 잇는 $M$개의 간선 정보가 주어진다. $1$일차부터 매일 노점에 들려야 할 때, 버틸 수 있는 가장 긴 날의 수를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $N - 1 ≤ M ≤ min(5 * 10^5, {N\choose 2})$ $1 ≤ t_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 분리 집합(disjoint_set) 풀이 모든 요리 학원에 다닐 수 있도록 $N - 1$ 개의 길을 고른다고 한다. 이 대목에서 유사 $mst$ 문제임을 눈치 챘다면 문제는 쉬워진다. 날짜가 $1$일차부터 시작하므로..

원문보기 내부링크

Tistory

백준 27925 - 인덕션 (C++)

문제 문제 링크 BOJ 27925 - 인덕션 문제 요약 $3$개의 인덕션의 온도 이동을 적절히 분배해 모든 요리를 완성하는 최솟값을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 5,000$ $0 ≤ t_i ≤ 9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 고려해야 할 상태는 결국 네 가지( 몇번째 음식 ? 현재 인덕션들 각각의 온도? ) 로 귀결된다. 이에 따라 다음과 같이 정의를 내려보자. $dp[i][x][y][z]$ : $i$번째 음식까지 요리했고, 각 인덕션의 온도 상태가 $x, y, z$일 때 답. 임의의 인덕션 $x_i$의 시점에서 $a[i + 1]$로 이동하기 위한 루트는 $+$ 방향으로 이동하거나 $-$ 방향으로 이동 하거나 둘 중 하나다. 구체..

원문보기 내부링크

Tistory

백준 16934 - 게임 닉네임 (C++)

문제 문제 링크 BOJ 16934 - 게임 닉네임 문제 요약 문제에 정의된 별칭 규칙에 따라 $N$명의 유저의 별칭을 찾아주자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N ≤ 100,000$ 닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 $10$을 넘지 않는다. 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 굳이 트라이를 써먹지 않아도 해쉬 셋과 맵만으로 더욱 간단하고 효율적으로 풀이할 수 있다. 먼저 $N_i$번째 닉네임이 주어지면 $[1, 1], [1, 2], ... [1, n]$ 단위로 잘라보며 별칭이 될 수 있는지 확인한다. 만약 별칭이 될 수 있는 순간이 온다면 그 순간의 문..

원문보기 내부링크

Tistory

백준 23835 - 어떤 우유의 배달목록 (Easy) (C++)

문제 문제 링크 BOJ 23835 - 어떤 우유의 배달목록 (Easy) 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 쿼리를 적절히 처리해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 1,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 깊이 우선 탐색(dfs) 풀이 범위를 보면, $Eazy$ 버전 답게 굉장히 작다. 그냥 쿼리마다 $dfs$를 돌려 $O(QN)$의 복잡도를 가져도 널널해 보인다. $Hard$ 버전은 딱봐도 $hld$ + 세그먼트 트리일 듯 한데, 구간에 등차수열을 더하는 문제인 이 문제 를 트리 위에서 진행 한다고 생각하면 될 것 같다. 조만간 도전해 봐야지.. 전체 ..

원문보기 내부링크

Tistory

백준 2014 - 소수의 곱 (C++)

문제 문제 링크 BOJ 2014 - 소수의 곱 문제 요약 $K$개의 소수에서 몇 개의 소수들을 곱하여 나열할 수 있다. 이 수열의 $N$번째 수를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ K ≤ 100$ $1 ≤ N ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 우선순위 큐(priority_queue) 수학(math) 정수론(number_theory) 풀이 우선순위 큐를 활용하는, 웰노운스러운 문제다. 매 사이클마다 가장 작은 수( $Q.top()$ )를 가지고 입력받은 수들과 곱해주면 된다. 그렇게 뚝딱 짜고 냈더니 처음에 $MLE$ 를 한 번 맞았다. 저번에 비슷한 문제를 풀었을 땐 $K ≤ 10$ 에 $N ≤ 200,000$ 의 상한이어..

원문보기 내부링크

Tistory

백준 25620 - 슬라임 키우기 (C++)

문제 문제 링크 BOJ 25620 - 슬라임 키우기 문제 요약 $N$마리 슬라임의 크기와 $Q$개의 업데이트 쿼리가 주어진다. 모든 쿼리의 적용이 끝난 후 최종 슬라임들의 상태를 출력해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200 000$ $0 ≤ N_i, x_i, y_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 우선순위 큐(priority_queue) 수학(math) 정수론(number_theory) 풀이 간단하면서도 재밌는 관찰이 필요한 문제였다. 우선 항상 최솟값 ~ $x$의 범위를 빠르게 추려내야 하므로 최솟값 우선순위 큐를 떠올려볼 수 있다. 이제 범위를 보면, $0 ≤ N_i, x_i, y_i ≤ 10^9$ 이고 각 쿼..

원문보기 내부링크

Tistory

백준 25078 - Software Package Manager (C++)

문제 문제 링크 BOJ 25078 - Software Package Manager 문제 요약 $n$개의 정점으로 이루어진 트리와 $q$개의 쿼리가 주어진다. 각 쿼리를 알맞게 처리해보자. 제한 TL : $1$ sec, ML : $1024$ MB $7 ≤ n ≤ 100,000$ $5 ≤ q ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 오일러 경로 테크닉(euler_tour technique) 세그먼트 트리(segment tree) 느리게 갱신되는 세그먼트 트리(lazy propagation) 풀이 여기 에서 다룬 문제의 하위호환 격인 문제다. 이 문제 역시 경로에 대한 구간 쿼리를 빠..

원문보기 내부링크

Tistory

백준 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$를 $..

원문보기 내부링크

Tistory

백준 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..

원문보기 내부링크

Tistory

백준 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 을..

원문보기 내부링크

Tistory

백준 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) 풀이 이 문제 를 풀어 보았는가 ? 이번 문제는 위 ..

원문보기 내부링크

Tistory

백준 16587 - Hierarchical Structure (C++)

문제 문제 링크 BOJ 16587 - Hierarchical Structure 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. $Q$개의 경로 쿼리에 대해 알맞는 답을 출력하자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 100,000$ $1 ≤ A_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 머지 소트 트리(merge sort tree) 정렬(sorting) 누적 합(prefix sum) 이분 탐색(binary search) 풀이 쿼리의 내용을 정리하면 다음과 같이 생각할 수 있다. 두 정점을 잇는 경..

원문보기 내부링크

Tistory

백준 27396 - 문자열 변환과 쿼리 (C++)

문제 문제 링크 BOJ 27396 - 문자열 변환과 쿼리 문제 요약 문자열 $S$가 주어진다. $N$개의 쿼리에 대해 그에 맞는 처리를 해보자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ len(S) ≤ 100,000$ $1 ≤ N ≤ 300,000$ $1 ≤$ 유형 $2$로 출력되는 문자의 총 수 $≤ 10^7$ 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 쿼리 1에서 $S$를 돌아보며 일일히 바꿔주고 있으면 당연히 $TLE$ 다. 등장하는 문자가 알파벳으로 한정됨에 따라 이에 맞는 카운트 배열을 만들어 주자. $M[x] = y$ : 문자 $x$가, 현재 문자 $y$로 바뀐 상태. 쿼리 ..

원문보기 내부링크

Tistory

백준 27397 - 문자열 변환과 쿼리 2 (C++)

문제 문제 링크 BOJ 27397 - 문자열 변환과 쿼리 2 문제 요약 문자열 $S$가 주어진다. $N$개의 쿼리에 대해 그에 맞는 처리를 해보자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ len(S) ≤ 300,000$ $1 ≤ N ≤ 300,000$ $1 ≤$ $len(S)$ $*$ $count(n_2)$ $≤ 10^7$ 알고리즘 분류 자료 구조(data structures) 문자열(string) 해시를 사용한 집합과 맵(hash _ set / map) 풀이 문자열 변환과 쿼리 $1$ 과 별반 다를 게 없다. 쿼리 내용 그대로 이번엔 최대 연속 구간을 세주면 되겠다. 이 역시 세번째 제한으로 인해 복잡도가 보장된다. 전체 코드 1234567891011121314151617181..

원문보기 내부링크

Tistory

백준 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) 희소 배열(sparse table) 최소 공통 조상(lowest common ancestor) 풀이 $N$개의 간선으로 이루어진 그래프 즉, 사이클이 내포된 $Unicycle$ $Graph$ 에서 사이클을 분리하는 방법을 아는가? 이에 익숙치 않다면 다음..

원문보기 내부링크

Tistory

백준 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$가 직접적으로 주어진다. 따라서, 동적 노드마다 절반 이상에서 ..

원문보기 내부링크

Tistory

백준 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..

원문보기 내부링크

Tistory

백준 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$ 만큼 비용..

원문보기 내부링크

Tistory

백준 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번 땅은 애초에 고려될 필요가..

원문보기 내부링크

Tistory

백준 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]$ : $..

원문보기 내부링크

Tistory

백준 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% 동일하니 간략하게 차이점만 짚고 넘어 가겠다. 그나..

원문보기 내부링크

Tistory

백준 4008 - 특공대 (C++)

문제 문제 링크 BOJ 4008 - 특공대 문제 요약 병사 $N$명의 전투력과 조정 전투력 등식 계수가 주어진다. 문제에 정의된 전투력 측정 방식을 따를 때, $n$명의 병사들에 대해 얻을 수 있는 최대 조정 전투력을 구해보자. 제한 TL : $1$ sec, ML : $64$ MB $1 ≤ N ≤ 1,000,000$ $-5 ≤ a ≤ -1$ $|b| ≤ 10,000,000$ $|c| ≤ 30,000,000$ $1 ≤ xi ≤ 100$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 CHT 대표 문제로 꼽히는 문제다. 물론 나도 CHT 태그를 타고 들어 왔지만 처음 내 반응은 "이게 왜 CHT?" 였다. 우선 연속 부분 수열 합을 고려해야 하므로 ..

원문보기 내부링크

Tistory

백준 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))$ 의 이득이 발..

원문보기 내부링크

Tistory

백준 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++..

원문보기 내부링크

Tistory

백준 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$로 굉장히 작아 모든 경우를 돌려보면 된다...

원문보기 내부링크

Tistory

백준 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$ 중 가장 큰 녀석에게 가지를 주는 것이 이득이지 않겠는가? 이러한 상황에 더없이 편한 녀석이 우선순위 큐다. 이..

원문보기 내부링크

Tistory

백준 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) 풀이 다익스트라 냄새가 물씬 나는 문제지만, 그동안 알고 있던 다익 문제들과 살짝 궤를 달리하는 신선한 문제다. 핵심은 문제에..

원문보기 내부링크

Tistory

백준 16947 - 서울 지하철 2호선 (C++)

문제 문제 링크 BOJ 16947 - 서울 지하철 2호선 문제 요약 $N$개의 정점과 간선으로 이루어진 그래프가 주어진다. 임의의 두 역 사이에 경로가 항상 존재할 때, 각 노드로부터 사이클 형상 까지의 거리를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $3 ≤ N ≤ 3,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs) 풀이 $N$개의 간선으로 이루어진 그래프에서 사이클을 떼네어볼 수 있는가를 묻는 교육적인 문제이다. 나는 개인적으로 indegree를 이용한 bfs를 이용해 사이클을 분리하는 방식을 선호한다. 다음의 과정을 보자. 간선 정보를 입력 받으면서 indegree를 카운트 해주면..

원문보기 내부링크

Tistory

백준 20440 - 니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마 - 1 (C++)

문제 문제 링크 BOJ 20440 - 니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마 - 1 문제 요약 $N$개의 모기 출입 정보가 주어진다. 이때, 모기가 가장 많이 있는 시간대의 모기 마릿수와 그 연속 구간을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 1,000,000$ $0 ≤ T_E < T_X ≤ 2,100,000,000$ 알고리즘 분류 누적 합(prefix_sum) 정렬(sorting) 값 / 좌표 압축(coordinate_compression) 풀이 수직선 상에 $N$번의 업데이트 후 최종 상태 출력.. 전형적인 imos법의 형태이다. 그러나 주어지는 좌표 범위가 $N$에 비해 난감하다. 어차피 존재할 수 있는 좌표 상태는 많아봐야 $2,0..

원문보기 내부링크

Tistory

백준 5467 - Type Printer (C++)

문제 문제 링크 BOJ 5467 - Type Printer 문제 요약 출력해야 하는 $N$개의 단어 목록이 주어진다. 프린터로 $3$가지의 작업을 수행할 수 있을 때, 주어진 단어 목록을 모두 출력하는 최소 작업 경로를 추적해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 25,000$ 각 단어는 소문자로만 구성되며 중복이 없고 20자를 넘지 않는다. 알고리즘 분류 자료 구조(data structures) 문자열(string) 트리(trees) 트라이(trie) 정렬(sorting) 풀이 결국 가장 긴 단어를 맨 마지막으로 출력해야 한다는 것은 자명하다. 단어들을 순회함에 있어서 트라이에 $N$개의 단어들을 모두 올린 뒤 이어진 max_size순으로 순회하면 될 듯 하다. ..

원문보기 내부링크

Tistory

백준 2550 - 전구 (C++)

문제 문제 링크 BOJ 2550 - 전구 문제 요약 $N$개의 스위치 및 전구의 연결 정보가 주어진다. 이때 교차하지 않게 가장 많은 전구를 켤 수 있는 경우를 추적해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 가장 긴 증가하는 부분 수열 O(NlogN) 풀이 그림만 봐도 알겠지만, 기본적인 lis 역추적 문제이다. $N$의 범위에 따라 $O(NlogN)$ 솔루션이 강제되지 않기 때문에, 굳이 이분 탐색을 이용하지 않아도 널널해 보인다. 전체 코드 12345678910111213141516171819202122232425262728#include#define N 10001using namespace std; vect..

원문보기 내부링크

Tistory

백준 27114 - 조교의 맹연습 (C++)

문제 문제 링크 BOJ 27114 - 조교의 맹연습 문제 요약 $3$가지 행동에 대한 에너지 소모량과 사용하고자 하는 에너지양이 주어진다. 정확히 사용하고자 하는 에너지양을 모두 소모하려할 때, 처음 바라보는 방향으로 돌아오는 행동 수행 횟수의 최솟값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ A, B, C, K ≤ 1,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 결국 매 순간마다 표현되는 상태는 두가지다. 남은(소모해야 하는) 에너지양과 바라보고 있는 방향. 이에 따라 다음과 같은 정의를 내려보자. $dp[i][j]$ : 남은 에너지양이 $i$이고 $j$의 방향을 바라보고 있을 때 제식 수행 횟수의 최솟값. 각 방향을 기준으로 $3$가지의 변화를 고..

원문보기 내부링크

Tistory

백준 13502 - 단어퍼즐 2 (C++)

문제 문제 링크 BOJ 13502 - 단어퍼즐 2 문제 요약 $5*5$의 맵과 미리 기록된 dict가 주어진다. dict에 속한 단어 중 맵에서 8방 탐색을 통해 찾을 수 있는 단어의 수를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB 알고리즘 분류 자료 구조(data structures) 문자열(string) 트리(trees) 트라이(trie) 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 백트래킹(backtracking) 런타임 전의 전처리(precomputation) 풀이 문제 자체는 어렵지 않다. dict에 속한 단어들을 트라이에 다 때려 박은 다음 맵에서 백트래킹으로 찾아지는 단어의 수를 구해주면 된다. 처음에 dict를 str..

원문보기 내부링크

Tistory

백준 14948 - 군대 탈출하기 (C++)

문제 문제 링크 BOJ 14948 - 군대 탈출하기 문제 요약 $N*M$의 맵이 주어지고 $(1, 1)$에서 $(N, M)$으로 이동하려 한다. 최소 각 칸에 적힌 레벨만큼은 되어야 해당 칸을 지날 수 있고 딱 한 번 한 칸을 건너뛸 수 있을 때, 갖춰야 하는 최소 레벨을 구해보자. 제한 TL : $1$ sec, ML : $256$ MB $1 ≤ n, m ≤ 100$ $0 ≤ k ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 이분 탐색(binary search) 매개 변수 탐색(parametric search) 풀이 문제 내용과 $k$의 범위만 봐도 파라매트릭 냄새가 솔솔 난다. 다음과 같이 결정 문제를 정의해보자. $f(x)$..

원문보기 내부링크

Tistory

백준 18277 - Bliski Brojevi (C++)

문제 문제 링크 BOJ 18277 - Bliski Brojevi 문제 요약 $N$개의 수열과 $Q$개의 쿼리가 주어진다. 각 쿼리마다 주어지는 구간에서의 $l ≤ i < j ≤ r$ 인 $min(|pi - pj|)$ 값을 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 30,000$ 알고리즘 분류 자료 구조(data structures) 세그먼트 트리 (segment tree) 오프라인 쿼리(offline_queries) mo's(mo's algorithm) 풀이 척 보면 mo's 냄새가 솔솔 난다. 그럼 문제는 결국 현재 관리하는 구간( $[s, e]$ )에서의 $X$ ( $l ≤ i < j ≤ r$ 를 만족하는 $min(|p_i$ - $p_j|)$ ) 를 어떻게..

원문보기 내부링크

Tistory

백준 19585 - 전설 (C++)

문제 문제 링크 BOJ 19585 - 전설 문제 요약 $C$가지의 색상과 $N$개의 닉네임이 주어진다. 색상과 닉네임을 순서대로 이어붙여 팀명을 지으면 ICPC 리저널에서 수상할 수 있을 때, $Q$개의 쿼리에 대해 해당 팀이 수상할 수 있는지 여부를 판단해보자. 제한 TL : $3$ sec, ML : $1024$ MB $1 ≤ C, N ≤ 4,000$ $1 ≤ Q ≤ 20,000$ 모든 색상 이름의 길이와 닉네임의 길이는 1,000글자를 넘지 않는다. 각 문자열은 중복되지 않으며 알파벳 소문자로만 이루어져 있다. 알고리즘 분류 자료 구조(data structures) 문자열 (string) 트리 (trees) 트라이 (trie) 해시를 사용한 집합과 맵 (hash _ set / map) 풀이 당연히 무..

원문보기 내부링크

Tistory

백준 25478 - Marinada (C++)

문제 문제 링크 BOJ 25478 - Marinada 문제 요약 $N * M$ 크기의 맵이 주어진다. $U$에서 목표 지역을 모두 거친 뒤 $I$로 이동하는 최소 이동 거리를 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, M ≤ 1,000$ $1 ≤ K ≤ 16$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 다이나믹 프로그래밍(dp) 비트마스킹(bitmask) 비트필드를 이용한 다이나믹 프로그래밍(dp_bitfield) 외판원 순회 문제(traveling salesman problem) 풀이 구현량이 적은 편은 아니지만, 그리 어려운 구현은 없는 문제이다. 결국 구하라는 것은 목표 지점을 모두 순회하는 최..

원문보기 내부링크

Tistory

백준 27978 - 보물 찾기 2 (C++)

문제 문제 링크 BOJ 27978 - 보물 찾기 2 문제 요약 $H * W$ 크기의 맵이 주어진다. 배에서부터 보물까지 이동하는 데에 드는 최소 연료 소모량을 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $3 ≤ H, W ≤ 500$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 풀이 문제의 정의에 따라 임의의 위치에서 오른 쪽으로 이동할 때 즉, $x$의 좌표가 증가할 때 가중치를 $0$ 으로 두고 나머지 $5$개의 방향에 대해선 가중치를 $1$로 두자. 구현 상 편의를 위해 $($, →, $)$에 해당하는 이동을 한 곳으로 몰아주고$( d[5], d[6] , d[7] )$ 인덱스 상의 비교$( i < 5 )$ 를 통해 가중..

원문보기 내부링크

Tistory

백준 25973 - 어지러운 트리 (C++)

문제 문제 링크 BOJ 25973 - 어지러운 트리 문제 요약 $N$개의 정점으로 이루어진 트리와 두 종류로 이루어진 $Q$개의 쿼리가 주어진다. 각 쿼리마다 그에 알맞는 처리를 해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $2$번 쿼리는 적어도 하나 이상 주어진다. 알고리즘 분류 트리(trees) 최소 공통 조상(lowest ancestor common) 다이나믹 프로그래밍(dp) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 주어지는 쿼리는 다음과 같다. $1$ $x$ : 루트 노드를 $x$번 노드로 변경한다. $2$ $x$ : $LCA(a, b) = x$번 노드인 $(a, b)$의 쌍으로 가능한 경우의 수를 출력한다. $(a, b)$와..

원문보기 내부링크

Tistory

백준 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 (C++)

문제 문제 링크 BOJ 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 문제 요약 $N$개의 정점으로 이루어진 트리와 윤이, 달구(경찰), 포닉스(경찰)의 시작 위치가 주어진다. 매 순간 윤이가 먼저 움직이고, 모두가 최선의 전략으로 추격전을 벌일 때 윤이가 탈출 할 수 있는 지의 여부를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ 윤이, 달구, 포닉스의 시작 위치는 모두 다르다. 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리 깊이 우선 탐색(dfs) 그리디 알고리즘(greedy) 풀이 문제를 읽어가면서 동시에 한가지 풀이가 떠올랐다. 시작 위치가 어떻던, 트리가 어떤 모양이던 간에 존재하는 모든 리프 노드에..

원문보기 내부링크

Tistory

백준 16920 - 확장 게임 (C++)

문제 문제 링크 BOJ 16920 - 확장 게임 문제 요약 $N*M$ 크기의 맵이 주어지고 $P$명의 플레이어 정보가 주어진다. 플레이어 번호 순으로 각 성이 $S_i$만큼 확장할 때, 최종 맵 상태를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, M ≤ 1,000$ $1 ≤ P ≤ 9$ $1 ≤ Si ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 풀이 각 플레이어별로 큐를 관리하고, 다음 이동을 담아줄 별도의 temp 큐 하나를 운용하였다. 맵은 통합으로 관리해 주었고 매 순간마다 각 플레이어 전용 큐 size의 합이 $0$이면 최종 상태가 됨을 판단 하였다. 위 조건이 만족될 때까지 계속해서..

원문보기 내부링크

Tistory

백준 22487 - Do use segment tree (C++)

문제 문제 링크 BOJ 22487 - Do use segment tree 문제 요약 N개의 정점으로 이루어진 트리와 두가지 유형으로 이루어진 Q개의 쿼리가 주어진다. 각 쿼리에 대하여 알맞게 처리해보자. 제한 1 ≤ N ≤ 200,000 1 ≤ Q ≤ 100,000 -10,000 ≤ wi ≤ 10,000 알고리즘 분류 구현 (implemantation) 자료 구조 (data structures) 트리 (trees) heavy - light 분할 (heavy - light decomposition) 세그먼트 트리 (segment tree) 느리게 갱신되는 세그먼트 트리 (lazy propagation) 풀이 이 문제를 시도하는 사람들이라면, 이제는 웰노운이 되어 버린 유형을 알고 있을 것이고 풀어봤을 것이..

원문보기 내부링크

Tistory

백준 8571 - Apteka (C++)

문제 문제 링크 BOJ 8571 - Apteka 문제 요약 $N$명의 $C_i$값이 주어진다. 자리를 바꿀 때마다 문제에 정의된 데로 비용이 발생할 때, 맨 앞으로 가는 최소 비용을 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N ≤ 10^6$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화 (convex hull trick) 풀이 우선 문제를 다음과 같이 이해하면 편하다. "$Hansel$의 위치가 $0$ 번 인덱스이고, $1, 2, ... N$번 인덱스 사람들의 $C_i$가 주어진다. 자리 스왑마다 $Hansel$과 $i$가 떨어진 거리 * $C_i$ 의 비용이 발생 한다고 할 때 $Hansel$이 $N$번째 자리에 도달..

원문보기 내부링크