Intro 이분 탐색 알고리즘은 컴퓨터 공학을 전공하지 않더라도 누구나 교양 시간에 배워봤을 만한 알고리즘입니다. 이분 탐색의 개념 자체는 직관적이지만 응용이 상당히 어렵습니다. 오늘은 이분 탐색과 그 활용에 대해 다뤄보겠습니다. 이분 탐색이란? 이분 탐색이 정확히 무엇일까요? 이분 탐색의 예시로 보통 업-다운 게임을 많이 사용하는데요, 진행자는 $1$부터 $100$까지의 정수 중 하나를 고르고, 질문자는 이 정수를 맞혀야 합니다. 질문자는 매 질문마다 정수를 하나 골라 질문하고, 진행자는 질문자가 고른 정수와 진행자가 고른 정수의 대소관계만을 대답해줍니다....
문제 링크 (2024/9/13 기준) Gold V 문제 읽기 문제가 살짝 난해합니다; $1$초부터 $T$초까지 매 초 $1$번 나무 또는 $2$번 나무에서 하나씩, 총 $T$개의 자두가 떨어집니다. $W$번 이하로 이동하며 떨어지는 자두를 받았을 때의 최댓값을 구해봅시다. 처음 시작은 $1$번 나무입니다. 풀이 제한을 잘 살펴봅시다. $T \leq 1 000$, $W \leq 30$, 나무가 $2$그루 있으니, dp[현재 시간][현재 위치][현재까지 이동한 횟수]로 3차원 DP를 해볼 수 있을 것 같습니다. 우선, DP 테이블에 초깃값들을 채워봅시다. $t$초에 자두가 떨어진 나무의 위치를 $P_t$라고 하면, $1$초에 $1$번 나무에서 시작하니, $DP_{1, 1, 0}=[P_i = 1]$이 되겠고 (편의상 $[c]$는 조건 $c$가 참이면 $1$, 거짓이면 $0$ 값을 가진다고 약속합시다), $1$초에 자두가 떨어지기 전 $2$번 나무로 움직였다면, $DP_{1, 2, 1}=[P_i = 2]$가 됩니다....
문제 링크 (2024/9/12 기준) Silver I 문제 읽기 $N$명의 사람들이 일렬로 서 있습니다. 왼쪽에서 $i$ (단, $1 \leq i < N$)번째 사람까지는 홍팀, 나머지는 청팀으로, 총 $N-1$가지 방법으로 팀을 나눌 수 있습니다. 이때, 각 팀에서 힘이 가장 센 사람이 힘을 겨루어, 두 사람 중 힘이 더 센 사람이 포함된 팀이 승리하게 됩니다. (무승부일 때는 어느 팀도 승리하지 않습니다.) 둘 중 어느 팀이 승리할 확률이 더 높을까요? 풀이 일단, 전체 경우의 수는 $N-1$로 고정되어 있습니다....
문제 링크 (2024/9/10 기준) Gold III 문제 읽기 하노이 탑 변형 문제입니다. 대신 기둥 D가 추가되었고, 기둥 D에 한 번 옮기면 다시 뺄 수 없습니다. 이외에는 기존 하노이 탑과 규칙이 동일합니다. $N$개의 원판을 기둥 D에 옮기는 최소 이동 횟수와, 그러한 이동 방법을 하나 찾아봅시다. 예시 편의를 위해 초기 상태에서의 위로부터 $N$번째 원판을 원판 $N$이라고 하겠습니다. $N=2$일 때, A에 있는 원판 $1$을 B로 옮긴다. A에 있는 원판 $2$를 D로 옮긴다. B에 있는 원판 $1$을 D로 옮긴다....
문제 링크 (2024/9/9 기준) Gold III 문제 읽기 꽃이 $N$종류 주어집니다. 각각의 꽃은 피는 날과 지는 날이 각각 $MM\ DD$꼴로 주어지고, 최소한의 종류의 꽃으로 $3$월 $1$일부터 $11$월 $31$일까지 매일 적어도 한 종류의 꽃이 피어있도록 배치해봅시다. 단, $d$일에 꽃이 지는 경우, $d$일에는 꽃이 피어있지 않았음에 유의합시다. 예시 4 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10 예제 1입니다. $4$종류의 꽃이 주어졌고, 이 중 $1$월 $1$일부터 $6$월 $30$일까지 피는 꽃과, $6$월 $10$일부터 $12$월 $10$일에 지는 꽃 $2$개를 선택하여 조건을 만족시킬 수 있습니다....