알고리즘 스터디 준비 - 기본적으로 알아야 할 것들 2. 주요 알고리즘 유형
1. 그리디 - 탐욕법
- 현재 상황에서 가장 좋은 것만 고르는 방법
- '사전에 외우고있지 않아도 풀 수 있을 가능성이 가장 높은 문제 유형'
- 그러나 매우 다양한 유형으로 인해, 항상 잘 풀리는 것은 아닌 유형
2. 구현
- 생각을 소스코드로 만들어내는 과정
- 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 직접 수행하는 것
3. DFS (Depth-first search) / BFS(Breadth-first search)
- 탐색과 자료구조(스택, 큐 등) 등 기본지식 필요.
- 가짓수를 먼저 보는 경우 / 깊이를 먼저 보는 경우
4. 정렬
- 데이터를 특정 기준에 따라 나열하는 것.
- 선택정렬, 삽입정렬, 퀵 정렬, 계수 정렬
5. 이진 탐색
- 순차 탐색 : 리스트 안에 있는 데이터를 찾기 위해 앞에서부터 하나씩 확인하는
6. 다이나믹 프로그래밍(=동적 계획법)
- 기저사례 : 재귀함수의 종료조건 쯤으로 이해하면 될 듯.
- 메모이제이션 : 값을 리스트 등에 저장해서 값이 있으면 굳이 연산하지 않는 것.
- 로직 : 경우의 수에 따라 움직이는 방법의 수
- 초기화 : 보통 0 또는 -1 이라는데, 아직 정확히는 와닿지 않는다.
7. 최단 경로 (=길찾기)
- 다익스트라
- 플로이드 워셜
- 벨만 포드
8. 그래프 이론
- 서로소 집합
- 신장 트리
- 크루스칼 알고리즘
- 위상 정렬 알고리즘
음.. 뒤로 갈수록 아예 뭔지도 모르겠다. 그래도 하다보면 발전이 있겠지. 우선은 방향이라도 잡자.
- 더 잘 정리해주신 글이 있어서 참고