Aerae’s blog

Intro 원래는 UCPC 2024에 도전했다가 뜨거운 실패의 맛을 보고, 팀도 깨져서 올해 ICPC는 포기하고 팀 대회는 군대나 다녀와서 시작할 생각이었습니다. 하지만… 우연히 평소 알고만 지내던 AlKon 동아리 2학년 motsuni04에게 연락이 왔습니다. (이 때는 몰랐지만) 작년 ICPC 팀원이었던 s6xybr8in님이 군입대를 하게 되셔서 제가 들어오게 되었습니다. 든든한 버스기사 yookwi도 합류해서 팀이 결성되었습니다! 팀연습은 보통 업다운 랜디, USACO나 ICPC 기출셋, Codeforces Div.2 등등 다양하게 하였고, 세종대 pizzaroot랑 팀원 분들도 가끔 같이 연습했었습니다. 공강이 겹치는 시간에 PC방에서 같이 Codeforces 버추얼을 쳤던 기억도 나네요 ㅋㅋ...

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로 옮긴다....