실전 대비 C 알고리즘 인터뷰

1부 코딩 인터뷰를 위한 기본 개념 익히기

1장 알고리즘 분석
_1.1 점근적 분석
_1.2 알고리즘 복잡도 분석
_1.3 시간 복잡도 예제
_1.4 마스터 정리
_1.5 배열 기반 문제
_1.6 재귀 함수

2장 알고리즘 문제를 풀기 위한 접근법
_2.1 제약 조건 분석
_2.2 아이디어 구상
_2.3 복잡도 계산
_2.4 코딩
_2.5 테스트
_2.6 코딩 인터뷰 예시
_2.7 정리

3장 추상 자료형과 자료 구조
_3.1 추상 자료형
_3.2 자료 구조
_3.3 배열
_3.4 연결 리스트
_3.5 스택
_3.6 큐
_3.7 트리
_3.8 힙
_3.9 해시 테이블
_3.10 딕셔너리와 심볼 테이블
_3.11 그래프
_3.12 정렬
_3.13 정리

4장 정렬
_4.1 정렬 유형
_4.2 정렬 알고리즘 비교
_4.3 정렬 문제

5장 검색
_5.1 왜 검색일까
_5.2 검색 알고리즘의 종류
_5.3 검색 문제

2부 자료 구조

6장 연결 리스트
_6.1 연결 리스트의 기본
_6.2 연결 리스트의 종류
_6.3 연결 리스트 문제

7장 스택
_7.1 스택의 추상 자료형
_7.2 시스템 스택과 함수 호출
_7.3 배열로 스택 구현하기
_7.4 연결 리스트로 스택 구현하기
_7.5 스택 문제

8장 큐
_8.1 큐의 추상 자료형
_8.2 배열로 큐 구현하기
_8.3 연결 리스트로 큐 구현하기
_8.4 큐 문제

9장 트리
_9.1 트리의 기본
_9.2 이진 트리
_9.3 이진 트리의 유형
_9.4 이진 트리 문제
_9.5 이진 탐색 트리
_9.6 이진 탐색 트리 문제
_9.7 이진 트리의 확장

10장 힙
_10.1 힙의 유형
_10.2 힙의 추상 자료형 연산
_10.3 힙 연산
_10.4 힙 정렬하기
_10.5 힙을 사용하는 곳
_10.6 힙 문제

11장 해시 테이블
_11.1 해시 테이블
_11.2 충돌 해결 기법
_11.3 해싱 문제

12장 그래프
_12.1 그래프 용어
_12.2 그래프 구현 방법
_12.3 그래프 순회
_12.4 그래프 문제

3부 고급 알고리즘

13장 문자열 알고리즘
_13.1 문자열 일치
_13.2 심볼 테이블과 딕셔너리
_13.3 문자열 문제

14장 알고리즘 설계 기법
_14.1 무차별 대입 알고리즘
_14.2 탐욕 알고리즘
_14.3 분할 정복과 부분 정복
_14.4 동적 계획법
_14.5 변환 정복
_14.6 백트래킹
_14.7 분기 한정
_14.8 A* 알고리즘
_14.9 정리

15장 무차별 대입 알고리즘
_15.1 버블 정렬
_15.2 선택 정렬
_15.3 순차 검색
_15.4 pow(a, n) 계산하기
_15.5 문자열 일치
_15.6 가장 가까운 두 점의 무차별 대입 알고리즘
_15.7 볼록 껍질 문제
_15.8 완전 탐색
_15.9 정리

16장 탐욕 알고리즘
_16.1 동전 교환 문제
_16.2 최소 신장 트리
_16.3 단일 출발 최단 경로의 데이크스트라 알고리즘
_16.4 최적 인코딩을 위한 허프만 트리
_16.5 작업 선택 문제
_16.6 배낭 문제

17장 분할 정복과 부분 정복
_17.1 일반 분할 정복의 반복
_17.2 병합 정렬
_17.3 퀵 정렬
_17.4 외부 정렬
_17.5 이진 검색
_17.6 제곱 함수
_17.7 볼록 껍질
_17.8 가장 가까운 두 점

18장 동적 계획법
_18.1 피보나치 수
_18.2 조립 라인 계획
_18.3 최장 증가 부분 수열
_18.4 최장 바이토닉 부분 수열
_18.5 연쇄 행렬 곱셈
_18.6 최장 공통 부분 수열
_18.7 동전 교환 문제

19장 백트래킹
_19.1 N 여왕 말 문제
_19.2 하노이의 탑

20장 복잡도 이론
_20.1 결정 문제
_20.2 복잡도 클래스
_20.3 정리

처음 접하는 문제는 어떻게 풀까요? 해답은 문제를 많이 풀어 보는 것입니다. 많은 문제를 풀다 보면 접해 보지 않은 문제도 풀 수 있게 됩니다. 문제를 충분히 많이 풀어 보면 처음 보는 문제에서 패턴을 발견하고 쉽게 해결할 수 있습니다.

문제를 푸는 것은 단지 알고리즘을 알고 좋은 소프트웨어 시스템을 만드는 것만을 의미하지 않습니다. 면접관은 여러분이 주어진 문제에 어떻게 접근하는지를 알고 싶어 합니다. 많은 사람이 주어진 문제를 명확하게 하는 질문을 하지 않아서 실수하게 됩니다. 이런 사람들은 한 번에 많은 것을 가정하고 문제를 풀기 시작합니다. 문제를 풀기 전에 면접관으로부터 얻어야 할 많은 정보를 놓친 채 말입니다.

우리는 비주얼 스튜디오 같은 IDE로 코딩하는 것에 익숙합니다. 화이트보드나 종이에 코드를 작성하라고 하면 많은 사람이 난처해합니다. 따라서 종이에 코딩하는 연습을 해야 합니다. 종이는 뒤로 가기 버튼이 없으니 코딩하기 전에 생각해야 합니다. 항상 모듈 형태의 코드를 작성하려고 노력하세요. 깨끗하고 관리하기 편한 코드가 되도록 함수를 작게 만들어야 합니다.

- 2장 알고리즘 문제를 풀기 위한 접근법 중에서