책 <파이썬 알고리즘 인터뷰> 정리

자료 구조, 알고리즘, 코딩 테스트에 대한 준비가 전혀 되어 있지 않은 나.

 

새로 시작한 K digital training 과정에 포함된 알고리즘과 코딩 테스트 과정 진도를 전혀 따라가지 못하고 있다.

잘은 모르지만 아마도 컴퓨터 공학을 대학에서 공부하는 친구들은 아마도 수업 시간에 좀 더 긴 시간을 가지고 공들여서 공부를 하는 부분인 것 같다.

나는 시간과 머리가 부족하지만, 아예 손을 놓고 있을 수 없으니 개발자 지인이 추천한 책을 일단 한 권 사서 보기 시작했다.

 

 

<파이썬 알고리즘 인터뷰>

700페이지가 넘은 무지 두꺼운 책이다.

 

자료구조와 알고리즘, 문제 풀이가 주가 되지만, 

머리 식힐 겸 읽어볼 만한 코딩 테스트 노하우, 이직 가이드 같은 내용도 있어 다행이 재미있게 보고 있다.

 

이제 겨우 읽기 시작했지만, 인상 깊거나 기억해 두어야할 부분 정리하기.

 

1부. 코딩 인터뷰

 

본격적인 알고리즘 공부와 문제 풀이에 앞서, 

대부분 이 책을 사서 보는 이유는 입사를 위한 코딩 테스트와 코딩 인터뷰를 준비하기 위해서일테니, 그에 대한 대략적인 설명, 그리고 이 책으로 공부하는 방법을 안내하고 있다.

 

이 책에 나온 문제들은 대부분 리트코드에 나오는 문제들이라고 한다.

leetcode.com/problemset/all/

Problems - LeetCode

한국의 백준, 프로그래머스 사이트만 알고 있었는데, 많은 사람들이 문제 풀이를 연습하는 영어 사이트라고 한다.

한 번 들어가서 풀어봐야겠다.

 

<인상적인 것>

1. 나만의 코드 스니핏을 정리해놓자.

 

확실히 자주 사용하는 코드 조각들이 있다.

자주 쓴다고 생각하면서 매번 다시 쓰고 있었는데, 아무래도 코딩 테스트는 시간과의 싸움이니까, 미리 정리를 해두면 좋을 것 같다.

코랩 등에 혹은 이 블로그에 하나씩 잘 정리해두면 좋을 것 같다.

 

2. 파이썬 dataclass 데코레이션

 

잘 모르던 내용이다.

dataclass를 선언하지 않아도 클래스 구현에는 문제가 없지만, 선언하게 되면 여러 내부 함수 기능을 자동으로 구현해 준다고 하니 공부해보자.

 

3. 코딩 테스트에 참여했으나  풀이 시간을 초과했을 때 

 

저자가 직접 경험한 이야기를 풀었다.

시간 초과 해서 플랫폼은 닫혔지만 따로 IDE에서 푼 다음, 채용 담당자에게 이메일을 보냈고, 좋은 피드백을 받고 인터뷰까지 갔다는 말이었다.

이건 항상 성공할 수는 없을 것 같고, 그 담당자가 직접 이메일을 찾아서 보낸 적극성을 높게 평가한 경우인 것 같다.

근데 해서 손해볼 것은 없고 낮은 확률로 이익을 얻을 수 있으니 안할 이유가 없는 팁이다.

 

2부. 파이썬

파이썬 언어가 다른 프로그래밍 언어와 다른 어떤 특징을 가지고 있는지,

그러한 파이썬의 특징을 활용해 해결할 수 있는 간단한 문제들과 함께 정리한 파트이다.

 

내 경우는 자바스크립트 강의를 아주 잠깐 들은 것을 제외하고는 거의 파이썬 밖에 모르기 때문에 다른 언어와의 비교는 와닿기 어려웠다.

하지만 list comprehension, lambda function, enumerate 등과 같이 잘 이해하고, 잘 쓸 수 있으면 코딩 테스트에서 자주 활용하게 되는 기능들을 정리해 준 점이 좋았다.

 

 

3부. 선형 자료구조

 

 

 

4부. 비선형 자료구조

 

 

 

5부. 알고리즘

 

 

책에서 다루는 모든 문제에 대한 해답 코드가 있는 깃허브

github.com/onlybooks/algorithm-interview

onlybooks/algorithm-interview

 

 

문제번호	책 페이지	리트코드 링크	난이도	책 단원	풀이 링크 (쉬운 건 포스팅 없음)
1	138	125.유효한 팰린드롬	★	6장. 문자열 조작
2	145	344.문자열 뒤집기	★	6장. 문자열 조작
3	148	937.로그 파일 재정렬	★	6장. 문자열 조작	rollingsnowball.tistory.com/116
4	151	819.가장 흔한 단어	★	6장. 문자열 조작	rollingsnowball.tistory.com/114
5	153	49.그룹 애너그램	★★	6장. 문자열 조작	rollingsnowball.tistory.com/117
6	159	5.가장 긴 팰린드롬 부분 문자열	★★	6장. 문자열 조작	rollingsnowball.tistory.com/118
7	173	1.두 수의 합	★	7장. 배열	rollingsnowball.tistory.com/122
8	180	42.빗물 트래핑	★★★	7장. 배열	https://rollingsnowball.tistory.com/173
9	184	15.세 수의 합	★★	7장. 배열	rollingsnowball.tistory.com/125
10	190	561.배열 파티션 I	★	7장. 배열
11	193	238.자신을 제외한 배열의 곱	★★	7장. 배열	rollingsnowball.tistory.com/126
12	195	121.주식을 사고팔기 가장 좋은 시점	★	7장. 배열	rollingsnowball.tistory.com/124
13	201	234.팰린드롬 연결 리스트	★	8장. 연결 리스트	https://rollingsnowball.tistory.com/131
14	213	21.두 정렬 리스트의 병합	★	8장. 연결 리스트	https://rollingsnowball.tistory.com/132
15	219	206.역순 연결 리스트	★	8장. 연결 리스트	https://rollingsnowball.tistory.com/138
16	221	2.두 수의 덧셈	★★	8장. 연결 리스트
17	229	24.페어의 노드 스왑	★★	8장. 연결 리스트
18	233	328.홀짝 연결 리스트	★★	8장. 연결 리스트
19	237	92.역순 연결 리스트 II	★★	8장. 연결 리스트
20	245	20.유효한 괄호	★	9장. 스택, 큐	https://rollingsnowball.tistory.com/168
21		중복 문자 제거	★★★	9장. 스택, 큐
22	252	739.일일 온도	★★	9장. 스택, 큐	https://rollingsnowball.tistory.com/169
23		큐를 이용한 스택 구현	★	9장. 스택, 큐
24		스택을 이용한 큐 구현	★	9장. 스택, 큐
25		원형 큐 디자인	★★	9장. 스택, 큐
26		원형 데크 디자인	★★	10장. 데크, 우선 순위 큐
27		k개 정렬 리스트 병합	★	10장. 데크, 우선 순위 큐
28		해시맵 디자인	★	11장. 해시 테이블
29		보석과 돌	★	11장. 해시 테이블
30		중복 문자 없는 가장 긴 부분 문자열	★★	11장. 해시 테이블
31		상위 K 빈도 요소	★★	11장. 해시 테이블
32		섬의 개수	★★	12장. 그래프
33		전화 번호 문자 조합	★★	12장. 그래프
34		순열	★★	12장. 그래프
35		조합	★★	12장. 그래프
36		조합의 합	★★	12장. 그래프
37		부분 집합	★★	12장. 그래프
38		일정 재구성	★★	12장. 그래프
39		코스 스케줄	★★	12장. 그래프
40		네트워크 딜레이 타임	★★	13장. 최단 경로 문제
41		K 경유지 내 가장 저렴한 항공권	★★	13장. 최단 경로 문제
42		이진 트리의 최대 깊이	★	14장. 트리
43		이진 트리의 직경	★	14장. 트리
44		가장 긴 동일 값의 경로	★	14장. 트리
45		이진 트리 반전	★	14장. 트리
46		두 이진 트리 병합	★	14장. 트리
47		이진 트리 직렬화 & 역직렬화	★★★	14장. 트리
48		균형 이진 트리	★	14장. 트리
49		최소 높이 트리	★★	14장. 트리
50		108. 정렬된 배열의 이진 탐색 트리 변환	★	14장. 트리	https://rollingsnowball.tistory.com/195
51		이진 탐색 트리(BST)를 더 큰 수 합계 트리로	★★	14장. 트리
52		이진 탐색 트리(BST) 합의 범위	★	14장. 트리
53		이진 탐색 트리(BST) 노드 간 최소 거리	★	14장. 트리
54		전위, 중위 순회 결과로 이진 트리 구축	★★	14장. 트리
55		215. 배열의 K번째 큰 요소	★★	15장. 힙
56		트라이 구현	★★	16장. 트라이
57		팰린드롬 페어	★★★	16장. 트라이
58		리스트 정렬	★★	17장. 정렬
59		구간 병합	★★	17장. 정렬
60		삽입 정렬 리스트	★★	17장. 정렬
61		가장 큰 수	★★	17장. 정렬
62		유효한 애너그램	★	17장. 정렬
63		색 정렬	★★	17장. 정렬
64		원점에 K번째 가까운 점	★★	17장. 정렬
65		이진 검색	★	18장. 이진 검색
66		회전 정렬된 배열 검색	★★	18장. 이진 검색
67		두 배열의 교집합	★	18장. 이진 검색
68		두 수의 합 II	★	18장. 이진 검색
69		2D 행렬 검색 II	★★	18장. 이진 검색
70		싱글 넘버	★	19장. 비트 조작
71		해밍 거리	★	19장. 비트 조작
72		두 정수의 합	★★★	19장. 비트 조작
73		UTF-8 검증	★★	19장. 비트 조작
74		1비트의 개수	★	19장. 비트 조작
75		최대 슬라이딩 윈도우	★★★	20장. 슬라이딩 윈도우
76		부분 문자열이 포함된 최소 윈도우	★★★	20장. 슬라이딩 윈도우
77		가장 긴 반복 문자 대체	★★	20장. 슬라이딩 윈도우
78		주식을 사고 팔기 가장 좋은 시점 II	★	21장. 그리디 알고리즘
79		키에 따른 대기열 재구성	★★	21장. 그리디 알고리즘
80		621. 태스크 스케줄러	★★	21장. 그리디 알고리즘
81		주유소	★★	21장. 그리디 알고리즘
82		쿠키 부여	★	21장. 그리디 알고리즘
83		과반수 엘리먼트	★	22장. 분할 정복
84		괄호를 삽입하는 여러가지 방법	★★	22장. 분할 정복
85		509. 피보나치 수	★	23장. 다이나믹 프로그래밍
86		최대 서브 배열	★	23장. 다이나믹 프로그래밍
87		70. 계단 오르기	★	23장. 다이나믹 프로그래밍
88		집 도둑	★	23장. 다이나믹 프로그래밍
89(문제 1)		비밀 지도	★	부록 B. 카카오 공채 문제 풀이
90(문제 2)		다트 게임	★	부록 B. 카카오 공채 문제 풀이
91(문제 3)		캐시	★	부록 B. 카카오 공채 문제 풀이
92(문제 4)		셔틀버스	★★	부록 B. 카카오 공채 문제 풀이
93(문제 5)		뉴스 클러스터링	★★	부록 B. 카카오 공채 문제 풀이
94(문제 6)		프렌즈4블록	★★★	부록 B. 카카오 공채 문제 풀이
95(문제 7)		추석 트래픽	★★★	부록 B. 카카오 공채 문제 풀이