나만의 블로그를 만들어 보세요

스택(Stack) 자료구조의 한 종류로 나중에 삽입된 원소가 먼저 삭제되는 LIFO(Last In First Out) 성질을 가지고 있다. 스택에서 연산이 일어나는 끝 부분을 top이라고 하며, top에서 삽입(push), 삭제(pop)가 일어난다. 시스템에서는 함수 호출이 일어난 이후 가장 최근 호출된 함수로 돌아가기 위해서 사용된다. =>스택 메모리의 스택이 이 녀석임. 스택(Stack) 구현: 배열 배열로 구현된 코드는 다음과 같다. #define MAX_SIZE 1000 #include using namespace std; int stack[MAX_SIZE]; int top = 0; bool IsEmpty(); bool IsFull(); void Push(int num); int Pop(); in..

다익스트라(Dijkstra) 알고리즘이란? 최단 경로를 구하는 알고리즘 중 하나. 단일 소스(하나의 노드)로부터 출발하여 나머지 노드까지 가는 데 최단 경로를 구하는 방법이다. 단, 음수 가중치가 있을 경우에는 사용 불가 알고리즘 동작 방식 다익스트라 알고리즘은 하나의 노드에서 그 노드와 가장 가까운 경로를 fix하는 데서 출발한다. 최소 신장 트리를 찾는 알고리즘 중 prim 알고리즘과 유사한데, 차이점이 있다면 prim은 현재 노드에서 가중치가 적은 노드를 찾는 반면 다익스트라는 시작 노드로부터 가중치가 적은 경로의 노드를 골라야 한다는 데에 있다. 좀 더 쉬운 이해를 위해 예시를 보도록 하자. 0 1 2 3 4 5 6 0 4 2 1 INF INF INF 시작노드 0을 기준으로 나머지 노드로의 가중치..