본문 바로가기

전체 글

 (141)
백준 30622 - Rush & Slash (C++) 문제 문제 링크 BOJ 30622 - Rush & Slash 문제 요약 $2$차원 상의 잡초들의 좌표 $(x_i, y_i)$가 $N$개 주어진다. 일련의 과정을 따라, 모든 잡초들을 제거하기 위해 이동해야 하는 거리의 합의 최솟값을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $-10^9 ≤ x_i, y_i ≤ 10^9$ 주어지는 모든 좌표는 서로 다르다. 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree_set) 분리 집합 (disjoint_set) 풀이 모든 좌표 $(x_i, y_i)$에 대해, 해당 좌표를 기준으로 $8$방향을 보며 인접한 좌표가 주어졌는지 확인하자. $x_i$와 $y_i$의 좌표 범위에 따..
백준 30515 - 방형구 탐색 (Hard) (C++) 문제 문제 링크 BOJ 30515 - 방형구 탐색 (Hard) 문제 요약 $1*N$ 크기의 격자에서, 각 칸에 피어있는 꽃의 종류 $A_1, A_2, ... , A_N$가 주어진다. 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $l$ $r$ $k$ : $[l, r]$에서 꽃의 종류가 $k$인 꽃의 개수를 출력한다. $2$ $l$ $r$ : $[l, r]$에 속한 모든 꽃들을 제거한다. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $1 ≤ A_i$$, k ≤ 10^9$ $1$번 쿼리는 하나 이상 주어진다. 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree_set) 풀이 $EASY$버전을 나이브하게 짜고..
백준 20933 - 마스크펑크 2077 (C++) 문제 문제 링크 BOJ 20933 - 마스크펑크 2077 문제 요약 $N$개의 마을 각각에 대해, 마스크 생산 비용과 인접 마을 간 이동 시간이 주어진다. 아래 두 쿼리를 수행하는 프로그램을 작성하자. $UPDATE$ $x$ $k$ : $x$번째 집과 $x+1$번째 집 사이의 이동 시간을 $k$분으로 갱신한다. $(1 ≤ x ≤ N-1$, $1 ≤ k ≤ 10^4)$ $CALL$ $x$ $k$ : $x$번째 집이 $k$분 이내에 얻을 수 있는 가장 싼 마스크의 가격을 출력한다. $(1 ≤ x ≤ N$, $1 ≤ k ≤ 10^6)$ 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $1 ≤ Q ≤ 5*10^4$ 알고리즘 분류 자료 구조 (data_structures) 세그..
백준 24124 - 高速道路 (Highway) (C++) 문제 문제 링크 BOJ 24124 - 高速道路 (Highway) 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리에서는, 간선 $e$가 정점 $u, v$를 이을 때 $weight_{uv}$와 $weight_{vu}$가 다를 수 있다. 어떤 $e$에 대해 번호가 작은 정점에서 큰 정점으로 향하는 방향을 상행, 반대를 하행이라고 하자. 이때, 다음 두 쿼리를 수행하는 프로그램을 작성해보자. $I$ $r$ $s$ $t$ : $r$번 간선의 상행 소요 시간을 $s$, 하행 소요 시간을 $t$로 수정한다. $Q$ $x$ $y$ : $x$번 정점에서 $y$번 정점에 도달하는 총 소요 시간을 출력한다. 제한 TL : $4$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $1 ≤ Q ≤..
백준 24505 - blobhyperthink (C++) 문제 문제 링크 BOJ 24505 - blobhyperthink 문제 요약 길이 $N$의 수열이 주어진다. 이 수열에서, 길이가 $11$인 증가수열의 개수를 $10^9+7$로 나눈 나머지를 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $1 ≤ A_i ≤ N$ 알고리즘 분류 다이나믹 프로그래밍(dp) 자료 구조(data_structures) 세그먼트 트리(segtree) 풀이 $N$이 적당히 작았다면, 각 $i$마다 이전 수열을 순회하며 답을 계산하는 $O(N^2)$에 풀 수 있을 테지만 $N ≤ 10^5$이다. $[A_1, A_i]$에서 길이가 $k$인 증가 수열의 개수를 구한다고 해보자. 이는 $A_1$, $A_2$, ... , $A_{i-1}$인 $A..
백준 30461 - 낚시 (C++) 문제 문제 링크 BOJ 30461 - 낚시 문제 요약 $N*M$개의 칸 각각에 존재하는 물고기의 정보가 주어진다. $Q$개의 쿼리에 대해, 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력하자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N,M ≤ 2,000$ $1 ≤ Q ≤ 300,000$ $0 ≤ a_{ij} ≤ 500$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 누적 합 (prefix_sum) 풀이 $dp[i][j]$에 $Q(i, j)$의 답을 저장한다고 생각해보자. 계단식으로 답을 계산할 수 있으므로, 먼저 $dp[i][j]$는 $dp[i - 1][j - 1]$을 포함한다. 여기에 추가적으로 $A[i][j] + A[i - 1][j] + A[i - 2][j] + ....
백준 30464 - 시간낭비 (C++) 문제 문제 링크 BOJ 30464 - 시간낭비 문제 요약 $a_1, a_2, ... , a_N$이 주어진다. 각 $a_i$에서는 해당 칸에 적힌 칸만큼 바라보는 방향으로 이동할 수 있다. 바라보는 방향을 최대 두 번 반전할 수 있을 때, $a_1$에서 $a_N$에 최대한 늦게 도착하는 경우를 찾아보자. 제한 TL : $1$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ $0 ≤ a_i ≤ 200,000$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 풀이 어떤 위치에서 고려해야할 상태는 $3$가지가 있다고 생각했다. 어느 위치$?$ 어느 방향$?$ 지금까지 몇 번 반전$?$ 이에 따라, 다음과 같이 점화식을 정의하자. $dp[u][p][q] :$ $a_u$에서, 방향 $p$를 바라보고 ..
백준 30466 - 우정은 BFS처럼, 사랑은 DFS처럼 (C++) 문제 문제 링크 BOJ 30466 - 우정은 BFS처럼, 사랑은 DFS처럼 문제 요약 $1$부터 $N$까지 번호가 메겨진 $N$개의 정점으로 이루어진 트리를 구하고자 한다. $1$번 정점을 시작으로 $DFS$와 $BFS$를 수행할 때, $d_i$, $b_i$를 각각 $DFS$, $BFS$에서 $i$번 정점에 방문한 순서라고 정의하자. 이때, $\sum_{i=1}^{N}{|d_i-b_i|}$ 을 최대로 하는 트리를 만들어보자. 제한 TL : $1$ sec, ML : $1024$ MB $3 ≤ N ≤ 200,000$ 각 탐색에서, 순회 후보가 여럿인 경우에는 번호가 더 작은 정점을 먼저 방문한다. 알고리즘 분류 트리 (trees) 해 구성하기 (constructive) 풀이 적당한 $N$에 대해 이런 저런 ..

티스토리툴바