2026-07-31 TIL (109일차)

알고리즘 문제 5선 — 코드 이전의 사고 과정

풀이 코드는 결과물일 뿐이고, 실제로 실력이 되는 건 “이 문제를 왜 이 유형으로 판단했는가” 입니다. 오늘은 각 문제를 만났을 때 머릿속에서 어떤 질문을 어떤 순서로 던졌는지만 기록합니다.

---

0. 코드를 쓰기 전에 항상 거치는 6단계

단계	하는 일	산출물
①	제한 조건에서 연산 예산을 계산한다	“$N \le 10^5$이니 $O(N \log N)$까지 허용”
②	구하는 것을 한 문장으로 쓴다	개수? 최소값? 목록? 가능 여부?
③	문제의 단어를 알고리즘의 단어로 번역한다	“연합” → 연결 요소, “하루 한 곳” → 매칭
④	유형 후보를 2개 이상 세운다	하나만 떠올리면 그게 맞는지 검증할 수 없다
⑤	작은 예제를 손으로 돌려본다	규칙 확인 + 경계 케이스 발견
⑥	반례를 만들어 본다	통과하면 구현 시작, 깨지면 ④로 복귀

①과 ⑥을 건너뛰는 게 대부분의 실패 원인입니다. ①을 안 하면 시간 초과, ⑥을 안 하면 오답입니다.

---

1. 인구 이동 — “무엇이 하루인가”를 먼저 정의한다

밑줄 친 문장: “국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라들을 오늘 하루 동안은 연합이라고 합니다.”

번역: 연합 = 조건부 간선(인구차가 L~R)으로 연결된 연결 요소. 즉 이 문제는 격자로 위장한 그래프 탐색입니다. 연결 요소를 찾는 도구는 BFS / DFS / Union-Find 세 가지뿐이므로, 여기서 후보가 정해집니다.

스스로 던진 질문 순서

1. 무엇을 세는가? → 날짜. 그러면 “하루”를 코드로 정의해야 합니다. 이게 이 문제의 전부입니다.
2. 하루의 정의는? → 문제 2번 조건이 답을 줍니다. “열어야 하는 국경선이 모두 열렸다면, 인구 이동을 시작합니다.” → ① 모든 연합을 먼저 찾고 → ② 그다음 평균을 낸다. 두 단계가 섞이면 안 됩니다.
3. 평균의 기준값은 언제 시점의 인구수인가? → 그날 시작 시점입니다. 그렇다면 A 연합을 갱신한 값이 B 연합 판정에 영향을 주면 안 됩니다. → “그룹을 전부 모은 뒤 한 번에 갱신” 이라는 설계가 여기서 나옵니다.
4. 언제 끝나는가? → “더 이상 인구 이동이 없을 때” 를 코드 조건으로 번역하면 크기 2 이상인 연합이 하루 동안 하나도 생기지 않았을 때입니다. 혼자 있는 나라는 이동이 아닙니다.
5. 시간이 되는가? → 하루에 격자 전체를 훑으니 $O(N^2) = 2{,}500$, 최대 2,000일이면 500만. 여유롭습니다. → 최적화를 고민할 필요가 없으니 문제 서술 그대로 정직하게 시뮬레이션한다는 결론.

후보 비교: 왜 BFS인가

도구	판단
BFS	연결 요소만 찾으면 되므로 방문 순서는 무관. 격자 최대 2,500칸이라 재귀 깊이 걱정이 없음 → 채택
DFS(재귀)	동작은 같지만 최악 깊이 2,500. 가능하긴 하나 굳이 스택 위험을 안을 이유가 없음
Union-Find	매일 조건이 달라져 간선을 새로 만들어야 함. 자료구조를 매일 초기화하므로 이득이 없음 → 탈락

도구 선택의 근거가 “익숙해서”가 아니라 “매일 간선이 변하니 Union-Find는 이점이 없다” 처럼 문제 특성에서 나와야 합니다.

손으로 먼저 확인할 케이스: 예제 2(L=40)는 아무 국경선도 열리지 않아 답이 0입니다. 종료 조건이 첫날부터 작동하는지 검증하는 케이스이므로, 구현 전에 이걸 기준으로 삼습니다.

구현 전 결정해야 할 것 3가지

• 방문 배열을 매일 새로 만들 것인가, 재사용할 것인가 (매일 새로 만드는 쪽이 버그가 없음)
• 그룹의 좌표를 어디에 모아둘 것인가 (합계와 좌표 목록을 동시에 들고 있어야 갱신이 한 번에 끝남)
• 평균은 정수 나눗셈 → 부호 없는 타입과 섞이지 않게 주의

---

2. 순회강연 — 그리디는 “정렬 기준 후보”를 두 개 세운다

밑줄 친 문장: “이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있습니다.”

번역: 각 강연에 서로 다른 날 하나씩, 그것도 기한 이하의 날을 배정하는 문제. 즉 스케줄링/매칭입니다.

스스로 던진 질문 순서

1. 완전 탐색이 되나? → $n \le 10{,}000$이므로 $2^n$은 즉시 탈락. 1단계에서 후보가 하나 지워집니다.
2. DP인가? → 상태를 “날짜 × 선택 여부”로 잡으면 $10^4 \times 10^4 = 10^8$이고, 무엇보다 상태 정의가 자연스럽게 안 나옵니다. 상태 정의가 어렵다는 건 DP가 아닐 신호입니다.
3. 그리디라면 무엇을 기준으로 정렬하나? → 여기서 후보를 반드시 두 개 세웁니다.

후보	전략	정당성	문제점
A. 강연료 내림차순	비싼 강연부터, 기한 이하의 가장 늦은 빈 날에 배정	앞날은 기한이 짧은 강연에게 양보해야 하므로 “가장 늦은 날”	빈 날을 선형 탐색하면 $O(nd) = 10^8$ (위험)
B. 기한 오름차순	순서대로 담다가 개수가 기한을 넘으면 가장 싼 것을 버림	아래 교환 논증	없음. $O(n \log n)$

1. B의 정당성을 말로 설명할 수 있는가? (이걸 못 하면 그리디를 쓰면 안 됩니다)
   • 기한이 d인 시점까지 처리할 수 있는 강연은 최대 d개다.
   • 담은 개수가 d를 초과하면 무엇이든 하나는 반드시 버려야 한다.
   • 어느 것을 버려도 “개수 제약”은 똑같이 만족되고, 달라지는 건 총 이익뿐이다.
   • 따라서 가장 싼 것을 버리는 게 항상 최선이다. → 최소값을 반복 추출해야 하므로 최소 힙이 필요하다.
2. 그리디를 의심하는 마지막 질문: “지금의 선택이 나중의 선택 가능성을 제약하는가?” → 개수만 제약하고 어느 것을 버려도 결과 구조가 같으므로 제약하지 않습니다. → DP가 아니라 그리디 확정.

사고 습관으로 남길 것

그리디에서 정렬 기준이 하나만 떠올랐다면, 그건 검증되지 않은 직감입니다. 반드시 다른 기준을 하나 더 세워 비교하고, 문제 예시로 두 기준을 모두 추적해 봐야 합니다. (강연료 기준 / 기한 기준 / 강연료÷기한 기준 등)

---

3. 용돈 관리 — “최소값”이 보이면 판정 문제로 바꿔본다

밑줄 친 문장: “현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였습니다.”

번역: 최적화 문제. 그런데 K가 하나 주어지면 “M번 이내로 가능한가?”는 한 번 훑어서 판정 가능합니다. 이 조합이 매개변수 탐색의 신호입니다.

매개변수 탐색을 의심하는 3박자

신호	이 문제에서
“최소값 / 최대값을 구하라”	최소 인출 금액 K
답의 범위가 매우 넓다	K는 1 ~ 10억 → 하나씩 시도 불가
답을 하나 주면 검증이 쉽다	K가 정해지면 인출 횟수를 $O(N)$에 계산 가능

스스로 던진 질문 순서

1. K를 1부터 늘려가며 검사하면? → 합계가 최대 $10^9$이므로 불가능. 다른 방법이 필요합니다.
2. 단조성이 있는가? (이분 탐색의 유일한 관문) → K가 커지면 한 번 인출로 더 오래 버티므로 인출 횟수는 줄어들거나 같습니다. 단조 감소 확인 → 이분 탐색 성립.
3. 판정 함수를 어떻게 만드나? → “K가 고정일 때 인출 횟수를 최소로 하는 전략”이 필요합니다. 답은 명백히 “모자랄 때만 인출한다” 입니다. 미리 인출해봐야 손해일 뿐이므로 이 그리디는 증명이 필요 없을 정도로 자명합니다.
4. 탐색 범위를 어떻게 잡나? (여기서 가장 많이 틀립니다)
   • 하한 = max(money_list) — 하루 사용액보다 적게 인출하면 그날 자체를 버틸 수 없어 판정 함수가 무의미해집니다. 1부터 시작하면 안 됩니다.
   • 상한 = sum(money_list) — 전액을 한 번에 뽑으면 인출 1번으로 끝나므로 반드시 가능합니다.
5. 조건이 == M인가 <= M인가? → 문제 문장을 다시 읽습니다. “K로 계산한 총 인출 횟수가 M번보다 적다면 … 정확히 M번을 맞출 수 있다고 가정합니다.” → <= M. 이걸 ==로 두면 답을 영원히 못 찾습니다.

사고 습관으로 남길 것

이분 탐색은 범위 / 판정 함수 / 좁히는 방향 세 가지만 결정하면 끝입니다. 그런데 셋 중 범위 설정에서 가장 많이 실수하므로, “하한이 왜 그 값인가”를 문장으로 설명할 수 있어야 합니다.

---

4. 수학숙제 — 제한 조건이 곧 정답 힌트다

밑줄 친 문장: “숫자의 자릿수가 매우 길어질 수 있으므로, 각 숫자는 문자열(string) 형태로 배열에 담아 반환해야 합니다.”

번역: 이 한 줄은 “정수로 변환하지 말라” 는 지시이고, 동시에 “비교 방법을 직접 만들어라” 는 뜻입니다. 즉 이 문제의 난이도는 파싱이 아니라 정렬 기준 설계에 있습니다.

문자열 문제를 만나면 확정할 3가지

결정할 것	이 문제의 답	근거가 되는 문장
① 토큰의 경계	연속된 숫자를 끝까지 하나로	“가능한 가장 큰 숫자를 찾아야 합니다. 모든 숫자의 앞과 뒤에 문자가 있거나…”
② 정규화 규칙	선행 0 제거, 전부 0이면 "0"	“숫자의 앞에 0이 있는 경우에는 모두 생략”, 예시 00 → 0
③ 비교 규칙	길이 우선 → 같으면 사전순	“비내림차순(오름차순)으로 정리” + 문자열 반환 제약

스스로 던진 질문 순서

1. 한 글자씩 처리해도 되나? → 안 됩니다. 3456을 3, 4, 5, 6으로 쪼개게 됩니다. “가장 큰 숫자”는 최대 길이 확장을 의미합니다.
2. 사전순 정렬로 되나? → 안 됩니다. "10" < "9"가 되어버립니다. 그럼 어떻게?
3. 선행 0을 제거하고 나면 무엇이 보장되나? → 길이가 곧 자릿수가 됩니다. 자릿수가 다르면 큰 쪽이 무조건 크고, 같으면 앞자리부터 비교하면 되므로 사전순 비교가 그대로 수치 비교와 일치합니다.
4. 순서가 중요한가? → 매우 중요합니다. 정규화(선행 0 제거) → 비교 순서를 바꾸면 "007"이 3자리로 잡혀 비교가 깨집니다.
5. 경계 케이스는? → "000". 선행 0을 다 지우면 빈 문자열이 되므로 명시적으로 "0"으로 분기해야 합니다. 예제 3이 정확히 이 케이스를 노리고 있습니다.

사고 습관으로 남길 것

제한 조건에 이유가 붙은 문장(“자릿수가 매우 길어질 수 있으므로”)이 있으면, 그건 출제자가 함정을 알려주는 것입니다. 그 문장이 어떤 구현을 금지하는지 먼저 생각합니다.

---

5. 꽃길 — 경우의 수를 먼저 계산해서 완전 탐색을 허가받는다

밑줄 친 문장: “N은 화단의 한 변의 길이이며, 6 이상 10 이하인 정수입니다.” / “꽃의 씨앗이 세 개밖에 없으며”

번역: N이 극단적으로 작고 고를 개수가 고정 → 완전 탐색/백트래킹을 의심하고, 계산으로 확인합니다.

스스로 던진 질문 순서

1. 후보 위치가 몇 개인가? → 꽃잎이 화단을 벗어나면 죽으므로 중심은 테두리에 올 수 없습니다. 실제 후보는 내부 $(N-2)^2$, 최대 $8 \times 8 = 64$칸. 문제의 제약이 후보를 알아서 줄여줍니다.
2. 경우의 수는? → $\binom{64}{3} = 41{,}664$. 배치마다 15칸을 검사해도 60만 연산. → 완전 탐색 허가. 여기서 “최적화를 고민하지 않아도 된다”가 확정되므로 남은 일은 구현 정확도뿐입니다.
3. 조합인가 순열인가? → 꽃 세 송이는 구별되지 않습니다. 따라서 조합이고, 인덱스가 증가하는 방향으로만 고릅니다. 이걸 놓치면 같은 배치를 $3! = 6$번 세게 됩니다.
4. 상태를 무엇으로 정의하나? (백트래킹의 핵심) → 세 가지입니다.
   • 진행도: 지금까지 몇 송이를 심었나 + 어디까지 후보를 검토했나
   • 점유 정보: 어떤 칸이 이미 꽃잎에 쓰였나
   • 누적값: 지금까지의 비용
5. 가지치기가 가능한가? → 가격이 모두 0 이상이라 비용은 절대 줄어들지 않습니다. 따라서 현재 비용이 이미 최선보다 크거나 같으면 그 아래는 볼 필요가 없습니다. “값이 단조 증가한다”는 성질이 가지치기의 근거입니다.
6. 실패 조건을 어디서 검사하나? → 문제의 사망 조건 두 개(화단 밖 / 겹침)를 배치 직전 한 함수에서 5칸 전체에 대해 확인합니다. 중심만 검사하면 겹침을 놓칩니다.

사고 습관으로 남길 것

백트래킹은 상태 3요소(진행도·점유·누적값) 를 먼저 말로 정의하고, 그다음 “되돌려야 하는 것의 목록” 을 적습니다. 목록을 적어두면 되돌리기 누락(최다 실수)이 사라집니다.

---

6. 유형별 “확인 질문” 정리

문제를 유형으로 분류한 다음, 그 유형이 성립하는지 검증하는 질문이 따로 있습니다. 분류만 하고 검증을 안 하면 틀립니다.

의심 유형	반드시 던져야 하는 질문
완전 탐색	경우의 수를 수식으로 쓰고 숫자를 대입했는가?
백트래킹	가지치기 근거가 되는 단조성이 있는가? 되돌릴 대상을 목록화했는가?
그리디	정렬 기준 후보를 2개 이상 세웠는가? 교환 논증을 말로 할 수 있는가? 반례를 찾아봤는가?
DP	상태를 한 문장으로 정의했는가? 부분 문제가 실제로 겹치는가?
이분 탐색	단조성이 있는가? 하한·상한이 왜 그 값인지 설명할 수 있는가?
BFS/DFS	무엇이 정점이고 무엇이 간선인가? 방문 처리 시점이 맞는가?
정렬	정렬 기준이 여러 개인가? 비교자가 엄격한 약한 순서를 만족하는가?

---

7. 막혔을 때의 탈출 순서

1. 제한 조건을 다시 읽는다. 대부분의 힌트는 여기 있고, 특히 “~하므로” 가 붙은 문장은 함정 경고입니다.
2. 예제를 손으로 끝까지 돌린다. 규칙을 오해했는지, 경계 케이스를 놓쳤는지가 여기서 드러납니다.
3. 완전 탐색으로 되돌아간다. 정답을 보장하는 풀이를 먼저 세우고, 그다음 어디가 낭비인지 찾습니다. 낭비가 중복 계산이면 DP, 불가능한 분기면 백트래킹, 규칙으로 대체 가능하면 그리디입니다.
4. 구하는 것을 바꿔본다. “최소값을 구하라”를 “이 값이 가능한가”로 바꾸면 이분 탐색이 되고, “경우의 수”를 “마지막 선택이 무엇인가”로 바꾸면 DP 점화식이 나옵니다.
5. 문제의 단어를 그래프 용어로 번역해본다. “연합”, “연결”, “그룹”, “도달”이 보이면 대개 탐색 문제입니다.

오늘의 결론: 코드를 빨리 쓰는 능력보다, 코드를 쓰기 전에 유형을 확정하고 그 근거를 말로 설명하는 능력이 실제 실력입니다. 근거를 말로 못 하면 그건 외운 것이고, 조금만 변형된 문제에서 무너집니다.