(코테) 백준_유형별 풀이 파악하는 팁

✅ 실전에서 문제 유형을 빠르게 분류하는 핵심 질문 5단계

🧠 문제를 받았을 때 바로 자문

---

1. ❓최단 거리, 최소 이동 횟수 찾는 문제인가?

• 예시 문장: "가장 빠른", "가장 적은 이동", "몇 초 후에 도착"
• ✅ BFS (Queue) 사용
• ✳️ 변형되면 → 다익스트라 (가중치 그래프), 0-1 BFS

---

2. ❓모든 경우의 수를 구하거나 찾는 문제인가?

• 예시 문장: "모든 조합", "모든 순열", "모든 방법"
• ✅ 백트래킹 / DFS / 완전탐색
• ✳️ 조건이 없다면 → 완전탐색
• ✳️ 조건이 있으면 → 백트래킹

---

3. ❓이전에 계산한 결과를 재활용할 수 있는가? (부분 문제 중복)

• 예시 문장: "최대 점수", "최소 비용", "몇 가지 방법", "이전 값 기반"
• ✅ DP (Dynamic Programming)
• ✳️ 점화식 도출 가능 여부가 핵심

---

4. ❓수나 배열을 정렬한 뒤 조건을 만족하는 쌍/구간을 찾는가?

• 예시 문장: "두 수의 합", "구간합", "연속된 부분"
• ✅ 투 포인터 / 이분 탐색 / 누적합 / 슬라이딩 윈도우

---

5. ❓"연결되어 있다", "같은 그룹", "사이클" 같은 단어가 나오는가?

• ✅ 그래프 탐색 (DFS/BFS), 유니온 파인드, MST, 위상 정렬
• ✳️ 방향 그래프 + 순서 = 위상 정렬
• ✳️ 가중치 + 연결 최소 = 크루스칼/프림

---

✅ 입력 조건으로 파악하는 팁

 

입력 크기	추천 알고리즘
N ≤ 10	완전탐색, 백트래킹 (2ⁿ 가능)
N ≤ 100	2차원 DP, Floyd
N ≤ 1000	O(N²) 알고리즘 가능
N ≤ 100,000	O(N log N) (정렬, 투포인터, 이분탐색)
N ≤ 1,000,000	O(N) 알고리즘만 가능

 

---

✅ 예시로 감 잡기

예1:

"수빈이는 걷거나 순간이동해서 동생을 찾아야 한다. 가장 빠르게 찾아갈 수 있는 시간은?"

✔️ "가장 빠르게" → 최단 거리
✅ BFS

---

예2:

"1부터 N까지 중복 없이 M개를 고르는 모든 순열을 구하시오."

✔️ "모든 순열" → 모든 경우 탐색
✅ 백트래킹 + 방문 배열

---

예3:

"배열에서 연속된 수들의 합이 S 이상이 되는 가장 짧은 길이의 부분 수열"

✔️ "연속된", "가장 짧은", "합이 조건 만족"
✅ 투 포인터 / 슬라이딩 윈도우

---

예4:

"가장 긴 증가하는 부분 수열의 길이를 구하라"

✔️ 수열, 길이, 최적해
✅ DP
✳️ 최적화하면 → 이분탐색 + LIS

---

예5:

"도시가 N개 있고 도로가 M개 있다. 모든 도시를 연결하는 최소 비용을 구하시오."

✔️ 그래프 + 최소 연결 비용
✅ MST (크루스칼 or 프림)

---

✅ 정리 요약표

조건/표현	판단 알고리즘
가장 빠른 / 최소 시간	BFS
모든 방법 / 경우의 수	백트래킹, 완전탐색
누적 / 최댓값 / 점화식	DP
정렬 후 구간 탐색	투 포인터, 슬라이딩 윈도우
연결 여부 / 사이클	DFS, 유니온 파인드, MST
"가능한가?" / 최적 조건	이분 탐색 (YES/NO 판단)
문자열 검색	KMP, Z, Trie