[알고리즘 공부 방법] 나는 어떻게 알고리즘 공부를 했을까? - 최백준 님

나는 어떻게 알고리즘 공부를 했을까? - 최백준 님

가끔씩 다시 봐도 참 좋은 자료라고 생각됩니다. 제가 중요하다고 생각하는 부분만 캡쳐해보았습니다.

글 하단의 링크를 클릭하면, 최백준님의 전체 발표자료를 볼 수 있습니다.

 

영어

- 초등학교 5학년 때 처음 영어를 배웠습니다.

- 영어 문법은 중학교 3학년 때 배우기 시작했고요

- 토익을 준비했습니다

- 그래서 토익을 대비하는 학원을 다녔습니다

- 그런데 영어는 아직도 못해요 ㅋㅋㅋ

- 다른 길을 찾아보고 싶은데, 영어는 해야해요

- 그래서 아직도 영어 공부를 해요

 

언제보다 중요한건 어떻게

 

알고리즘 공부하기

- 알고리즘을 아는 것도 중요하지만 구현해보는 것도 중요

- 내가 제대로 구현했는지 확인해봐야함

- 사실 알고리즘은 어떤 문제를 푸는 과정이라서

- 문제를 풀기 위해 탄생한 알고리즘이기 때문에

- 문제를 풀어보지 않으면 반쪽자리 공부!

- Dijkstra, Kruskal과 같이 유명한 알고리즘만 알고리즘은 아니다!

설명하기

- 가장 효과를 본 방법이 설명하기

- 설명을 들을 사람이 없으면, 혼자 종이에 설명해보는 것도 좋음

- 아니면, 알고리즘을 공부하지 않는 사람을 이해시켜보는 것도 좋음

- 혼자 공부할 때 빼먹었던거나

- 상대방의 질문을 통해서 무엇인가를 얻을 수 있음!

- 복습하는 효과도 추가~

- 앞에서 하는 발표는 준비를 해야 하기 때문에 강제로 공부해야함

- 설명에서 가장 중요한 것은 대화

- 설명해줄 때 모른다고 뭐라고 하지 않기

- 설명해줄 때 이해 못한다고 뭐라고 하지 않기

- 설명들을 때 질문도 함께 하기

- 비슷한거 또 질문한다고 뭐라고 하지 않기

 

질문하기와 설명하기에서 주의해야 할 점

- 바로 수평적인 상황을 유지해야한다는 것

- 내가 자라온 환경은 거의 항상 수평적이었는데

- 아닌 환경에 있는 사람도 매우 많을 것임

- 꼭 알고리즘만 그런 것은 아니겠지만

- 나이가 많다고 잘하는 것도 아니고

- 오래 했다고 해서 잘하는 것도 아님

- 어떤 사람이 다른 어떤 사람보다 모든 방면에서 뛰어날 수는 없음

- 나이가 많다고 해서 꼭 어린 친구보다 잘해야 할 필요는 없고

- 시작한지 오래되었다고 해서 꼭 얼마 안된친구보다 잘할 필요는 없음

- 앞에서도 말했지만, 오기로 어떻게든 푸는건 절대 좋은 방법이 아님

- 제발 모르면 질문합시다!

결론!

1. 알고리즘 공부에 가장 효과적인 건? 문제 풀이!

2. 모르는 문제는? 질문한다!

3. 내가 가장 효과를 많이 본 방법은? 설명하기

4. 그래도 모르는 문제는? 풀이 찾아보기!

5. 공부는 누구와 함께? 다같이 함께

 

 

 

 

링크: 나는 어떻게 알고리즘을 공부했을까? + 신기한 방법으로 문제 풀어보기 de Baekjoon Choi

2015년 8월 29일 강남역 네이버 D2에서 열린 SOCC 6th Conference 에서 발표한 자료입니다.

첫 번째로는 많은 사람들이 언제 처음 공부를 시작했는지를 중요하게 생각하는데, 어떻게가 더 중요하다는 점을 강조하고자 했습니다.

두 번째로는 내가 어떻게 공부를 했었는지에 대한 방법을 소개했습니다.

마지막으로 신기한 방법으로 두 문제를 풀어봅니다.

https://www.acmicpc.net/problem/9457
https://www.acmicpc.net/problem/2329

 

출처: www.slideshare.net/Baekjoon/ss-52193873

 

 

 

 

 

 

이 블로그의 코드플러스(강사: 최백준) 강의 수강 후기

♠ 백준 알고리즘 코드플러스 강의(인강) 후기

백준 알고리즘 코드플러스 강의(인강) 후기

 

 

참고를 위한 요약 버전

 

1. 알고리즘과 입/출력

 

알고리즘을 공부하는 방법

시간 복잡도

입/출력을 받는 방법

 

2. 자료구조 1

 

스택

큐

덱

문자열 

 

3. 다이나믹 프로그래밍 1

 

4. 수학 1

 

나머지 연산

최대 공약수와 최소 공배수

소수

소인수분해

진법 변환

팩토리얼 

 

5. 정렬

 

STL의 sort를 응용하는 방법

O(NlgN) 정렬 알고리즘

퀵 소트와 머지 소트는 '분할 정복' 챕터

힙 소트는 '자료구조 2' 챕터 

 

6. 그래프 1

 

그래프를 저장하는 방법 세 가지 - 인접 행렬, 인접 리스트, 간선 리스트

인접 리스트: 시간과 공간이 더 효율적

효율적인 알고리즘 구현을 위해서 STL의 vector를 사용해서 인접 리스트를 구현

 

간선 리스트라는 자료구조

 

그래프의 탐색 - DFS / BFS

DFS와 BFS의 응용 - 연결 요소 / 이분 그래프

 

그래프에서 가장 중요한 것 => 문제를 그래프로 모델링

그래프 모델링을 연습하기 위해서 사이클을 찾는 연습

이차원 배열 상에서 플로드 필 알고리즘

 

7. 트리 1

 

트리를 순회하는 방법: 프리 오더, 인 오더, 포스트 오더

그래프와 마찬가지로 트리를 저장하는 방법 세 가지

트리의 부모에 대한 내용과 트리의 지름

 

8. 그리디 알고리즘

 

어렵지만 풀 수 있다

증명이 중요

 

잘하는 방법은 다양한 문제를 푸는 것 

 

9. 분할 정복

 

문제를 분할한 다음 합쳐서 문제를 푸는 알고리즘

 

대표: 이분 탐색 알고리즘 / 머지 소트 / 퀵 소트

가장 가까운 두 점을 찾는 방법: 분할 정복 알고리즘의 하이라이트

 

10. 이분 탐색으로 정답 찾기

 

정렬된 리스트에 어떤 수가 있는지 없는지를 조사하는 알고리즘

주로, 정답을 구하기는 어려운데 정답을 검증하기 쉬운 경우에 이 알고리즘을 사용 

 

11. 완전 탐색 1 (모든 경우 다 해보기)

 

여섯 가지

 

• 부르트 포스(Brute Force)
• N중 for문을 이용해서 문제를 푸는 방법
• 순열을 이용해서 모든 경우를 중복 없이 다 해보는 방법
• 가장 중요한 알고리즘 중의 하나인 BFS를 이용해서 모든 경우를 다 해보는 방법
• 재귀 호출을 이용해서 백트래킹
• 비트마스크를 이용해서 모든 경우를 중복 없이 다 해보는 방법

 

12. 완전 탐색 2

 

정답이 될 수 있는 것만 다 해보는 (일부 경우만 다 해보는) 알고리즘

완전 탐색 1에서 배운 BFS를 덱을 사용해서 하는 방법

탐색의 규모가 너무 큰 경우에 문제의 크기를 절반으로 나누어서 푸는 중간에서 만나는 알고리즘 (Meet in the Middle) 알고리즘

 

13. 자료구조 2

 

스택을 조금 더 화려하게 사용

그래프 알고리즘 중에서 크루스칼을 배울 때 필요한 Disjoint-set

비트마스크

힙 - 최대 힙과 최소 힙 / 힙을 구현, 힙 소트

이진 검색 트리 (BST)

 

14. 다이나믹 프로그래밍 2

 

15. 수학 2

 

다른 문제를 풀 때 필요한 경우가 많아서 배우는 부분

a^b 제곱 연산

• 분할 정복 알고리즘을 이용해서 구하는 방법
• 이진수의 원리를 이용해서 구하는 방법

행렬

피보나치 - 피보나치 수를 구하는 다양한 방법, 피사노 주기, 피보나치 수의 다양한 성질, 피보나치 수를 행렬을 이용해서 구하는 방법

이항 계수 - 파스칼의 삼각형

카탈란 수

오일러 피 함수

두 수를 나눌 때, 나머지 연산을 어떻게 해야하는지 배움

확장 유클리드 알고리즘

순열 - 다음 순열 / 이전 순열 / 모든 순열 / 순열의 순서

 

16. 그래프 알고리즘 2

 

위상 정렬

최소 스패닝 트리 (MST) - 프림 / 크루스칼

최단 경로 알고리즘 -벨만 포드 알고리즘 / 다익스트라 알고리즘 / 플로이드 와샬 알고리즘

 

17. 트리 2

 

가장 가까운 공통 조상(LCA) - 직관적 구현 / 다이나믹 프로그래밍

임의의 두 정점 사이의 거리를 BFS 알고리즘보다 빠르게 구하는 방법

 

18. 구간의 최소값 구하기

 

그냥 다 해보는 방법

이차원 배열에 저장해서 구하는 방법

루트 N으로 나눠서 구하는 방법 (sqrt decomposition)

다이나믹 프로그래밍을 이용해서 구하는 방법

세그먼트 트리를 이용해서 구하는 방법

슬라이딩 윈도우 알고리즘 

 

19. 구간의 합 구하기

 

누적합을 이용

세그먼트 트리를 이용

펜윅 트리(바이너리 인덱스 트리)를 이용

구간을 업데이트하는 경우: 세그먼트 트리 나중에 업데이트 하기 (Segment Tree Lazy Propagation)

세그먼트 트리

BIT 

 

20. 세그먼트 트리 활용하기

 

구간의 최소값과 합을 구할 때 사용

분할 정복과 함께 세그먼트 트리를 사용

최소값을 찾는 방법을 이용해서 K번째를 찾는 방법 

 

21. 다이나믹 프로그래밍 3

 

비트마스크를 이용해 상태를 나타내고 그 상태를 다이나믹에 이용

한 문제를 5가지 서로 다른 점화식으로 풀기

 

22. 네트워크 플로우

 

네트워크 플로우: 가장 중요한 알고리즘

최대 유량을 구하는 두 가지 알고리즘 - Ford-Fulkerson / Edmond-Karp

이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합

그래프 모델링을 연습

 

23. 최소 비용 유량 (MCMF)

 

최대 유량 문제에서 최소 비용문제가 추가되면 최소 비용 유량 문제

그래프 모델링하는 연습

 

24. 그래프 알고리즘 3

 

오일러 회로를 구하는 방법

강한 연결 요소 (SCC)을 구하는 Kosaju's Algorithm과 Tarjan's Algorithm

DFS Tree

Tarjan's Algorithm 을 응용해 단절점과 단절선을 구하는 방법

2-SAT 문제 

 

25. 다이나믹 프로그래밍 4

 

트리 다이나믹

왼쪽과 오른쪽을 왔다갔다 하면서 푸는 다이나믹

다이나믹 점화식을 통해서 정답을 역추적하는 방법

확률 다이나믹

왼쪽과 오른쪽에서 시작해서 가운데로 모이는 다이나믹

 

26. 문자열 알고리즘

 

문자열 매칭 알고리즘: KMP, Trie, Aho-corasick, Suffix Array

 

27. 기하 알고리즘

 

원, 직선, 선분과 같은 도형에 대한 내용

다각형에 대한 내용

CCW 알고리즘: 선분의 교차를 판별하는 방법

어떤 점이 다각형의 내부에 있는지 아닌지, 다각형의 넓이를 구하는 방법

볼록 껍질(Convex Hull)을 구하는 방법인 그라함 스캔(Graham Scan)

라인 스위핑 알고리즘(Line Sweeping Algorithm) - 가장 가까운 두 점

로테이핑 캘리퍼 알고리즘(Rotating Calipers) - 가장 먼 두 점

겹치는 선분 문제

직사각형 N개의 합집합 

 

28. 알고리즘 게임

 

조합 게임(Combinatorial Game) 문제 중에서 Impartial Game 문제를 푸는 방법 

돌 게임(Subtraction Game)

님 게임 (Nim Game)

The Sprague-Grundy Function을 이용해 조합 게임 문제를 푸는 방법

다양한 님 게임 변형 문제의 Grundy Number

 

 

 

♠ 백준 인강 듣는 법 (백준 알고리즘 강의 - 코드 플러스)

백준 인강 듣는 법 (백준 알고리즘 강의 - 코드 플러스)