[2024 동계 모각코] 3주차 계획

3주차 계획

개요

3주차(1. 15~ 1. 21)의 계획입니다.

• 12장 최적화 문제 결정 문제로 바꿔 풀기
  • 문제: DARPA
  • 문제: ARCTIC
  • 문제: CANADATRIP
  • 문제: WITHDRAWAL

---

12장 최적화 문제 결정 문제로 바꿔 풀기

문제: DARPA

알고리즘 문제 Aggressive Cows와 유사한 문제입니다. 여러 개의 요소 중 최소 값을 최대화 하는 문제입니다.

DP로도 풀 수 있지만, 이번에 배우는 Greedy + 이분탐색을 써서 풀 수 있습니다.

문제

코드

문제: ARCTIC

$Vertex$들과 각 $Vertex$간의 거리가 주어지면, 이들을 연결 그래프로 만들기 위한 최소한의 $edge$의 길이를 구하는 문제입니다.

이 또한 최소 값을 최대화하는 문제로, Greedy + 이분탐색으로 풀 수 있습니다.

하지만 그래프 문제로도 볼 수 있기에 Kruscal의 MST, Prim 알고리즘 등으로 더 빠르게! 풀 수 있습니다.

문제

이분탐색 코드

Prim 알고리즘 코드

문제: CANADATRIP

여러 개의 정렬된 수열에서 k번째 원소를 찾는 유형의 알고리즘 문제입니다.

완전탐색으로는 무리가 있기에 이분 탐색을 이용하여 시간복잡도를 줄일 수 있습니다.

문제

코드

문제: WITHDRAWAL

파라메트릭 서치(최적화 문제를 결정 문제로 바꿔 풀기)를 이용해서 답을 찾는 문제입니다.

비율이 큰 것부터 제외하는 식으로 그리디로 쉽게 풀릴 줄 알았으나, 이런 방식으로는 풀면 안되는 문제입니다.

문제

코드