david의 CS Blog 자세히보기

공지사항

블로그 소개 & 알고리즘 정리

david0506 2021. 2. 11. 11:37

david의 CS 블로그

 

안녕하세요! 알고리즘과 CV를 위주로 다루는 블로그입니다. 이 블로그는 알고리즘을 공부하면서 익혔던 개념, 테크닉, 대회 경험 등을 정리하고자 하는 목적에서 시작되었습니다. 지금은 알고리즘 과외, 멘토링을 위한 자료 등을 업로드하거나 CNN 공부 내용을 정리하고 있습니다.

 

 

 


 

 

 

아래는 알고리즘 공부를 위한 가이드라인입니다. 주관적으로 작성된 기준이며, 필요에 따라 원하는 내용을 순서 상관 없이 공부하셔도 좋습니다!

 

 


 

 

1. Introduction. Algorithm이란?

 

         - Algorithm의 분석과 성능의 점근적 표기법(시간복잡도)에 대해 알아보며 알고리즘 공부를 시작합니다.

 

2. Search.

         - 가장 기본적인 알고리즘은 해를 구하기 위한 탐색

 

 

 

3. 정렬과 자료구조

         - 데이터의 구조화를 위한 Sorting과 Data Structure에 대해 학습합니다.

 

4. Graph & Tree

         - 가장 대표적인 비선형 공간인 그래프와, 특수한 형태의 그래프인 트리에 대해 학습하고, 탐색방법을 익힙니다.

 

 

5. 최적화 기법 : 동적계획법, 그리디, 분할 정복

        - 탐색을 최적화하여 해를 구하는 방법입니다. 구간을 분할하거나 데이터 조정을 통해 문제를 간단하게 해결하는 것이 핵심입니다.

 

 

6. 기타

18. 투 포인터

 

중급

 

자료구조

19. union find

 

 

Graph 알고리즘 : 최단 경로를 찾는 방법, Graph를 Tree로 변형하는 방법 등에 대해 익힙니다.

20. 최소 신장 트리(프림, 크루스칼)

21. 최단 경로 알고리즘(다익스트라, 플로이드)

22. 벨만 포드 알고리즘

23. 위상 정렬

24. LCA 알고리즘

 

동적계획법 : 기존의 동적계획법이 결과만을 구하는 방법이었다면, 이제는 그 해를 구하기 위해 고른 원소, 즉 과정을 구하는 방법에 대해 연습합니다. 아울러 특이한 기법에 대해 탐구합니다.

25. 동적계획법(경로 역추적)

26. 동적계획법(비트마스크)

27. 동적계획법(TreeDp)

 

기하

28. convex hull

29. 스위핑

 

쿼리

30. segment tree(세그먼트 트리)

31. segment tree lazy propagation

32. fenwick tree

33. merge sort tree(머지 소트 트리)

34. offline query(오프라인 쿼리)

 

고급

 

그래프

35. 네트워크 플로우 

36. 이분 매칭

37. SCC(강한 연결 요소)

38. 단절점

39. 단절선

40. 2-SAT

 

문자열

41. KMP 알고리즘

42. 라빈 카프 알고리즘

43. 트라이 알고리즘

44. 아호 코라식 알고리즘

 

쿼리

45. 평방 분할(sqrt decomposition)

46. Mo's algorithm

47. 병렬 이분 탐색

48. Dynamic Segment Tree

49. Persistent Segment Tree

트리

50. Heavy Light Decomposition

51. centroid decomposition

 

탐색

52. 삼분 탐색

 

수학

53. FFT 알고리즘

54. 폴라드 로 알고리즘

 

동적계획법 최적화

55. convex hull trick

56. slope trick

57. hirschberg algorithm