Hello

: )

2022년 12월 29일 목요일

[147] 문제 풀이 강의 조언 정리 1

문제 풀이 강의 과정을 들으면서 강사님이 했던 말을 정리해 봅니다.

 * 강의 주제는 No internet, No 참고자료, 제한시간 상황에서 특정 알고리즘을 이용해서 푸는 방식이 아닌, 문제 코드를 잘 분석해서 요구하는 기능을 최적화해서 구현하는 스타일의 문제에 대한 강의


... 여러 문제 상황에 대해서 접근하기 쉽고 변형이 쉬운 방법을 익혀두는 것이 좋습니다. 예를 들어, 구간 합 구하기 문제를 봅시다.

구간 합 구하기 / https://www.acmicpc.net/problem/2042

 이 문제의 경우에 펜윅 트리를 이용할 수 있으면 좋겠지만, 구현하기도 어렵고, 응용이 필요한 경우에 변경이 쉽지도 않습니다. 하지만, Sqrt Decomposition 을 이용하면 구현하기도 더 쉽고 상황에 따라서 속도도 더 빠르게 됩니다. Sqrt Decompostion 을 잘 익혀두면 이 문제뿐만 아니라 다른 여러 타입의 문제에 대해서도 적용할 수 있으니 꼭 익혀두시기 바랍니다 ...


Sqrt Decomposition 을 익어 두어라.


관련 참고 자료: https://david0506.tistory.com/57





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)


2022년 2월 17일 목요일

다시 공부 시작

다시 공부 시작하려고 마음 먹은 날..

Stackoverflow 에러(Stack Overflow is currently offline for maintenance) 봤네요..

하지 말라는 뜻인가.. 😂...





2019년 6월 30일 일요일

C++ 이야기: C++ Core Guidelines

C++ 의 창시자 Bjarne Stroustrup (비아르네 스트로우스트루프?) 님과 ISO C++ 표준 위원회에서 오랜 기간 활동 해오고 있는  Herb Shutter (허브 서터) 님이 Editor 로 되어 있는 C++ Core Guidelines 라는 문서가 있네요.

C++ 을 어느 정도 알게 되면, 그냥 이 글을 읽어보는게 더 좋다고 하는데....... 😃
정말일까요? 😑

http://isocpp.github.io/CppCoreGuidelines/



Read the C++ Core Guidelines 를 통해서 해당 내용을 볼 수 있고, 한국어 번역작업이 아래 링크에서 진행 중입니다.

https://github.com/CppKorea/CppCoreGuidelines





* 참고1: 허브 서터 인터뷰 (https://jacking75.github.io/cpp-17-herb-sutter-interview/)

2019년 4월 12일 금요일

알고리즘 공부를 위한 블로그 이용법

BOJ 를 통해서 알고리즘 공부를 조금씩 하면서 필요한 것들을 정리해 두고 있고, 이 블로그에 있는 몇 가지 초보자들이 알아둬야 하고 쓰면 편한 것들을 이용하는 방법을 알려드리고자 합니다. 😆

찾기 편하게 하기 위해서 모두 번호를 붙여서 왼쪽 카테고리에 두었으니
Ctrl + F 키를 이용하여 찾으시거나, 직접 카테고리에서 보면서 찾으셔도 됩니다.

1) 알고리즘 문제 풀이를 시작하는 분들은 아래 방법을 추천드립니다.

[001] 알고리즘 공부 시작하기 좋은 조합

책을 살 필요도 없고, 예제 코드가 간결하게 잘 만들어져 있어서 배우기에도 좋다고 생각합니다. 기본적인 입출력 처리와 알고리즘 문제 풀이에 대한 이해를 BOJ 를 이용해서 해보실수 있습니다.

주로 많이 쓰는 방식을 이용하면 내가 남의 코드를 보기도 편하고, 남이 내 코드를 보기도 편합니다. 그러니, 예제 코드가 군더더기 없이 잘 만들어져 있으니 참고하시길 바랍니다.


2) 문제를 풀기 전에 (혹은, 문제를 선택하기 전에)..

이번 내용은 어떠한 문제를 선택해서 풀어야 하는가에 대한 고민입니다.

당연히 안 풀리는 문제가 더 많기 때문에 가급적 도움을 받을 수 있는 문제를 선택하는 것이 좋을 듯 합니다.

Google 로 검색하면 나오는게 많기는 하지만...

여튼, BOJ 문제는 출처가 있는 문제와 출처가 없는 문제가 있습니다.
그 중에 출처가 있는 문제에 대한 이야기를 하고자 합니다.

3052 번 나머지 문제를 보면 문제 하단에 아래와 같이 출처를 명시하고 있습니다.



COCI 라는 대회에서 출제된 문제라는 의미입니다.

출처가 있는 문제는 해당 문제가 사용된 대회 주최 측에서 여러가지 정보가 제공이 되는 경우가 많습니다.

먼저, Ctrl + F 후에 "COCI" 를 입력해서 해당 글을 읽어보세요.
아래와 같이 검색이 되니 선택하시면 됩니다.



대회 주최 측에 따라서 공개되는 데이터는 보통

1) 문제 내용
2) 문제 풀이 설명
3) 문제에서 사용된 전체 Test case (Test data)
4) 문제 정답 코드 (모범답안)
5) 문제 제출자의 정답 코드
6) 기타 (Test data generator 등등)

1) + 3) 번의 조합이 공개되어 있다면, BOJ 에 금방 문제가 추가가 됩니다.
=> 이 조합의 데이터가 있다면, 를 참고하셔서 요청하시면 됩니다. 😃

1) 번만 공개가 되는 경우에 BOJ 에서 Test data 를 직접 만들어야 하기 때문에 중요한 대회의 경우에 한해서만 추가가 되는 것 같습니다... 예) 한국정보올림피아드(KOI) 같은 경우

일단, 문제 추가가 된 후에는 여러 고수분들이 해보시면서 Test data 를 추가해 달라고 요청하는 경우가 많습니다. 이런 경우는 아래와 같은 것 같습니다.

- 특정 코너 케이스를 잡아내지 못하는 경우
- 입력 데이터가 한계치까지 만들어지 않은 경우 (예, NlgN 시간복잡도의 알고리즘으로 시도시에 통과가 되도록 의도한 문제이나, N*N 시간복잡도의 알고리즘으로도 풀리는 경우)

BOJ 에 오래시간동안 많이 풀려진 문제는 아주 잘 다듬어져 있다고 보시면 됩니다.


제가 초보자에게 추천드리는 방식은 문제를 푼 사람이 많으며, 출처가 있는 문제를 선택하시라는 의견을 드립니다.


3) 문제 풀이 환경에 대해서...

처음 시작하시는 분들은 Windows OS + Visual Studio Community 를 이용하실 것을 권합니다.

Visual Studio 만큼 편하게 디버거를 쓸 수 있는 환경은 없다고 생각합니다.

생각대로 코드가 동작하는지 변수값은 제대로 들어가 있는지 보면서 코드를 잘 따라가실 수 있습니다.

그리고, 입출력을 아래와 같이 파일 기반으로 해두면 출처에서 받은 Test data 를 넣어보면서 코드가 잘 동작하는지 시도해 보기에도 편합니다.

여러 TC 중에 하나를 선택해서 input.txt 에 붙여넣고 난 후에 output.txt 에 결과값이 동일하게 나오는지 보면 됩니다.

- [020] Visual Studio 에서 입력 간편하게 처리하기
- [072] Google Code Jam 문제 정리 / Visual Studio 맞춤 설정 방법


4) Test data 를 만들어 보는 것...

공개된 Test data 를 보기 전에 (혹은, 공개된 것이 없다면..) 직접 간단히 만들어 볼 수도 있습니다. 간단한 것은 수작업으로 만들어도 되지만, 100 * 100 크기의 데이터를 만들어야 한다면 쉽지 않은 일입니다. 그 때는 간단히 웹인터페이스를 이용하는 아래 방법을 사용해보시는 걸 추천드립니다.

- [093] 간단히 test data 만들어 보는 방법 (1)
- [117] 간단히 test data 만들어 보는 방법 (2)

큰 데이터를 만들기 위한 설치형 애플리케이션입니다.

- [133] 간단히 test data 만들어 보는 방법 (3)

Test data 가 공개되어 있지 않은 문제를 풀던 중에 계속 "틀림"으로 나와서 너무 고민을 많이 했는데, 입력 최대 크기 1000*1000 데이터를 만들어서 실행해보니 단순한 버퍼 사이즈 문제라 허탈했던 기억이 나네요.

저장시에는 문서형식을 Unix/Linux 로 하여 한 줄의 끝이 \n 으로 끝나도록 해주세요.
Dos 형식으로 저장하여 \r\n 을 사용하시면 안 됩니다.

BOJ 의 채점 서버는 Linux 기반이니까요.