항해99 5주차 WIL - 알고리즘 파이널

✅ 이번주에 배운 것들 : 이진탐색, 최단경로 (다익스트라, 플루이드 워셜), DP

 

이번주에는 알고리즘의 꽃이라고 불리는 이진탐색, 최단경로 및 DP를 마지막으로 배웠다.

이진탐색의 경우, 탐색의 범위를 절반씩으로 줄이며 원하는 해당 값을 찾아나가는 개념인데, 시간복잡도 logN으로 진행이 가능하여, 비교적 인풋값이 큰 알고리즘 문제의 경우 이진탐색을 고민해봐야 한다.

문제를 풀면서 헷갈렸던 부분이 이진탐색의 경우 start, end라는 인덱스의 양끝 값을 기준으로 mid값으로 원하는 값의 범위를 찾아나가는데 이진탐색을 종료하는 부분에 대한 것이었다. 문제마다 다른 점이 있겠지만 세 포인터가 겹칠때 마지막으로 확인 후 알고리즘을 빠져나가게 설계되는 부분이 처음에는 이해가 되지 않아서, 어려웠지만 문제를 풀면서 이해가 된 것같다.

 

최단경로의 경우, 다익스트라와 플루이드 워셜 두 가지 방법의 알고리즘을 배웠다. 다익스트라의 경우 시간복잡도는 O(v^2) 또는 O(ElogV)이다. 음수 간선은 사용이 불가능하여 음수간선이 있는 경우 다른 알고리즘을 사용해서 풀어야한다. 또한 노드의 가중치가 있기 때문에, 우선순위 큐를 통해서 접근할 경우 보다 수월하게 문제 풀이가 가능하다. 기본적으로 푸는 방법은 노드에 대한 정보를 담는 리스트와, 최단 거리 테이블을 무한으로 초기화 하고, 방문여부를 체크하는 리스트 3개를 가진 후 방문하지 않은 노드 중, 최단 거리가 짧은 노드의 번호를 선택 후 반환하는 식으로 이루어진다. 

 플루이드 워셜의 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 때 쓰이며, 시간복잡도가 N^3로 보다 길다. 플루이드 워셜은 모든 지점에 대한 최단 경로이기 때문에 a에서 b로 갈 경우 a>b, k라는 중간지점을 통해서 갈 경우 두 가지의 케이스가 있으므로 min내장함수를 통해서 더 짧은 값을 뽑아낸다. 

 

다이나믹 프로그래밍은, 기본적으로 재귀를 생각해보면 재귀에서 모든 노드를 방문함에 따라 많은 시간과 계산이 소요되기 때문에 이를 메모이제이션(기억해서 저장해둔다)과 잘게 쪼개는 방법으로 풀어낼 수 있다. 위 세가지 알고리즘은 알고리즘 문제의 정수이기 때문에 각 알고리즘 별로 보다 제대로 된 정리를 할 예정이다. 알고리즘 마지막 주차에 어려운 문제들을 만나서 정말 힘들고 어려웠지만, 그럼에도 좋은 조원들을 만나서 끝까지 제대로 완주한 것 같다. 앞으로 다가올 주특기도 열심히 준비해서 좋은 결과를 만들어 내고 싶다.