🧠 Problem Solving (with Baekjoon & BarkingDog)

코딩테스트 대비를 위한 알고리즘 문제풀이 정리 저장소입니다.
바킹독 알고리즘 시리즈를 기반으로 유형별로 학습하고,
시간 제한, 회독 기록, 오답 복습을 통해 실력을 체계적으로 향상시킵니다.

목표는 단순히 BOJ 티어를 올리는 것이 아닙니다.
“반복 학습”을 통해 실전에서 통과 가능한 실력을 기르고, 실제 기업 코딩테스트 합격을 목표로 합니다.

---

🎯 풀이 목표 시간

난이도	목표 시간
실버	⏱️ 10분 이내
골드	⏱️ 30분 이내

모든 문제는 해당 시간 내에 풀이를 완료해야
“오답이 성공적으로 해결되었다”고 판단합니다.

---

🧩 진도표 상태 이모지 가이드

상태 구분	기호	설명
🔄 진행중	🔄	현재 회독 중인 챕터
✅ 1회독 완료	✅	1회독 완료
✅✅ 2회독 완료	✅✅	2회독까지 완료
🔁 다시 복습 필요	🔁	틀린 문제 많아서 재복습 예정
🚀 완전 숙지	🚀	빠르게 풀이 가능, 복습 불필요
⏳ 미시작	⏳	아직 시작하지 않음

세부 상태 이모지

🥈 실버 난이도 풀이 완료 / 🥇 골드 난이도 풀이 완료 / 💎 플래티넘 난이도 풀이 완료

---

📌 바킹독 알고리즘 진도표

No.	챕터	주제	한 줄 정의	상태	1회독	2회독	3회독
01	0x05	스택	지금 처리할 수 없는 것들을 보류하고, 나중에 다시 꺼내는 사고의 기술	✅	🥈🥇💎
02	0x06	큐	들어온 순서를 그대로 존중해, 먼저 온 것을 먼저 처리	✅	🚀
03	0x07	덱	스택과 큐를 모두 일반화한(슈퍼셋) 자료구조	✅	🥈🥇💎
04	0x09	BFS	동시에 퍼져나가는 물결 - connected_components,deqth 제한 bfs, multi-source bfs, frontier bfs / 완료 : 1926,2174,1679,1012,2583,2468,6593,2667,2206,7569,2573,2146,16920,3197,9328	🔄	🥈 🥇
05	0x0A	DFS	한 갈래를 끝까지 내려가 보는 탐험	⏳
06	0x0B	재귀		⏳
07	0x0D	시뮬레이션		⏳
08	0x0C	백트래킹	가능성의 숲을 내려가며, 막힌 가지는 즉시 잘라 되돌아오는 탐험 - 15649,9663	🔄
09	0x11	그리디	지금 가장 맛있는 한 입이, 끝까지도 최선일 때만 통하는 즉결 선택	⏳
10	0x13	이분 탐색	정답을 반씩 접어 가며, 가능한 영역을 절반으로 베어내는 탐색	⏳
11	0x14	투 포인터		⏳
12	0x15	해시		⏳
13	0x10	DP	문제를 쪼개 기억하고, 같은 질문엔 같은 답으로 되갚는 메모의 기술 : 1463,9095,2579,1149,11726	🔄
14	0x18	그래프		⏳
15	0x19	트리		⏳
16	0x1A	위상 정렬		⏳
17	0x1B	MST		⏳
18	0x1D	다익스트라	BFS가 동심원처럼 “한 층씩” 퍼져나간다면, 다익스트라는 지형의 고저에 따라 “거리 파동이 굴절되며” 퍼져나가는 모습 - Multi-source Dijkstra / 1753, 1504, 1261, 11779, 1238, 1916, 17835, 20183, 24042 - 다시	🔄	🥈 🥇
19	0x1C	플로이드 - 위셜		⏳
20	0x1E	KMP		⏳
21	0x1F	트라이		⏳

---

📚 2회독 이후 추천 문제집

유형 학습이 어느 정도 정리되면, 실전 감각을 높이기 위해 아래 문제집들을 풀 예정입니다.

• 🔗 삼성 SW 역량 테스트 기출 문제집

  • 삼성 A형 스타일 (구현, 시뮬레이션, BFS 등)

• 🔗 IT기업/대기업 기출 유사 문제집 (지속 업데이트)

  • 카카오, 라인, SK, 현대오토에버 등 실전 스타일 문제

이 문제집들은 시간 제한을 더욱 엄격히 적용해 실전처럼 풀이할 예정입니다.

---

🧑‍💻 Author

forwarder1121

---

🧭 코딩테스트 문제 풀이의 본질

모든 문제는 ‘상태 공간’을 정의하고, 그 안을 효율적으로 탐색하는 일이다.

---

🚀 문제 풀이 5단계 사고 프레임워크

단계	핵심 질문	핵심 개념
① 상태 정의	“지금 상황을 표현하려면 어떤 정보가 필요하지?”	문제를 수학적·논리적으로 표현 (위치, 선택, 남은 자원 등)
② 상태 전이	“이 상태에서 다음으로 갈 수 있는 선택은 뭐야?”	가능한 모든 다음 상태를 생성 (DFS·BFS·DP의 공통 기반)
③ 종료 조건	“언제 탐색을 멈출까?”	목표 도달 or 더 진행 불가 시 종료 (leaf node)
④ 가지치기	“이 경로는 더 볼 필요 없지 않나?”	불가능·비효율 상태는 미리 제거 (탐색량 축소 핵심)
⑤ 탐색 전략	“상태 공간을 어떤 순서로 돌까?”	DFS / BFS / DP / Greedy / Binary Search 등 전략 선택

---

🎯 요약: “상태를 정의하고 → 전이 규칙을 세우고 → 종료 조건과 가지치기를 넣고 → 적절한 탐색 전략으로 순회한다.”

---

참고

🧠 코테 사고법 (Thinking Patterns) 8종 정리

---

1️⃣ 거꾸로 생각하기 (Reverse Thinking)

출발점·도착점을 반대로 보면 계산이 단순해진다.
예시: BOJ 17835 면접보는 승범이네, BOJ 11779 최소비용 구하기 2

---

2️⃣ 대칭성 활용 (Symmetry)

절반만 계산하고 반대편은 그대로 적용한다.
예시: BOJ 1213 팰린드롬 만들기, BOJ 10942 팰린드롬?

---

3️⃣ 상태 고정 (Fix a Variable)

한 변수를 고정시키고 나머지를 탐색한다.
예시: BOJ 1806 부분합, BOJ 2470 두 용액

---

4️⃣ 경계값 사고 (Boundary / Parametric Thinking)

정답이 아니라 조건을 만족하는 최소/최대 경계값을 찾는다.
예시: BOJ 1654 랜선 자르기, BOJ 2805 나무 자르기, BOJ 1300 K번째 수

---

5️⃣ 전환 (Transformation)

문제의 구조를 다른 형태로 바꿔 단순화한다.
예시: BOJ 1916 최소비용 구하기, BOJ 1932 정수 삼각형, BOJ 2268 구간합 세그트리

---

6️⃣ 누적/차이 사고 (Prefix–Diff)

이미 계산한 값을 재활용해 중복 계산을 피한다.
예시: BOJ 11659 구간합, BOJ 10986 나머지 합, BOJ 2042 구간합 구하기

---

7️⃣ 그래프적 사고 (Graph Modeling)

관계를 그래프 구조로 모델링하면 풀이가 명확해진다.
예시: BOJ 1516 게임 개발, BOJ 2252 줄 세우기, BOJ 2667 단지번호붙이기

---

8️⃣ 역전 / 역추적 (Reverse Simulation)

결과 상태에서 거꾸로 과정을 복원한다.
예시: BOJ 11779 최소비용 구하기 2, BOJ 13913 숨바꼭질 4, BOJ 12852 1로 만들기 2

---

Memo

“멀티소스 다익스트라는 동일한 위상(phase) 을 가진 출발점 집합에서만 가능하다.
즉, ‘출발점의 정체성’이 결과에 영향을 미치지 않아야 한다.
그래프를 뒤집으면 면접장 집합이 이런 동등한 위상을 가지므로,
한 번의 다익스트라로 모든 노드의 최소 거리를 계산할 수 있다.”