노트알고리즘 문제 풀이 접근법
Problem Solving Approach
CS#algorithm · 연결된 개념 8개
쉽게 말하면
가구를 조립하기 전에 완성 사진을 보고, 부품을 늘어놓고, 설명서 순서를 훑어본 뒤 드라이버를 드는 습관 같아요. 문제 풀이 접근법도 바로 코드부터 쓰다 엉뚱한 문제를 푸는 일을 막아 줘요.
비유의 한계 설명서대로면 끝나는 조립과 달리 문제 풀이는 막히는 단계가 있어요. 그때는 핵심 어려움을 잠시 빼고 더 쉬운 문제를 푼 뒤 다시 끼워 넣고, 다 푼 뒤에도 돌아보며 리팩터링해요.
낯선 문제를 만났을 때 바로 코드를 쓰기보다 따르는 다섯 단계. 수학자 폴리아(George Pólya)의 『어떻게 문제를 풀 것인가』(How to Solve It)에서 이어지는 흐름이다.
- 문제 이해하기: 내 말로 다시 말할 수 있는가? 입력과 출력은 무엇인가? 입력만으로 출력을 정할 정보가 충분한가? 중요한 데이터에 무슨 이름을 붙일까?
- 구체적인 예 살펴보기: 간단한 예에서 시작해 복잡한 예로 넓힌다. 빈 입력과 잘못된 입력도 따져 본다
- 분해하기: 필요한 단계를 말이나 의사 코드(Pseudocode)로 적는다. 코드를 쓰기 전에 오해를 걸러 낸다
- 풀거나 단순화하기: 풀 수 있으면 푼다. 막히면 핵심 어려움을 잠시 무시하고 더 쉬운 문제를 푼 뒤, 그 어려움을 다시 끼워 넣는다
- 돌아보고 리팩터링하기: 결과가 맞는가? 다르게 풀 수 있었나? 한눈에 이해되나? 다른 문제에도 쓸 수 있나? 더 빠르게 할 수 있나? 남들은 어떻게 풀었나?
자주 쓰는 풀이 패턴
- 빈도수 세기 패턴: 값의 빈도를 객체·Map에 모은다
- 투 포인터: 정렬된 배열 양끝이나 같은 방향의 포인터 두 개
- 슬라이딩 윈도우: 연속 구간을 한 칸씩 밀며 이전 계산을 재사용한다
- 분할 정복: 작은 조각으로 나눠 풀고 합친다
- 동적 프로그래밍, 탐욕 알고리즘(Greedy Algorithm), 백트래킹(Backtracking)
패턴은 복잡도를 낮추는 도구다. 디버깅에서 문제를 먼저 정의하는 습관(디버깅 문제 정의 5단계)과 같은 태도이고, 막혔을 때 문제를 줄이는 넷째 단계는 최소 재현과 닮았다.
연결된 개념
이 노트를 가리키는 문서
뜻이 가까운 노트
- 디자인 패턴
반복해서 나타나는 설계 문제에 대한 검증된 해결 구조와 그 이름. 복사해 쓰는 완성 코드가 아니라 객체들이 협력하는 방식을 설명하는 어휘다. 1994년 이른바 GoF(Gang of Four, 네 명의 저자)의 책 『Design Patterns: Elements of Reusable Object-Oriented Software』가 23개 패턴을 정리하며 널리 퍼졌다.
- 러버덕 디버깅
문제를 남에게(혹은 고무 오리에게) 말로 설명하다 보면 스스로 답을 찾게 되는 디버깅 방법.
- 재귀
함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.
- 문제 공간과 해결 공간
문제 공간은 "무엇을 왜 풀어야 하는가"를, 해결 공간은 "어떻게 풀 것인가"를 다루는 영역이다. 둘을 나눠 생각하고, 문제를 충분히 이해한 뒤에 해결책으로 넘어가라는 것이 요점이다.
- 디버깅 포켓 가이드 (개요)
줄리아 에반스가 디버깅의 마음가짐과 구체적인 전략을 한 권에 모은 진(zine).