Problem Solving (145) 썸네일형 리스트형 백준 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$에 대해 이런 저런 .. 백준 25606 - 장마 (C++) 문제 문제 링크 BOJ 25606 - 장마 문제 요약 $N$일동안 비가 내린다. 장마 시작 $t$일 후 내리는 비는 상자에 $a_i$만큼 물을 채운다. 보관된 상자에선 매일 $M$만큼의 물이 증발할 때, 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $t$ : 장마 시작 $t$일 후, 모든 상자에 들어있는 물의 양의 합은 무엇인가$?$ $2$ $t$ : 장마 시작 $t$일 후, 모든 상자에서 증발하는 물의 양의 합은 무엇인가$?$ 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ M, a_i ≤ 10^4$ 알고리즘 분류 누적 합 (prefix_sum) 풀이 쿼리가 들어올 때마다 답을 계산하기엔 조금 귀찮아 보인다. $N ≤ 10^5$이고 각 $N_i$.. 백준 23314 - Minimum Spanning Cactus (C++) 문제 문제 링크 BOJ 23314 - Minimum Spanning Cactus 문제 요약 $N$개의 정점과 이들을 잇는 무향 가중치 간선 $M$개로 이루어진 $Cactus$ $Graph$가 주어진다. 아래 쿼리를 수행하는 프로그램을 작성하자. $u$ $v$ $d$ : 정점 $u$와 정점 $v$를 잇는 간선의 가중치를 $d$로 바꾸고, 최소 신장 선인장의 비용을 출력한다. 제한 TL : $1.2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $N-1 ≤ M ≤ 150,000$ $1 ≤ Q ≤ 100,000$ $-10^9 ≤ c ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component).. 백준 21025 - Healthy Lifestyle (C++) 문제 문제 링크 BOJ 21025 - Healthy Lifestyle 문제 요약 $N$개의 정점과, 이들을 잇는 $M$개의 간선으로 이루어진 그래프가 주어진다. 아래의 쿼리를 수행하는 프로그램을 작성하자. $u$ $v$ : $u$에서 $v$로 가는 서로 다른 경로가 존재하면 $YES$, 존재하지 않는다면 $NO$를 출력한다. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, M, Q ≤ 10^5$ 알고리즘 분류 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component) 자료 구조 (data_structures) 분리 집합 (disjoint_set) 풀이 간단히 생각해보면, 답이 $YES$인 경우는 $u, v$가 같은 사이클에 속할 때 뿐이라는 것을 알 수 .. 백준 26358, 26359 - A Prickly Problem – Black Edition (C++) 문제 문제 링크 BOJ 26359 - A Prickly Problem – Black Edition 문제 요약 $V$개의 정점으로 이루어진 $Cactus$ $Graph$가 주어진다. 스패닝 트리가 되도록 $V-1$개의 간선만을 남겼을 때, 서로 다른 모양의 트리가 존재할 수 있다. 이 스패닝 트리의 가짓수에 대해 $1,007$로 나눈 나머지를 출력하자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ V ≤ 50,000$ $1 ≤ E ≤ (3*V)/2$ 주어지는 그래프는 $Cactus$ $Graph$임이 보장된다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 알고리즘 분류 그래프 이론 (graphs) 이중 연결 요소 (biconnected_component) 선인장 (cactus) .. 이전 1 2 3 4 5 6 ··· 19 다음 3/19