분류 전체보기 (145) 썸네일형 리스트형 백준 30869 - 빨리 기다리기 (C++) 문제 문제 링크 BOJ 30869 - 빨리 기다리기 문제 요약 $N$개의 버스 정류장에 대해 $M$개의 버스 노선 정보가 주어진다. '빨리 기다리기'를 최대 $K$번까지 사용할 수 있을 때, $1$번 정류장에서 $N$번 정류장까지 가는 데에 걸리는 최소 시간을 구해보자. 제한 TL : $2$ sec, ML : $1024$ MB $2 ≤ N ≤ 500$ $0 ≤ K ≤ 500$ $1 ≤ M ≤ 250,000$ $1 ≤ t_i, g_i ≤ 10,000$ 알고리즘 분류 그래프 이론 (graphs) 다익스트라 (dijkstra) 풀이 그래프에서 두 정점쌍 간의 최단 거리는 기본적으로 다익스트라를 이용해 쉽게 구할 수 있다. 그런데 이번 문제에선, 고려해야 할 것들이 조금 있다. 간선마다 배차 간격이 존재한다. .. 백준 30512 - 조용히 완전히 영원히 (C++) 문제 문제 링크 BOJ 30512 - 조용히 완전히 영원히 문제 요약 길이 $N$의 수열 $A_1, A_2, ... , A_N$이 주어진다. 아래 쿼리가 $Q$개 주어질 때, $Q$개의 쿼리를 순서대로 처리한 후의 수열과 각 쿼리마다 잊힌 원소의 개수를 구해보자. $L$ $R$ $x$ : 모든 $L ≤ i ≤ R$에 대해 $A_i = min(A_i, x)$를 적용한다. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $0 ≤ A_i, x ≤ 1,000,000$ 알고리즘 분류 자료 구조 (data_structures) 세그먼트 트리 (segtree) 느리게 갱신되는 세그먼트 트리 (lazy_propagation) 풀이 구간 업데이트답게 무지성 $lazy$_$p.. 백준 30691 - 슈퍼 트리 뽀개기 (C++) 문제 문제 링크 BOJ 30691 - 슈퍼 트리 뽀개기 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 어떤 정점을 대상으로 작업을 진행할 때, 그 정점을 루트로 하는 서브트리에서 거리가 $K$ 이하인 모든 정점들이 함께 뽀개진다고 한다. 한 번의 작업만 수행할 수 있을 때 최대한 많은 정점을 뽀개는 경우를 찾아보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $1 ≤ K ≤ 10^{18}$ $1 ≤weight ≤ 10^9$ 알고리즘 분류 자료 구조 (data_structures) 트리 (trees) 세그먼트 트리 (segtree) 머지 소트 트리 (merge_sort tree) 오일러 경로 테크닉 (euler_tour technique) 풀이 트리 문제.. 백준 30621 - 어? 금지 (C++) 문제 문제 링크 BOJ 30621 - 어? 금지 문제 요약 $N$개의 시각에 대해 수열 $t_N, b_N, c_N$이 주어진다. 성우가 규칙을 지키는 선에서 대회장에 줄 수 있는 최종 혼란의 최댓값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 100,000$ $1 ≤ t_i, b_i, c_i ≤ 10^9$ $t_{i-1} < t_i;$ $b_i ≤ t_i$ 알고리즘 분류 다이나믹 프로그래밍 (dp) 이분 탐색 (binary_search) 풀이 어떤 시각 $t_i$에서, 선택할 수 있는 분기 방향을 생각해보자. 이는 다음과 같을 것이다. '어?'를 외치지 않는다. 지금부터 '어?'를 처음 외친다. 두 번째 경우의 연장선인데, $(t_i - b_i)$부터 지금까지 '.. 백준 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 ≤.. 이전 1 2 3 4 5 ··· 19 다음 2/19