Up There

다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 음의 간선을 포함 X 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나이다. 최단 거리는 여러 개의 최단 거리로 이루어져 있기 떄문에 다익스트라 알고리즘은 다이나믹 프로그래밍이다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 현재까지 알고 있던 최단 경로를 계속해서 갱신해 나간다. 작동과정 출발 노드설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 위 과정 반복. 다익스트라 알고리즘의 특징 그리디 알고리즘..

⭐️탐욕 알고리즘(Greedy Algorithom)이란? Greedy 는 '탐욕스러운, 욕심 많은' 이란 뜻. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 👉🏻탐욕 알고리즘 문제를 해결하는 방법 선택절차(Selection Procedure): 현재 상태에서의 최적의..

완전 탐색 알고리즘이란? 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미 이 방법은 무식하게 한다는 의미로 **"Brute Force"**라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법. Ex) 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000~9999 까지 모두 시도해보는 것이다. ( 최대 10,000번의 시도로 해결가능) 하지만, Computer Science에서 문재 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용. 사용된 알고리즘이 적절한가? (문..