내일배움캠프 10일차 TIL + 알고리즘

오늘도 알고리즘에 대해 정리해보자.

탐색 알고리즘

이진 탐색

정렬된 배열 기준으로 값을 중간부터 비교하면서 그보다 크거나 작으면 해당 자리쪽으로 반 만큼 이동하며 찾는다.
시간 복잡도 : O(log n)

DFS (노드 = 2개의 vertex를 잇는 선)

그래프에서 한쪽 노드를 따라서 우선 그 끝을 탐색하고 다시 부모vertex로 돌아온다.
시간 복잡도 : O( 노드 수 + 층 수 )

BFS

같은 층에 노드들을 다 탐색하고 다음 층에 vertex들을 탐색한다.
시간 복잡도 : O( 노드 수 + 층 수 )

최단 경로 알고리즘 (vetex = 도착지점들)

가중치 그래프에서 시작 vertex에서 모든 vertex에 방문하는 가장 빠른 방법

Dijkstra’s algorithm

1. 시작 vertex에서 각 vertex까지 가중된 path들을 고려해서 도착 비용을 저장해둔다
2. 초기 값은 시작지점 0, 나머지 무한대
3. 그 뒤로는 가까운 vertex 부터 확인하여 그걸로 도달하는 vertex의 값을 수정
4. 다음 시작지점 vertex를 선택하고 이렇게 선택된 vertex는 목록에서 제외
5. 다음 vertex부터 가까운 vertex까지 초기 시작지점에서부터 거리 또 계산하여 표 업데이트

Bellman-Ford Algorithm

음수 가중치 path가 존재하는 경우

1. vertex들의 순서를 정한다.
2. 해당 vertex들을 (vertex의 수 - 1)만큼 순회한다.
3. 1회 순회 마다 순서대로 방문하며 다른 vertex로 갈 최단거리를 업데이트한다.
4. 이래도 정답이 안나오거나 수렴이 안되는 vertex는 최단거리가 없는 vertex다

A-star Algorithm (미로찾기)

heuristic 함수를 써서 도착지점까지 거리를 추가로 고려하여 탐색하는 방법
이럴려면 일단 도착지점의 좌표를 알아야한다.
예를들어 시작지점에서 현재지점까지의 거리 + 도착지점까지 직선거리를 계산해서 이 점수를 기준으로 짧은 거리를 탐색할 수 있다.
나중에 도착지점에 도착하고 나면 추가 계산으로 시작지점까지 경로를 찾아줘야한다.

동적 프로그래밍

찾은 값들을 저장하면서 다음 값을 찾는 방식 시간 복잡도 : O(n) 공간 복잡도 : O(n)

greedy 알고리즘

매번 최적값을 찾는 방식. 각 단계에서 최적값을 찾아간다.