프로그래밍 대회 공략을 위한 알고리즘과 자료 구조 입문
책소개: link
정오표: link
제가 좋아하는 백준 온라인 저지 이용법과 문제들이 소개되어 있어서 사게 된 책입니다. 생각보다 BOJ 문제가 많지 않아서 서운했네요.. 😅 BOJ 사이트 이용법이 추가되어 있어서 초보자 분들이 이용하기에는 좋을 것 같습니다. 그리고, 개인 취향이긴 하지만, 예제 코드가 정말 깔끔하게 만들어져 있습니다.
책의 저자가 이용하는 문제 풀이 사이트
https://judge.u-aizu.ac.jp
답안 제출 후에 결과를 선택하면 해당 문제의 TC 를 다 볼 수가 있습니다.
제출한 결과를 선택하면 아래와 같은 화면이 보이는데,
예를 들어, Case #3 을 선택했을 때의 결과입니다.
어디서 틀렸는지 보고, 틀린 데이터를 확인해 볼 수가 있습니다.
== 3 장 =====================================================
37 page 의 ALDS1_1_D Maximum Profit 문제는
Problem > Course > Introduction to Algorithms and Data Structures 에 있습니다.
BOJ 에 같은 문제는 없을 것 같고, 유사한 문제는 큰 입력을 받아서 선형으로 처리하는 식의 문제면 될 것 같은데..
https://www.acmicpc.net/problem/10818 최소, 최대
https://www.acmicpc.net/problem/20053 최소, 최대2
43 page 의 ALDS1_1_A Insertion Sort
BOJ에 같은 문제는 없고, 대략 비슷한 시간/공간 복잡도를 가지는 문제는..
https://www.acmicpc.net/problem/24051 알고리즘 수업 - 삽입 정렬 1
https://www.acmicpc.net/problem/24052 알고리즘 수업 - 삽입 정렬 2
52 page 의 ALDS1_1_B Selection Sort
BOJ에 같은 문제는 없고, 대략 비슷한 시간/공간 복잡도를 가지는 문제는..
https://www.acmicpc.net/problem/23881 알고리즘 수업 - 선택 정렬 1
https://www.acmicpc.net/problem/23882 알고리즘 수업 - 선택 정렬 1
56 page 의 ALDS1_2_C Stable Sort 문제
?
60 page 의 ALDS1_2_D Shell Sort 문제
?
3장 BOJ 추천 문제
https://www.acmicpc.net/problem/2750 수 정렬하기
https://www.acmicpc.net/problem/18868 멀티버스 I
== 4 장 =====================================================
70 page 의 ALDS1_3_A Stack 문제
https://www.acmicpc.net/problem/10828 스택
https://www.acmicpc.net/problem/1406 에디터 ( 👀 좌스택, 커서, 우스택 )
75 page 의 ALDS1_3_B Queue 문제
https://www.acmicpc.net/problem/10845 큐
https://www.acmicpc.net/problem/18258 큐 2 (필요한 큐의 크기가 다르고, 입출력 속도에 신경을 써야 함)
82 page 의 ALDS1_3_C Doubly Linked List 문제
유사 BOJ ?
98 page 의 ALDS1_3_D Areas on the Cross-Section Diagram
유사 BOJ ?
4장 BOJ 추천 문제
https://www.acmicpc.net/problem/2257 화학식량
https://www.acmicpc.net/problem/2504 괄호의 값
== 5 장 =====================================================
107 page 의 ALDS1_4_A Linear Search 문제 (code)
유사 BOJ ?
109 page 의 ALDS1_4_B Binary Search 문제 (code, code2 using lower_bound)
유사 BOJ ?
<정오표 신청 내용: 122 page>
return 0;★☆ => return 0;
114 page 의 ALDS1_4_C Dictionary 문제 (code)
유사 BOJ ?
122 page 의 ALDS_4_D Allocation 문제 (code)
유사 BOJ ?
<정오표 신청 내용: 124 page>
int solve() => llong solve() {
main() { => int main() {
} => return 0; }
5장 BOJ 추천 문제
https://www.acmicpc.net/problem/10815 숫자 카드
https://www.acmicpc.net/problem/10816 숫자 카드 2
https://www.acmicpc.net/problem/2110 공유기 설치 !
https://www.acmicpc.net/problem/2343 기타 레슨 !
https://www.acmicpc.net/problem/1300 K번째 수 !
== 6 장 =====================================================
131 page 의 ALDS1_5_A Exhauseive Search 문제 (code)
134 page 의 ADLS1_5_C Koch Curve 문제 (code)
<정오표 신청 내용: 137 page>
#include<math.h> => #define _USE_MATH_DEFINES // For Visual Studio
#include<math.h>
답안 제출할 때에는 _USE_MATH_DEFINES 선언 여부가 상관이 없는데, Visual Studio 에서 빌드하려면 선언이 필요합니다.
6장 BOJ 추천 문제
https://www.acmicpc.net/problem/10870 피보나치 수 5
https://www.acmicpc.net/problem/1759 암호 만들기
https://www.acmicpc.net/problem/2447 별 찍기 - 10
https://www.acmicpc.net/problem/1074 Z
https://www.acmicpc.net/problem/1780 종이의 개수
== 7 장 =====================================================
144 page 의 ALDS1_5_B Merge Sort 문제 (code)
149 page 의 ALDS1_6_B Partition 문제 (code)
153 page 의 ALDS1_6_C Quick SOrt 문제 (code)
<정오표 신청 내용: 156 page>
Visual Studio 를 사용하는 경우에는 스택 크기를 2MB (1024 * 1024 * 2 == 2097152 bytes)로 해주어야 실행시 Stack overflow 가 발생하지 않습니다. (기본 1MB)
158 page 의 ALDS1_6_A Counting Sort 문제 (
code)
<정오표 신청 내용: 161 page>
A = malloc(... 코드를
A = (unsigned short*)malloc(... 와 같이 해주어야 합니다.
AIZU 에 제출시 compile error 발생합니다.
165 page 의 ALDS1_5_D The Number of Inversions (code)
167 page 의 ALDS1_6_D Minimum Cost Sort (code)
7장 BOJ 추천 문제
https://www.acmicpc.net/problem/2751 수 정렬하기 2
https://www.acmicpc.net/problem/10989 수 정렬하기 3
https://www.acmicpc.net/problem/11650 좌표 정렬하기
https://www.acmicpc.net/problem/18870 좌표 압축 💦
https://www.acmicpc.net/problem/1377 버블 소트
https://www.acmicpc.net/problem/1517 버블 소트
== 8 장 =====================================================
180 page 의 ALDS1_7_A Rooted Trees 문제 (code)
<정오표 신청 내용: 184 page>
int rec(int u, int p) 함수는 return 값이 없기 때문에 int 에서 void 로 바꿔야 합니다.
185 page 의 ALDS1_7_B Binary Tree 문제 (code)
189 page 의 ALDS1_7_C Tree Walk 문제 (code)
193 page 의 ALDS1_7_D Reconstruction of the Tree 문제 (code)
8장 BOJ 추천 문제
https://www.acmicpc.net/problem/1991 트리 순회
https://www.acmicpc.net/problem/11725 트리의 부모 찾기
https://www.acmicpc.net/problem/11437 LCA
https://www.acmicpc.net/problem/14267 회사 문화 1
== 9 장 =====================================================
203 page 의 ALDS1_8_A Binary Search Tree 1 (code / code_with_static_allocation)
☝ malloc 을 사용하는 이 문제의 예제코드는 바람직하지 않은 예제인 것 같습니다. TC 를 여러 개 입력받아서 수행하는 방식도 있기 때문에, malloc()을 사용한 예제코드에서는 free()를 사용하는 코드까지 제공이 되어야만 한다고 생각합니다. 여튼, 저는 CP 에서는 동적 할당(dynamic allocation)보다는 정적 할당(static allocation) 방식이 더 적합하다고 생각이 됩니다.
이유1, include 대상이 줄어서 binary size 가 작아진다.
이유2, TC 를 N 개 반복수행 하는 경우에 malloc / free 방식 보다 훨씬 편하게 메모리를 초기화할 수 있다. index 만 0 으로 초기화하면 끝!
이유3, 수행 속도도 더 빠릅니다.
코드를 비교해 보면, 크게 더 추가되는 것도 없습니다.
TC 가 N 개인 경우에는 새로운 TC 시작 지점에 index 초기화 코드가 있어야 하고, Alloc 하고 나서 이전 TC 수행시 할당된 값이 남아있지 않도록 각 멤버들을 잘 초기화만 하면 됩니다.
AIZU Online Judge 수행 결과도 비교해두었습니다.
Time / Memory / Code
00:43 s 26628 KB 1079 B -> 위 왼쪽 코드
00:36 s 18872 KB 1119 B -> 위 오른쪽 코드 (static allocation 방식)
207 page 의 ALDS1_8_B Binary Search Tree II (code)
210 page 의 ALDS1_8_C Binary Search Tree III (code)
221 page 의 ALDS1_4_C: Dictionary (code)
9장 BOJ 추천 문제
https://www.acmicpc.net/problem/1764 듣보잡
https://www.acmicpc.net/problem/1269 대칭 차집합
https://www.acmicpc.net/problem/7785 회사에 있는 사람
https://www.acmicpc.net/problem/1302 베스트셀러
== 10 장 =====================================================
227 page 의 ALDS1_9_A Complete Binary Tree (code)
229 page 의 ALDS1_9_B Maximum Heap (code)
233 page 의 ALDS1_9_C Priority Queue (code, code_with_STL_priority_queue)
10 장 BOJ 추천 문제
https://www.acmicpc.net/problem/1927 최소 힙
https://www.acmicpc.net/problem/11286 절댓값 힙
https://www.acmicpc.net/problem/1655 가운데를 말해요
== 11 장 동적 계획법=============================================
245 page 의 ALDS1_10_A Fibonacci Number (code)
248 page 의 ALDS1_10_C Longest Common Subsequence (code)
<정오표 신청 내용: 251 page>
Visual Studio 에서 실행하는 경우 default stack 크기를 초과(1MB)하여 runtime error 가 발생하기 때문에 전역 변수로 변경해서 실행해야 합니다. (stack 크기를 늘이거나..)
int c[N + 1][N + 1];
int lcs(string X, string Y) {
// int c[N + 1][N + 1];
252 page 의 ALDS1_10_B Matrix Chain Multiplication (code)
11 장 BOJ 추천 문제
https://www.acmicpc.net/problem/9252 LCS 2
https://www.acmicpc.net/problem/11727 2 X n 타일링 2
https://www.acmicpc.net/problem/10942 팰린드롬
https://www.acmicpc.net/problem/1149 RGB 거리
https://www.acmicpc.net/problem/10844 쉬운 계단 수
== 12 장 그래프 ================================================
266 page 의 ALDS1_11_A Graph (code)
269 page 의 ALDS1_11_B Depth First Search (recursive, stack)
278 page 의 ALDS1_11_C Breadth First Search (code)
282 page 의 ALDS1_11_D Connected Components (code)
12 장 BOJ 추천 문제
https://www.acmicpc.net/problem/1260 DFS와 BFS
https://www.acmicpc.net/problem/11724 연결 요소의 개수
https://www.acmicpc.net/problem/1707 이분 그래프
https://www.acmicpc.net/problem/1199 오일러 회로
== 13 장 가중치 그래프 ==========================================
294 page 의 ALDS1_12_A Minimum Spanning Tree (code)
299 page 의 ALDS1_12_B Single Source Shortest Path I (code)
305 page 의 ALDS1_12_C Single Source Shortest Path II (code)
13 장 BOJ 추천 문제
https://www.acmicpc.net/problem/1922 네트워크 연결
https://www.acmicpc.net/problem/1647 도시 분할 계획
https://www.acmicpc.net/problem/1504 특이한 최단 경로
https://www.acmicpc.net/problem/1162 도로포장
== 14 장 고급 자료 구조 ==========================================
318 page 의 DSL_1_A Disjoint Set: Union Find Tree (code)
