탐색 알고리즘
탐색 알고리즘에 대해 정리해 놓은 글
선형 탐색
- n개면 O(n)
이진 탐색
- 반씩 줄여나가므로 O(log n)
너비 우선 탐색
- FIFO 구조로 큐를 이용한다
깊이 우선 탐색, 백트레킹
- 스택을 써도 된다.
재귀함수에서도 엄청 들어가다가 너무 들어갔다 싶으면 중간에 나오는 방법도 있음.
재귀함수는 반복적인데 n의 횟수가 가변적이면 쉽지 않다. 재귀함수만 부르면 스택에 재귀함수가 계속 쌓임. 스택오버플로우가 일어날 수 있음. 이건 에러.
재귀는 마스터해야한다.
벨먼 포드 알고리즘
다익스트라 알고리즘
dijkstra
다익스트라 알고리즘
단일 출발점에서 양의 가중치를 갖는 그래프에서의 최단 거리를 구하는 알고리즘