2021년 필독 "알고리즘 책" 추천 목록

1. 자료구조와 알고리즘 기초

 

 

• 알고리즘: 컴퓨터가 문제를 해결하기 위해 실행할 일련의 절차
• 자료구조: 데이터를 구조화하고 저장하는 방법
• 배열(Array): 인덱스를 통해 접근할 수 있는 데이터의 집합
• 연결 리스트(Linked List): 각 노드가 데이터와 포인터로 이루어지는 자료구조
• 스택(Stack): 후입선출(LIFO) 구조를 따르는 자료구조
• 큐(Queue): 선입선출(FIFO) 구조를 따르는 자료구조
• 해시테이블(Hash Table): 키-값 쌍을 저장하는 자료구조

 

 

2. 알고리즘 설계 기법

 

 

• 탐욕 알고리즘(Greedy Algorithm): 현재 상황에서 가장 최적인 해결책을 선택하는 알고리즘
• 분할정복(Divide and Conquer): 문제를 작은 단위로 분할하여 해결한 뒤 합치는 방법
• 다이나믹 프로그래밍(Dynamic Programming): 이미 계산한 결과를 저장하고 재활용하여 중복 계산을 피하는 알고리즘
• 백트래킹(Backtracking): 해가 될 수 없는 경우 가지 치기를 해서 효율적으로 해를 찾는 알고리즘
• 그래프(Graph): 객체간의 관계를 표현하는 자료구조로 다양한 문제 해결에 사용되는 기법

 

 

3. 그리디 알고리즘

 

 

• 그리디 알고리즘

그리디 알고리즘은 매 순간 최선의 선택을 하는 알고리즘이다. 보통 최소 비용 문제나 스케줄링 문제 등에 사용된다. 그리디 알고리즘을 이해하고 싶다면 아래의 책들을 확인해보자.

• 알고리즘 문제 해결 전략 - 구종만

이 책은 그리디 알고리즘뿐만 아니라 동적 계획법, 그래프 이론 등을 폭넓게 다루고 있다. 초보자부터 숙련자까지 모두에게 유용하다.

• 이것이 취업을 위한 코딩 테스트다 - 나동빈

코딩 테스트 준비생이라면 이 책은 필수적이다. 그리디 알고리즘뿐만 아니라 많은 주제를 다루고 있어 효율적인 학습이 가능하다.

• Introduction to the Design and Analysis of Algorithms - Anany Levitin

영어로 된 책이지만 그리디 알고리즘의 이론적인 부분을 깊이 있게 다루고 있다. 수학적인 접근을 원한다면 이 책을 추천한다.

 

 

4. 분할 정복 알고리즘

 

 

• 분할 정복 알고리즘

분할 정복 알고리즘은 큰 문제를 작은 부분 문제로 나누어 해결하는 방법이다. 이 알고리즘은 일반적으로 세 가지 단계로 구성된다.

1. 분할(Divide): 문제를 작은 부분 문제로 나눈다.
2. 정복(Conquer): 각 부분 문제를 재귀적으로 해결한다.
3. 통합(Combine): 작은 부분 문제의 해답을 결합하여 원래 문제의 해답을 구한다.

대표적인 분할 정복 알고리즘 중 하나는 퀵 정렬이 있다. 퀵 정렬은 리스트를 분할하고 정복한 후 통합하는 과정을 반복하여 정렬을 수행한다. 다른 예로는 병합 정렬이 있다. 병합 정렬은 리스트를 반으로 나눈 뒤 정렬하여 합친다. 이렇게 분할 정복 알고리즘은 효율적인 문제 해결을 위해 자주 활용된다.

 

 

5. 동적 계획법

 

 

• 책 제목: "동적 계획법과 최적화"
• 저자: Richard Bellman
• 출판사: 외무성출판사
• 내용: 동적 계획법의 기본 원리부터 응용까지 체계적으로 다룬 책
• 핵심 포인트: 최적 부분 구조를 활용한 문제 해결 전략 소개

 

 

6. 백트래킹

 

 

• 백트래킹(Backtracking): 모든 후보해를 검사하되, 그 중에서 불필요한 후보해를 탈락시켜 빠르게 해를 찾는 알고리즘 기법.
• 가독성: 재귀 호출이 많이 사용되므로 코드가 복잡하고 이해하기 어려울 수 있음. 따라서 주석을 통해 각 과정을 명확하게 설명하는 것이 중요함.
• 예시 문제: N-Queens 문제, 순열 생성 등의 문제가 백트래킹 알고리즘을 사용하여 해결됨.
• 주의사항: 백트래킹 알고리즘은 모든 경우의 수를 고려하기 때문에 경우의 수가 많을수록 시간 복잡도가 급격히 증가할 수 있음.

 

 

7. 그래프 알고리즘

 

 

• 도입부: 그래프 알고리즘은 풍부한 실무 경험을 바탕으로 개발된 알고리즘으로, 실무에서 자주 활용되는 기법이다.
• 1. 깊이 우선 탐색(Depth First Search, DFS): 그래프를 탐색하는 알고리즘으로, 스택이나 재귀 함수를 활용하여 구현한다.
• 2. 너비 우선 탐색(Breadth First Search, BFS): 그래프를 탐색하는 알고리즘으로, 큐를 활용하여 구현한다. 최단 경로 문제에 효과적이다.
• 3. 다익스트라 알고리즘(Dijkstra’s Algorithm): 최단 경로를 찾는 알고리즘으로, 음수 가중치가 없는 그래프에서 사용된다.
• 4. 크루스칼 알고리즘(Kruskal’s Algorithm): 최소 비용 신장 트리를 찾는 알고리즘으로, 그리디 알고리즘의 하나이다.
• 5. 프림 알고리즘(Prim’s Algorithm): 최소 비용 신장 트리를 찾는 알고리즘으로, 트리를 확장해가는 방식으로 동작한다.

 

 

8. 문자열 알고리즘

 

 

• 문자열 매칭: 주어진 문자열에서 특정 패턴을 찾는 과정
• 보이어-무어 알고리즘: 텍스트에서 패턴을 빠르게 찾는 알고리즘
• KMP 알고리즘: 문자열에서 특정 패턴을 찾는 데 사용되는 알고리즘
• 레벤슈타인 거리: 두 문자열 사이의 차이를 측정하는 방법

 

 

9. 정렬 알고리즘

 

 

• 1. 버블 정렬 (Bubble Sort): 인접한 두 원소를 비교하고, 조건에 맞지 않을 경우 자리를 교환하는 방식으로 정렬
• 2. 선택 정렬 (Selection Sort): 배열에서 최솟값을 찾아 첫 번째 위치와 교환, 두 번째로 작은 값과 두 번째 위치 교환하는 방식으로 정렬
• 3. 삽입 정렬 (Insertion Sort): 각 요소를 적절한 위치에 삽입하는 방식으로 정렬
• 4. 합병 정렬 (Merge Sort): 분할 정복(divide and conquer) 방법을 이용하여 정렬

 

 

10. 탐색 알고리즘

 

 

• 순차 탐색(Sequential Search): 리스트의 처음부터 끝까지 하나씩 원소를 찾는 알고리즘.
• 이진 탐색(Binary Search): 정렬된 리스트에서 중간값을 기준으로 찾고자 하는 값이 왼쪽 또는 오른쪽에 있는지를 반복해서 확인하는 알고리즘.
• 너비 우선 탐색(Breadth-First Search): 루트 노드부터 시작하여 인접한 노드를 먼저 탐색하는 알고리즘.
• 깊이 우선 탐색(Depth-First Search): 한 노드의 자식을 탐색하기 전에 형제 노드가 있는지 검사하는 알고리즘.

 

 

11. 네트워크 플로우 알고리즘

 

 

• 네트워크 플로우 알고리즘

네트워크 플로우 알고리즘은 그래프 이론에서 중요한 개념 중 하나로, 네트워크에서 데이터가 흐르는 최적 경로를 찾는 알고리즘입니다. 주로 최대 유량 문제를 해결하는 데 사용되며, 그래프 내에서 어떻게 데이터가 흐르고 최대로 흐를 수 있는지를 결정합니다. 다양한 변형 알고리즘이 존재하며, 이를 효율적으로 구현하고 활용하는 것이 중요합니다. 최소 스패닝 트리, 플로이드-와샬 알고리즘과 함께 그래프 이론의 기본적인 개념 중 하나이니 꼭 숙지해두는 것이 좋습니다.

 

 

12. 최단 경로 알고리즘

 

 

• 다익스트라 알고리즘 (Dijkstra Algorithm): 정점 간의 가장 짧은 경로를 찾아주는 알고리즘으로, 음의 가중치가 없는 최단 경로를 찾을 때 유용하게 활용됩니다.
• 벨만-포드 알고리즘 (Bellman-Ford Algorithm): 음의 가중치가 포함된 경우에도 적용 가능한 최단 경로 알고리즘으로, 음의 사이클을 감지할 수 있는 장점을 가지고 있습니다.
• 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm): 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘으로, 음의 가중치가 있어도 정상적으로 작동합니다.

 

 

13. 해시 알고리즘

 

 

• 해시 알고리즘 해시 알고리즘은 데이터를 고유한 해시 코드로 변환하는 알고리즘이다. 이러한 해시 함수는 주어진 입력 값에 대해 일정한 길이의 고정된 출력 값을 생성한다. 이를 통해 데이터 변조 여부를 감지하거나 데이터의 무결성을 검증하는 데 사용된다.
• MD5 MD5는 메시지 다이제스트 알고리즘 5의 약자로, 128비트 해시 값을 생성하는 알고리즘이다. 이전에는 주로 사용되었지만 현재는 보안 문제로 인해 권장되지 않는다.
• SHA 알고리즘 SHA(Secure Hash Algorithm) 알고리즘은 미국 국립표준기술연구소(NIST)에서 개발된 해시 함수로, 데이터의 무결성을 검증하는 데 널리 사용된다. SHA-1, SHA-256, SHA-384, SHA-512 등 다양한 버전이 있다.
• 해시 충돌 해시 충돌은 두 개 이상의 입력이 동일한 해시 코드를 생성하는 경우를 말한다. 이는 보안상 문제가 될 수 있으므로 충돌 저항성이 좋은 해시 함수를 선택하는 것이 중요하다.

 

 

14. 시뮬레이션 및 구현 문제

 

 

• 백준 14499번: 주사위 굴리기
• 백준 14503번: 로봇 청소기
• 백준 14890번: 경사로
• 프로그래머스 2019 카카오 겨울 인턴십 - 징검다리 건너기
• 프로그래머스 2020 카카오 인턴십 - 보석 쇼핑

 

 

15. 코딩 인터뷰를 위한 알고리즘 문제

 

 

코딩 인터뷰를 위한 알고리즘 문제
• Cracking the Coding Interview - **Gayle Laakmann McDowell**의 책으로, 코딩 인터뷰를 대비하기에 최적화된 알고리즘 문제 해결 방법을 제시
• Elements of Programming Interviews - 동료 프로그래머 **Adnan Aziz**, **Tsung-Hsien Lee**, **Amit Prakash**의 책으로, 다양한 알고리즘 문제와 해설을 담고 있음
• Programming Interviews Exposed - **John Mongan**, **Noah Suojanen Kindler**, **Eric Giguère**의 책, 코딩 인터뷰의 전반적인 과정을 다루며 실전 문제와 해답을 소개