파이썬 자료구조와 알고리즘

 

총평

파이썬이 인기를 얻으면서 최근에는 출간 목록도 다 쫓아가기 힘들 정도로 많은 책이 나오고 있다. 새로운 프레임워크나 언어 자체에 대한 책은 보통 버전이 올라가면 새로운 내용이 추가되므로 기존의 책은 다시 볼 일이 거의 없지만, 기본에 대한 책은 그렇지 않다. “파이썬 자료구조와 알고리즘"도 그런 책이다. 프로그래밍 면접을 볼 때 파이썬은 주로 사용하는 언어 중 하나이며, 자료구조와 알고리즘은 프로그래밍에서 항상 빠지지 않는 기본 중의 기본이다. 게다가, 최근 한국에서도 더 많은 소프트웨어 관련 회사들이 알고리즘 문제를 어떻게 해결하는 지를 주요 평가 기준으로 사용하기 때문에 시의적절한 책이라고 생각한다. Part 1은 파이썬 문법, Part 2, 3는 알고리즘이며, Part 3에서 그래프, 트리를 다루고 있다(각 장별 상세한 리뷰는 아래). 분량에 비해 비교적 많은 예제를 통해 설명하고 있고, 연습문제도 leetcode.com의 easy 난이도 정도의 문제들로 구성되어 이제 막 초급을 벗어나려는 경우 적절하다고 생각한다. 다만 각 chapter별 난이도가 고르지 않은 느낌이 있고, 구성이 일반적인 파이썬/자료구조 & 알고리즘 책과 다른 게 약간 어색하다는 생각이 든다.

Part 1

아무래도 제한된 분량 내에서 파이썬 문법을 설명하려다 보니 자세한 설명은 부족하지만, 하나의 소주제마다 많은 예제를 통해 바로 사용할 수 있는 실용성에 초점을 둔 거 같다.

Chapter1.

파이썬 기초 문법을 주로 설명하는데, 넘파이가 같이 포함되어 있다. 초보자들의 경우 설치부터 어려움을 겪는 경우가 많은데 이 부분을 언급하지 않고 바로 넘파이를 설명하면 python만 설치한 경우에는 분명히 오류를 보고 책에 문제가 있다거나 설명이 부족하다는 생각을 할 거 같다.

Chapter2.

string 처리를 설명하는데, string reverse에서 시작해 단어별 reverse와 같은 방식으로 확장하거나, 순열, palindrome 회문을 설명하는 등 초보자에게는 약간 어려울 수 있는 부분까지 확장한다.

Chapter3.

컬렉션을 설명하고, anagram 애너그램, 주사위, 중복 제거 등의 연습 문제를 보여준다. 이 부분은 워낙 중요하기도 하고 어떤 프로그램을 작성하건 항상 사용하는 부분이라 조금 더 설명이 자세하면 좋겠다는 생각이 들었다.

Chatper4.

4장은 순전히 파이썬 문법에 관계된 부분이며, 문제를 해결하는데 보조적인 역할을 하는 여러 가지 부분을 설명한다(대표적으로 file I/O). 간단한 문제 해결을 위한 프로그램에서는 별로 관계가 없으나 프로젝트를 진행하는 등 약간이라도 규모가 커지는 경우는 역시 매우 중요한 부분이다(예를 들어 프로젝트 구조를 결정하기 위해 import를 하는 등).

Chapter5.

5장은 OOP에 대한 내용인데, 이게 과연 초보자용 책에 필요할지는 잘 모르겠다. 디자인 패턴까지 넣었지만, 또 들어간 내용은 observer와 singleton뿐인데, 이건 심화 주제로 따로 소개만 하는 게 좋았을 거란 생각이 들었다.

Chapter6.

6장 역시 5장과 마찬가지로, 프로세스와 스레드, 가상 환경은 초보자용의 주제는 아니다. 물론 이 책은 초중급용이긴 하지만, 책의 주제를 생각하면 너무 적은 분량에 많은 주제를 넣고 싶어 했던 저자의 욕심이 아닐까 하는 생각이 든다. 디버깅과 테스트 부분은 하나의 파일/모듈로만 이뤄진 프로그램에서도 필요한 부분이므로 넣을 만 하단 생각이 든다.

Part 2

Chapter7.

스택 큐 힙 연결 리스트 해시 테이블같은 기본이 되는 자료구조에 대한 장. 특히 7장에서 나온 스택과 큐 구현은 정석적인 구현으로 확실히 기억해두는 게 좋다. 해시테이블은 보통 프로그래밍 문제를 해결할 때 파이썬 내장을 이용하고, 해시테이블 자체를 구현해야 하는 문제는 없으므로 보고 이해만 할 수 있으면 된다.

Chatper8.

시간 복잡도를 설명하는 장. 보통 자료구조 알고리즘 책을 보면 거의 1장에 나오는 내용이므로 7장보다 앞에 가야 순서가 맞을 거 같다.

Chatper9.

정렬을 설명한다. python에서는 sort()나 sorted()로 간단하게 정렬을 할 수 있지만, 프로그래밍 면접에서는 실제로 구현을 해야 하는 경우가 있고(대개는 quicksort나 mergesort, heapsort), 구현은 안 해도 설명을 해야 하는 경우는 종종 있기 때문에 잘 파악을 해야 한다. 연습문제는 가장 큰 k개를 찾는 건데 보통 heap을 이용하는데 여기서는 quicksort로 설명을 한다.

Chapter10.

순차와 이진 검색을 설명하고 여러 가지 연습문제를 설명한다. 교집합을 구하는데 이진 검색을 사용하는 경우는 처음 본 거 같은데 개인적으로 잘 기억해야겠다는 생각을 했다. 자주 나오는 문제는 자기가 언제나 확실히 해결할 수 있는 방식을 하나 이상 확실히, 외울 정도로 기억하고 이렇게 새로운 방식으로 가능하다는 점도 알아두는 식으로 확장을 하면 좋다.

Chapter11.

dynamic programming. memoization을 아주 간단하게 언급하고 지나간다. 면접에서 만나는 프로그래밍 문제의 경우 간단한 DP 문제가 나오는 경우가 많기 때문에 이에 대한 연습이 필요한 경우 따로 책을 보는 게 좋다. 최근에 출간된 책 — 다이내믹 프로그래밍 완전 정복이 있어서 한 번 보려고 생각 중인데, 목차만 볼 때는 기본적인 부분을 설명하고 여러 가지 대표적인 DP관련 프로그래밍 문제를 다루는 걸로 보인다.

Part 3

Chapter12.

graph 기초를 설명하고 간단히 구현할 수 있는 방법을 설명한다. 설명이 간단한 편이라 잘 읽어보고 그래도 이해가 안 되면 더 자세하게 설명하는 책을 봐야 한다.

Chapter13.

binary tree & binary search tree를 알려준다. 이 부분은 프로그래밍 퀴즈에서 정말 자주 나오는 부분이라 잘 기억해야 한다. 반면에 AVL 트리나 레드 블랙 트리는 물론 알면 좋지만 이 책의 전반적인 수준에서는 굳이 필요할까 하는 생각이 들었다. 개인적으로 봤던 수많은 프로그래밍 면접에서 단 한 번도 겪어본 적이 없는 문제이고, 다른 사람들 후기에서도 거의 본 적이 없다. 물론 그만큼 좀 더 어려운 부분이라 잘 알고 설명할 수 있다면 자신만의 강점이 될 수 있는 부분이기도 하다.

Chapter14.

DFS, BFS. stack과 queue를 이용해 iterative로 잘 설명하고 있다. 여러 가지 프로그래밍 문제에서 아주 유용하게 사용할 수 있는 부분이라 외울 정도로 기억해두는 게 좋은 기본 코드이다. 너비 우선 탐색을 영어로 breadth-first search BFS로 썼지만 예제에서 함수 이름은 BFT로 썼는데, 이게 breadth-first traverse의 약자라는 걸 같이 써주면 더 좋았겠다는 아주 쓸데없는 트집 하나 정도는 잡을 수 있다.

부록

그래프 알고리즘을 참고할 geeksforgeeks 링크와 프로그래밍 면접 준비를 위한 hackerrank, 백준 알고리즘 사이트 추천을 하고 있다. 개인적으로는 hackerrank보다 leetcode를 추천하는데, 그 이유는 hackerrank는 일단 문제 설명이 쓸데없이 길고 아주 가끔이지만 leetcode보다 좀 더 오류(도저히 못 풀겠어서 hackerrank가 제공하는 solution을 그대로 입력했는데도 timeout이 발생하는 등)가 있었기 때문이다.

Etc.

옮긴이 github. 예전에도 겪었던 일인데, 책 시작 부분의 저자 혹은 옮긴이의 말 부분에 있는 link는 리디북스에서는 link가 걸리지 않아서 따로 입력을 해야 한다. 일일이 확인을 하진 않았지만, 어떤 경우는 link를 클릭해서 바로 브라우저에서 볼 수 있고(34p NOTE의 시간 복잡도) 또 그렇지 않은 경우(37p 넘파이 링크는 클릭 불가능)가 있는 걸 보면 리디북스에서 link 부분을 처리할 때 오류가 있는 게 아닌가 싶다.

https://github.com/AstinCHOI/Python-and-Algorithms-and-Data-Structures