WIL 항해W5 자료구조/알고리즘 4주차

자료구조/알고리즘 4주차

 

알고리즘 마지막 주차

 

이번주에는 이진탐색, 최단경로, 다이나믹 프로그래밍을 배웠다.

마지막 주차라서 그런지 난이도도 상당히 높았다.

 

이진탐색

데이터가 정렬되어 있는 배열에서 특정한 값을 찾아낼 때,

반절씩 범위를 좁혀나가서 원하는 데이터를 찾는 알고리즘이다.

 

1에서 100까지 숫자 중에

친구가 임의 값을 고르고, 내가 그 숫자를 맞추는 게임을 한다고 할때

 

내가 50을 말하면, 친구는 up 이나 down 중에 말하게 된다.

up이라 말하면

나는 50 ~ 100 범위에서 반절인 75를 물어본다. 

down이라 하면

50 ~ 75 범위에서 중간인 58을 물어본다.

down이라 하면

50 ~ 58 범위에서 중간인 54를 물어본다.

up이라 하면 

...

이런식으로 답을 찾아내듯이 

 

중간 값을 구하고 값을 비교하여 중간에서 뒤쪽이나 앞쪽을 버리면서

값을 찾을 때 까지

or 남는 값이 없을 때(찾는 값이 배열에 없음) 까지 반복한다.

 

 

아래 그림은 이진 탐색으로 원하는 숫자 77을 찾는 과정이다.

이진탐색 예시(https://namu.wiki/w/이진 탐색)

 

최단 경로

최단경로는 그래프 이론에서 두 노드 간의 가장 짧은 경로를 찾는 알고리즘으로,
가중치의 합이 최소가 되도록 하는 경로를 찾는 문제이다.

지도 앱에서 빠른 길을 찾을 때 많이 사용된다. 

각 도로 구간에서 소요되는 시간이 각 엣지의 가중치라고 할 수 있다.

다익스트라 알고리즘 (출처 : https://www.researchgate.net/figure/Illustration-of-Dijkstras-algorithm_fig1_331484960)

위의 그림에서

1에서 9까지 최단 경로를 찾아보면

1에서 갈 수 있는 노드들 중에 

가장 가까운 2를 방문하고, 2에서 갈 수 있는 노드들의 최소거리를 측정한다.

방문 안한 노드 중에 가장 가까운 노드인 5를 방문하고, 5에서 갈수있는 노드들의 최소거리를 측정하고

해당 노드의 기존 최소 거리보다 작으면 업데이트 한다.

 

인공지는 분야에서도 이 알고리즘을 변형하여 균일 비용 탐색 등에 사용된다고 한다.