Hello

: )

2022년 2월 19일 토요일

프로그래밍 대회 공략을 위한 알고리즘과 자료 구조 입문 [책]


프로그래밍 대회 공략을 위한 알고리즘과 자료 구조 입문


책소개: 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)