전체 글 (141) 썸네일형 리스트형 백준 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 .. 이전 1 ··· 15 16 17 18 다음