3주차 계획 개요 3주차(1. 15~ 1. 21)의 계획입니다. 12장 최적화 문제 결정 문제로 바꿔 풀기 문제: DARPA 문제: ARCTIC 문제: CANADATRIP 문제: WITHDRAWAL 12장 최적화 문제 결정 문제로 바꿔 풀기 문제: DARPA 알고리즘 문제 ...

문제 $(0,0)$을 중심으로 하는 반지름 $8$인 원 $C$가 있다. $n$개의 원 $C’$의 좌표와 반지름 $y_i, x_i, r_i$이 추가로 제공된다. 추가로 제공되는 원 $C’$로 원 $C$의 둘레를 전부 감싸려고 할 때, 최소로 필요한 $C’$의 개수를 구하시오, 단, 구할 수 없으면 IMPOSSIBLE를 출력한다. 원 $C’$의 중심...

2주차 계획 개요 2주차(1. 8~ 1. 14)의 계획입니다. 10장 탐욕법 문제: MATCHORDER 문제: LUNCHBOX 문제: STRJOIN 문제: MINASTIRITH 11장 조합 탐색 문제: BOARDCOVER2 문제: ALLERGY ...

문제 곡의 수 $n(1 \leq n \leq 50)$, 실행시간(분) $k(1 \leq k \leq 1000000)$, 좋아하는 곡 개수 $m(1 \leq m \leq 10)$ 각 곡의 길이 $Length[0…n-1], Length_i(1 \leq Length_i \leq 4 , Length_i \text{는 정수})$ 곡 재생이 끝난 후 다음 곡...

문제 다음과 같은 조건이 주어졌을 때, 얻을 수 있는 최대한의 선호도를 구하시오. 초밥의 종류 $n(1 \leq n \leq 20)$개와 예산 $m(1 \leq m \leq 2^{32} - 1)$와 $price[1…n]$, $preference[1…n]$ 이 주어집니다. $price(100 \leq price \leq 20000)$이고 100의 ...

1주차 계획 개요 1주차(1. 2~ 1. 7)의 계획입니다. 9장 DP 활용 조합 게임 문제: TICTACTOE 문제: NUMBERGAME 문제: BLOCKGAME 반복적 동적 계획법 ...

목표 알고리즘 문제 해결 전략 끝내보기 알고리즘에서 유명한 책 알고리즘 문제 해결 전략을 끝까지 공부하려고 합니다. 현재 남은 챕터는 다음과 같습니다. 알고리즘 설계 패러다임 9장 DP 활용 10장 탐욕법 11장 조합 탐색 12장 최적화 문제 결정 문제로 바꿔 풀기 유명한 ...

문제 문자열 $k(1 \leq k \leq 15)$개를 입력을 받아서, 해당 문자열을 한 줄로 모두 포함하는 가장 짧은 문자열 하나를 출력합니다. $length(k):1 \leq k \leq 40$ 문제 링크 서론 이번에는 입력이 문자열 여러 개인 경우에 대해서 Dynamic programming을 적용해보려고 합니다. 알고리즘 구상 문...

문제 최대 15자리 정수 $e$와 정수 $k(2 \leq k \leq 20)$가 주어졌을때, $e$의 각 자리를 바꾼 $e’$의 개수를 세는 문제입니다. $e’$는 다음과 같은 조건이 있습니다. $e’ < e$ $e’ \mod k = 0$ 문제 링크 서론 이번에는 입력이 순열인 경우에 대해서 Dynamic programming...

문제 중복되는 $LIS$ (Longest Increasing subsequence) 중, 사전 순으로 정렬했을 때 중복되는 $k$번째의 $LIS$를 구하는 문제입니다. 문제 링크 서론 지금까지 DP를 이용하여 최댓값이나 최솟값을 구하는 문제를 풀어보았습니다. 하지만, 최댓값이나 최솟값이 아닌 k번째의 답을 계산하는건 어떨까요? 이럴 때에도 ...