실전 코딩 테스트 가이드 - 12가지 핵심 알고리즘 문제 접근과 구현 노하우 학습하기

코딩 테스트를 어떻게 준비해야 할까?

 

코딩 테스트에 자주 등장하는 핵심 유형들 구현(시뮬레이션), 완전 탐색, 동적 프로그래밍, 탐욕법, 이진 탐색, 투 포인터 등 문제를 푸는 데 꼭 필요한 주요 알고리즘을 어떻게 읽고, 문제 유형과 구현 패턴을 배울 수 있습니다.

AI가 코드를 대신 써 주는 시대일수록, 개발자는 더 정확하게 읽고 더 깊이 이해할 수 있어야 합니다. 이 책은 초보 개발자가 그 출발점을 단단하게 만들 수 있도록 안내하는 친절한 길잡이가 되어 줄 것입니다.

【 대상 독자층 】

- 코딩 테스트를 처음 준비하는 개발자 및 취업 준비생

- 알고리즘 기본 이론을 배웠지만 문제 풀이가 어려운 분

- 정답 코드를 봐도 왜 그렇게 풀었는지 이해하기 어려운 분

[목차]

1장 구현(시뮬레이션)

1. 문제 분류 설명

1-1. 요구사항을 함수로 나누어 구현하기

1-2. 함수 분할의 기준

1-3. 데이터의 배열화

1-4. 비트 처리

2. 문제 풀이

기본 문제 1: 중국 신분증 번호

기본 문제 2: 로봇 청소기

응용 문제 1: 온풍기 안녕!

응용 문제 2: 큐빙

 

2장. 완전 탐색

1. 문제 분류 설명

2-1. 알고리즘 시간 복잡도 분석

2-2. 재귀 함수

2-3. 재귀 함수 구현 방법

2-4. 재귀 함수 작성 시 주의점

2-5. 백트래킹과 가지치기

2-6. DFS와 BFS

2. 문제 풀이

기본 문제 1: DFS와 BFS

기본 문제 2: N과 M (1)

기본 문제 3: N과 M (2)

기본 문제 4: 숨바꼭질

응용 문제 1: 연구소

 

3장. 동적 프로그래밍

1. 문제 분류 설명

3-1. 피보나치 수열과 점화식

3-2. 메모이제이션(memoization)

3-3. 메모이제이션의 시간 복잡도

3-4. 메모이제이션 템플릿

3-5. Top-down과 Bottom-up

3-6. 배낭 문제

2. 문제 풀이

기본 문제 1: 피보나치 수

기본 문제 2: 2 × n 타일링

기본 문제 3: 계단 오르기

응용 문제 1: 체스판 위의 공

응용 문제 2: 파이프 옮기기

응용 문제 3: 가장 큰 정사각형

4장 탐욕법

1. 문제 분류 설명

4-1. 커스텀 Comparator 만드는 법

4-2. 우선순위 큐 사용법

2. 문제 풀이

기본 문제 1: 로프

기본 문제 2: 회의실 배정

기본 문제 3: 순회 강연

응용 문제 1: 전구 끄기

 

5장 이진 탐색

1. 문제 분류 설명

5-1. 이진 탐색

5-2. 매개 변수 탐색(파라메트릭 서치)

5-3. Upper Bound와 Lower Bound

2. 문제 풀이

기본 문제 1: 수 찾기

응용 문제 1: 공유기 설치

응용 문제 2: 숫자 구슬

 

6장 투 포인터

1. 문제 분류 설명

6-1. 투 포인터

6-2. 타입 체크

2. 문제 풀이

기본 문제 1: 수들의 합

응용 문제 1: 회전 초밥

응용 문제 2: 합이 0인 네 정수

 

7장 그래프와 트리

1. 문제 분류 설명

7-1. 그래프

7-2. 그래프의 종류

7-3. 간선의 표현 방법

7-4. 경로

7-5. 사이클

7-6. 트리

7-7. 트리의 재귀적 특징

2. 문제 풀이

기본 문제 1: 케빈 베이컨의 6단계 법칙

기본 문제 2: 트리 순회

응용 문제 1: 게리맨더링

응용 문제 2: 트리 색칠하기

응용 문제 3: 회장 선거

8장 위상 정렬

1. 문제 분류 설명

8-1. 위상 정렬의 조건

8-2. 위상 정렬의 특징

8-3. 위상 정렬 구현법

8-4. 위상 정렬 템플릿

2. 문제 풀이

기본 문제 1: 줄 세우기

응용 문제 1: 게임 개발

 

9장 분할 정복

1. 문제 분류 설명

2. 문제 풀이

기본 문제 1: 쿼드 트리

응용 문제 1: 트리의 순회

 

10장 누적합

1. 문제 분류 설명

10-1. 2차원 배열에서의 누적합

2. 문제 풀이

기본 문제 1: 합 구하기

응용 문제 1: 배나무

 

11장 최단 거리

1. 문제 분류 설명

11-1. 다익스트라 알고리즘

11-2. 벨만 포드 알고리즘

11-3. 플로이드 워셜 알고리즘

11-4. 어떤 최단 거리 알고리즘을 고를 것인가?

2. 문제 풀이

기본 문제 1: 최단 경로

기본 문제 2: 타임머신

기본 문제 3: 플로이드

 

12장 트라이

1. 문제 분류 설명

12-1. ant와 air를 트라이에 추가하는 경우

12-2. 트라이 노드에 더 많은 정보를 추가하여 활용

2. 문제 풀이

기본 문제 1: 접두사 찾기

응용 문제 1: 게임 닉네임