GOOD DAY TO CODE: 2월 2022

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

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

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; }

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)

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, 수행 속도도 더 빠릅니다.

코드를 비교해 보면, 크게 더 추가되는 것도 없습니다.