알고리즘 문제 접근법

🎯 학습 목표

이 강을 마치면 다음을 할 수 있습니다.

• 낯선 문제를 받았을 때 당황하지 않고 4단계로 체계적으로 접근할 수 있습니다.
• 문제 유형을 보고 어떤 알고리즘 패턴을 적용할지 빠르게 판단할 수 있습니다.
• 면접관에게 사고 과정을 말하면서 풀이하는 Thinking Aloud 기법을 구사할 수 있습니다.
• 막혔을 때 힌트를 요청하거나 방향을 전환하는 전략을 실행할 수 있습니다.

🧩 알고리즘 면접에서 "정답"보다 중요한 것

이 섹션에서는 알고리즘 면접이 코딩 테스트와 어떻게 다른지, 면접관이 진짜 무엇을 보는지 살펴보겠습니다.

온라인 코딩 테스트와 라이브 면접 코딩의 가장 큰 차이점은 면접관이 당신의 화면 앞에 앉아 있다는 것입니다. 이 때문에 전략이 완전히 달라집니다. 코딩 테스트에서는 최종 코드만 평가하지만, 라이브 코딩에서는 문제를 이해하는 방식, 가설을 세우는 방식, 막혔을 때 대처하는 방식까지 모두 평가합니다.

면접관이 알고리즘 문제를 내는 이유는 세 가지입니다. 첫째, 복잡한 문제를 단순화하는 능력. 둘째, 제약 조건을 인식하고 트레이드오프를 판단하는 능력. 셋째, 막혔을 때 포기하지 않고 다른 각도에서 접근하는 회복 탄력성입니다. 30분 안에 완벽한 코드를 작성하지 못해도, 이 세 가지를 보여주면 통과할 수 있습니다. 반대로 코드를 완성해도 면접관과 한 마디도 소통하지 않고 뚝딱 코드만 짜면 낮은 점수를 받을 수 있습니다.

🔢 4단계 문제 접근 프레임워크

이 섹션에서는 어떤 알고리즘 문제가 나와도 흔들리지 않는 4단계 접근법을 살펴보겠습니다. 이 프레임워크는 구글·아마존·카카오 등 모든 기술 면접에서 검증된 방법입니다.

1단계 — 문제 완전히 이해하기 (3~5분)

가장 많이 하는 실수는 문제를 제대로 읽지 않고 코드부터 짜기 시작하는 것입니다. 문제를 받으면 최소 3분은 읽고 분석하세요. 다음 사항을 반드시 파악해야 합니다.

• 입력과 출력의 형태: 배열인가, 문자열인가, 정수인가? 출력은 무엇인가?
• 입력 크기와 제약 조건: N의 범위가 얼마인가? 이것이 O(n²) 허용 여부를 결정합니다.
• 엣지 케이스: 빈 배열, 음수, 중복, 최대값·최소값은 처리되는가?
• 정확히 무엇을 반환해야 하는가: 인덱스인가 값인가, 개수인가 목록인가?

이 단계에서 면접관에게 질문하는 것은 매우 좋은 신호입니다. "배열이 항상 정렬되어 있나요?", "입력 크기가 최대 얼마인가요?"처럼 제약을 확인하는 질문은 당신이 문제를 깊게 분석하고 있음을 보여줍니다.

2단계 — 예시로 손으로 풀어보기 (3분)

문제를 이해했으면 종이나 화이트보드에 예시를 직접 손으로 풀어보세요. 주어진 예시를 따라가면서 어떤 패턴이 보이는지 관찰합니다. "이 과정에서 뭔가 반복되는 구조가 있는가?", "정렬하면 더 쉬워지는가?", "나누어서 생각하면 어떤가?" 같은 질문을 스스로에게 던지면서 패턴을 찾으세요.

이 단계의 핵심은 코드 없이 머릿속으로 시뮬레이션하는 것입니다. 코드로 표현하기 전에 로직이 명확해야 합니다. 손으로 풀어보지 않고 코드부터 짜면 중간에 설계가 틀렸다는 것을 깨닫고 전부 다시 써야 하는 상황이 생깁니다.

3단계 — 브루트 포스 해법 먼저 (5분)

완벽한 최적 해법을 처음부터 찾으려다 아무것도 못하는 것보다, 느리더라도 작동하는 해법을 먼저 말하는 것이 훨씬 낫습니다. 브루트 포스(모든 경우를 시도)로 접근하면서 그 시간복잡도를 말하세요. 면접관에게 "먼저 O(n²) 브루트 포스 방법을 생각해봤는데, 이것부터 확인하고 최적화를 진행해도 될까요?"라고 말하면 매우 좋은 인상을 줍니다.

4단계 — 최적화 (10~15분)

브루트 포스 해법이 있으면 최적화를 시도합니다. 다음 질문들이 최적화의 단서가 됩니다.

• 어떤 계산이 반복되는가? → 메모이제이션 또는 캐싱 적용
• 정렬하면 이진 탐색을 쓸 수 있는가? → O(n) → O(log n)
• 투 포인터나 슬라이딩 윈도우로 O(n²) → O(n)이 되는가?
• 그래프 문제인가? → BFS/DFS 적용
• 최적 부분 구조가 있는가? → 동적 프로그래밍 적용

🔍 알고리즘 패턴 인식법

이 섹션에서는 문제 유형을 보고 어떤 알고리즘 패턴을 적용할지 빠르게 판단하는 법을 살펴보겠습니다.

알고리즘 문제는 사실 패턴의 변형입니다. 패턴을 인식하는 능력을 키우면 처음 보는 문제도 "이거 ~패턴이네"라고 분류하고 접근할 수 있습니다.

문제 키워드	적용 패턴	핵심 아이디어
정렬된 배열 + 탐색	이진 탐색	중간을 기준으로 절반씩 제거
연속 부분 배열 + 합/최대/최소	슬라이딩 윈도우	윈도우를 오른쪽으로 이동하며 갱신
두 수의 합, 이동하는 포인터	투 포인터	양쪽에서 좁혀가기
최단 경로, 레벨별 탐색	BFS (큐)	가까운 것부터 탐색
경로 탐색, 사이클 감지	DFS (스택/재귀)	한 방향 끝까지 탐색
최대/최소를 매 단계 선택	그리디	현재 최선이 전체 최선
겹치는 부분 문제, 최적해 구성	동적 프로그래밍	작은 문제 결과를 저장·재사용
괄호·짝 맞추기·역순 처리	스택	LIFO 구조 활용
빠른 삽입·삭제·최소/최대 조회	힙(우선순위 큐)	트리 구조로 O(log n) 보장

이 표를 외우는 것보다 각 패턴을 유형 문제 10문제씩 풀면서 손에 익히는 것이 훨씬 중요합니다. 패턴 인식은 이론이 아니라 경험입니다.

🗣️ Thinking Aloud — 면접관과 대화하며 풀기

이 섹션에서는 라이브 면접 코딩에서 가장 중요한 기술 중 하나인 Thinking Aloud 기법을 살펴보겠습니다.

Thinking Aloud는 자신의 사고 과정을 소리 내어 말하면서 코드를 작성하는 기법입니다. 이것이 중요한 이유는 단순합니다. 면접관은 당신의 화면을 보고 있지만 당신이 무슨 생각을 하는지 모릅니다. 말하지 않으면 면접관은 침묵 속에서 불안감만 느낍니다. 반대로 생각을 소리 내어 말하면 설령 코드가 완벽하지 않아도 사고 과정 자체가 평가 포인트가 됩니다.

Thinking Aloud 스크립트 예시

"문제를 읽어보면, 정렬된 배열에서 타겟 값을 찾는 건데... 정렬되어 있으니까 이진 탐색을 쓸 수 있겠네요. 시간복잡도가 O(log n)으로 줄어들고요. 먼저 left=0, right=n-1로 설정하고 mid를 구해서... 잠깐, 오버플로우 방지를 위해 mid = left + (right - left) / 2로 하는 게 안전하겠습니다. mid 값이 타겟보다 크면 오른쪽은 다 볼 필요가 없으니 right=mid-1로 좁히고..."

이렇게 말하는 것이 어색할 수 있습니다. 하지만 반드시 연습해야 합니다. 혼자 코딩 연습할 때도 소리 내어 설명하면서 연습하면 자연스러워집니다.

Thinking Aloud 핵심 포인트 4가지

1. 문제 이해를 소리 내어 확인: "이 문제는 ~를 구하는 문제죠?"
2. 접근 방향 선언: "이진 탐색으로 접근해보겠습니다. 이유는 ~이기 때문입니다."
3. 코드 작성 중 설명: "여기서 left가 right를 초과하면 루프를 종료합니다."
4. 검증 단계 선언: "제가 예시 케이스로 한번 트레이스해보겠습니다."

🆘 막혔을 때 전략 — 포기하지 않는 법

이 섹션에서는 문제를 풀다가 막혔을 때 침묵 대신 사용할 수 있는 구체적인 전략을 살펴보겠습니다.

막히는 것은 당연합니다. 중요한 것은 막혔을 때 어떻게 하는가입니다. 가장 나쁜 대응은 침묵하면서 화면만 바라보는 것입니다. 이 상황에서 면접관은 당신이 포기했다고 느낍니다.

막혔을 때 즉시 사용할 수 있는 5가지 전략

전략 1 — 작은 예시로 돌아가기: "제가 좀 막혔는데, 가장 작은 예시로 다시 손으로 풀어볼게요." 추상적인 문제를 n=3, n=4 같은 구체적인 수로 시뮬레이션하면 패턴이 보이는 경우가 많습니다.

전략 2 — 더 쉬운 버전 먼저: "제약 조건을 단순화해서 먼저 생각해볼게요." 예를 들어 정렬된 입력만 들어온다고 가정하거나, 중복이 없다고 가정해서 풀고 나서 제약을 해제합니다.

전략 3 — 브루트 포스 먼저 코딩: "일단 O(n²) 해법으로 구현하고, 이후에 최적화하겠습니다." 작동하는 코드를 먼저 확보하면 심리적 안정감이 생기고 최적화도 더 잘 됩니다.

전략 4 — 면접관에게 힌트 요청: "제가 두 가지 방향을 생각하고 있는데 한 방향으로 진행해도 될지 여쭤봐도 될까요?" 또는 "제가 이 부분에서 좀 막혔는데, 방향이 맞는지 확인해도 될까요?" 면접관은 힌트를 주기 위해 거기 있습니다. 완전히 막혀서 아무것도 못하는 것보다, 힌트를 받고 진행하는 것이 훨씬 낫습니다.

전략 5 — 다른 자료구조·알고리즘으로 전환: "현재 O(n²) 방식이 너무 느린 것 같아서, 해시맵을 이용한 O(n) 방법이 있을지 생각해보겠습니다." 막혔다는 것을 인지하고 다른 도구로 전환할 수 있다는 것 자체가 능력입니다.

⏱️ 면접 시간 관리 전략

이 섹션에서는 보통 45분~1시간인 알고리즘 면접 시간을 효율적으로 배분하는 방법을 살펴보겠습니다.

단계	시간	활동
문제 이해 + 질문	3~5분	제약 확인, 엣지케이스 파악
예시 풀이	3~5분	손으로 시뮬레이션, 패턴 탐색
접근 방향 선언	2분	브루트포스 → 최적화 계획 말하기
코드 작성	15~20분	Thinking Aloud 유지, 꾸준히 진행
검증 + 엣지케이스	5분	예시 트레이스, 예외 처리 확인
복잡도 분석 + QA	3~5분	시간·공간 복잡도, 역질문

시간이 부족할 것 같으면 먼저 코드의 핵심 로직을 완성하고, 엣지케이스 처리는 "이 부분은 ~한 경우를 처리해야 하는데 시간이 부족하면 이렇게 할 것입니다"라고 말하는 것이 아무것도 완성하지 못하는 것보다 낫습니다. 면접관은 모든 케이스를 처리한 완벽한 코드보다 핵심 로직을 이해하고 제한 시간 안에 실행 가능한 코드를 만드는 능력을 더 높이 평가합니다.

📝 핵심 요약

4강에서 배운 내용을 정리해 보겠습니다.

단계	핵심 행동	시간
1. 문제 이해	입력·출력·제약·엣지케이스 파악, 면접관에게 질문	3~5분
2. 예시 시뮬레이션	손으로 풀어보며 패턴 탐색	3~5분
3. 브루트 포스 선언	느리더라도 작동하는 해법 먼저	2~3분
4. 최적화	패턴 인식 → 알고리즘 선택 → 구현	15~20분

막혔을 때 절대 침묵하지 마세요. 작은 예시로 돌아가거나, 더 쉬운 버전을 먼저 풀거나, 힌트를 요청하는 것이 모두 합격 전략입니다. 다음 강인 5강 — 시간·공간 복잡도에서는 알고리즘의 성능을 Big-O 표기법으로 정확히 분석하는 방법과 면접에서 복잡도 질문에 답하는 전략을 완전히 익힙니다. 복잡도를 말할 수 없으면 코드를 완성해도 절반 점수입니다!