whyz카테고리
문제 풀이
알고리즘 문제 풀이를 기록합니다.-
[BOJ] 3176 | 도로 네트워크
Sparse table로 LCA를 구하면서 조상까지의 최장·최단 도로를 함께 DP로 저장해, 각 쿼리를 O(log N)에 처리합니다.
-
[BOJ] 5419 | 북서풍
섬을 좌표 기준으로 정렬해 스위핑하고, 좌표 압축과 세그먼트 트리로 항해 가능한 섬 쌍의 개수를 O(N log N)에 셉니다.
-
[BOJ] 13537 | 수열과 쿼리 1
쿼리와 원소를 값 기준 내림차순으로 정렬한 뒤, 세그먼트 트리에 하나씩 반영하는 오프라인 쿼리 방식으로 구간 내 k보다 큰 원소 개수를 구합니다.
-
[BOJ] 2436 | 공약수
GCD × LCM = a × b라는 관계와 유클리드 호제법을 이용해, √(GCD·LCM)까지만 탐색하며 합이 최소인 두 수를 찾습니다. (KOI 2011)
-
[BOJ] 11047 | 동전 0
각 동전이 이전 동전의 배수라는 조건을 이용해, 큰 동전부터 사용하는 그리디로 O(N)에 최소 개수를 구합니다.
-
[BOJ] 2294 | 동전 2
동전 1의 풀이를 확장해, 금액별 최소 동전 개수를 DP로 갱신하고 만들 수 없는 경우를 처리합니다.
-
[BOJ] 1451 | 직사각형으로 나누기
직사각형을 셋으로 나누는 6가지 경우를 모두 따져보고, 2차원 구간 합으로 각 넓이를 O(1)에 계산해 최댓값을 찾습니다.
-
[BOJ] 2293 | 동전 1
1차원 DP로 메모리 초과를 피하면서, 동전별로 금액 1~k를 갱신해 O(nk)에 경우의 수를 구합니다.