본문 바로가기

분류 전체보기

 (144)
백준 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 (C++) 문제 문제 링크 BOJ 27924 - 윤이는 엄청난 것을 훔쳐갔습니다 문제 요약 $N$개의 정점으로 이루어진 트리와 윤이, 달구(경찰), 포닉스(경찰)의 시작 위치가 주어진다. 매 순간 윤이가 먼저 움직이고, 모두가 최선의 전략으로 추격전을 벌일 때 윤이가 탈출 할 수 있는 지의 여부를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ 윤이, 달구, 포닉스의 시작 위치는 모두 다르다. 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 깊이 우선 탐색(dfs) 그리디 알고리즘(greedy) 풀이 문제를 읽어가면서 동시에 다음의 생각이 떠올랐다. 시작 위치가 어떻던, 트리가 어떤 모양이던 간에 존재하는 모든..
백준 25973 - 어지러운 트리 (C++) 문제 문제 링크 BOJ 25973 - 어지러운 트리 문제 요약 $N$개의 정점으로 이루어진 트리와 $Q$개의 쿼리가 주어진다. 각 쿼리마다 그에 맞는 처리를 진행하자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $2$번 쿼리는 적어도 하나 이상 주어진다. 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 다이나믹 프로그래밍(dp) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 매 쿼리마다 $dfs$ 돌려볼 순 없는 노릇이다. 루트가 $1$인 최초 시점을 기준으로 모든 경우의 수를 전처리 후, $x$와 현재 루트 정점을 가지고 뭐 어떻게 잘 요리해서 쿼리당 $O(logN)$ 으로 응답할 것을 생각하자. 경우의..
백준 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 )$ 를 통해 가중..
백준 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) 풀이 구현량이 적은 편은 아니지만, 그리 어려운 구현은 없는 문제이다. 결국 구하라는 것은 목표 지점을 모두 순회하는 최..
백준 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) 풀이 당연히 무..
백준 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|)$ ) 를 어떻게..
백준 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$번째 자리에 도달..
백준 22487 - Do use segment tree (C++) 문제 문제 링크 BOJ 22487 - Do use segment tree 문제 요약 $N$개의 정점으로 이루어진 트리와 두가지 유형으로 이루어진 $Q$개의 쿼리가 주어진다. 각 쿼리를 알맞게 처리해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N ≤ 200,000$ $1 ≤ Q ≤ 100,000$ $-10,000 ≤ w_i ≤ 10,000$ 알고리즘 분류 구현 (implemantation) 자료 구조 (data structures) 트리 (trees) heavy-light 분할 (heavy-light decomposition) 세그먼트 트리 (segment tree) 느리게 갱신되는 세그먼트 트리 (lazy propagation) 풀이 BOJ 16993 - 연속합과 쿼리 BOJ ..

티스토리툴바