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

2주차 계획

개요

2주차(1. 8~ 1. 14)의 계획입니다.

• 10장 탐욕법
  • 문제: MATCHORDER
  • 문제: LUNCHBOX
  • 문제: STRJOIN
  • 문제: MINASTIRITH
• 11장 조합 탐색
  • 문제: BOARDCOVER2
  • 문제: ALLERGY
  • 문제: KAKURO2

---

10장 탐욕법

문제: MATCHORDER

최대한 아슬아슬하게 승리하는 것이 최적임을 알면 구현하기는 쉽습니다.

문제

코드

문제: LUNCHBOX

도시락을 먹는데 오래 걸리는 사람을 먼저 전자레인지에 데워줍시다.

문제

코드

문제: STRJOIN

1. 문자열 중 가장 길이가 작은 문자열 2개를 택해서 합칩니다.
2. 두 문자열의 길이 합을 최종 $sum$에 더합니다.
3. 합친 문자열은 하나의 새로운 문자열로 간주합니다.
4. 이 과정을 문자열이 하나만 남을 때까지 반복합니다.

허프만 코드를 각색한 그리디 알고리즘 문제입니다.

문제

코드

문제: MINASTIRITH

선분 커버 문제의 어려운 변형 문제입니다.

문제

코드

포스트

---

11장 조합 탐색

문제: BOARDCOVER2

완전탐색과 가지치기를 이용하는 문제입니다. 엄청 어려웠던 문제입니다. 이게 난이도 하..?

문제

코드

포스트

문제: ALLERGY

이 또한 완전탐색과 가지치기를 이용하는 문제입니다. 알고리즘 구상이 BOARDCOVER2와 비슷해서 그나마 쉽게 구현한 것 같습니다.

문제

코드

포스트

문제: KAKURO2

제약 전파 문제(CSP)의 일종인 카쿠로를 푸는 프로그램을 작성합니다.

문제

코드

포스트