노트알고리즘 문제 풀이 접근법
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).