꾸물꾸물 졔의 개발공부

🔎다익스트라 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 찾을 때 사용된다. 단, 음의 가중치를 가진 간선이 포함되어 있으면 안된다. 현실세계는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에서 활용하기에 매우 적합한 알고리즘 중 하나이다. 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 여러개의 최단 거리로 이루어져 있기 때문' 이다. 작은 문제의 답을 활용하여 큰 문제의 답을 도출해내기 때문에 다이나믹 프로그래밍을 활용한다. 즉, 다익스트라는 하나의 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 ..

배열이나 리스트에서 이분탐색을 이용해 특정 값을 찾을 때, 중복된 값을 포함하고 있을 수 있다. 그 중복값을 전부 찾거나 또는 그 중복값들을 활용해서 문제를 해결 하기 위해 upper_bound나 lower_bound를 사용한다. Upper bound와 Lower bound 모두 이진탐색을 활용한 알고리즘이기 때문에 이진탐색에 대해 알고 있어야 한다. Lower bound lower_bound는 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 반환한다. [left, right) 의 범위내에서, 특정 find값 보다 크거나 같은 첫번째 원소의 인덱스를 반환한다. 만약 그런 원소가 없다면 right 인덱스를 반환한다. 이 때 원소를 담고 있는 리스트는 모두 정렬된 상태여야 한다. 각각의 요소들 중 el..

🔎 이분 탐색이란? 이분 탐색은 이진 탐색, Binary Search 라고도 한다. 순차적 탐색보다 빠른 탐색을 위해 나온 방법으로 실제로 이분탐색의 시간복잡도는 순차적 탐색보다 낮다. 순차적 탐색 정렬된 배열 내에서 특정 원소를 찾기 위해 0번 인덱스부터 차례로 탐색 원소를 건너뛰는 일 없이 순차적으로 모두 탐색 이분 탐색 정렬된 배열 내에서 특정 원소를 찾을 때 인덱스 i부터 j의 중간값과 비교 중간값이 찾는 원소가 아니라면, 인덱스 i와 j를 다시 정해줌 인덱스 i와 j의 범위는 정할 때 마다 탐색 범위의 반으로 줄어듦 이분 탐색 방법 1. 처음 탐색 범위는 인덱스 0부터 끝까지이다. 해당 범위의 중간 인덱스를 mid로 둔다. 2. mid와 찾는 원소의 값을 비교한다. 찾는 원소와 mid 값이 같다..

플로이드 워셜 알고리즘 🔎 플로이드 워셜(Floyd-Warshall) 알고리즘 이란? '모든 정점' 에서 다른 '모든 정점' 까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것이 핵심 아이디어 📒 플로이드 워셜 알고리즘 구현 과정 모든 노드 간의 최단 거리를 구해야 하므로 2차원 인접 행렬을 구성한다. 가능한 출발 노드 → 도착 노드의 단계를 모두 수행하며 각 단계마다 거쳐가기 위한 경유 노드를 선택하고, 더 짧은 거리로 갈 수 있는 노드가 나온다면 거리의 값을 줄이는 과정을 반복한다. 다음과 같은 그래프를 2차원 인접 행렬로 나타내면 다음과 같다. 노드간 갈 수 있는 경로가 없다면 무한으로 표시한다. 목적이 노드간 최소 경로값을 구하..

DP ( 다이나믹 프로그래밍 ) 을 활용한, 최단경로 구하기 알고리즘 하나의 특정 정점에서 나머지 모든 정점으로의 최단경로를 구하는 알고리즘 음의 간선을 포함할 수 없기 때문에, 현실 세계에 사용하기에 매우 적합 DP를 활용하여, 현재까지 알고있던 최단 경로를 계속해서 갱신함