도저히 Python으로는 다익스트라 알고리즘의 원리가 이해가지 않아 C++로 다시 개념을 정리하였습니다. 우선순위 큐를 사용하지 않는 코드 #include int number = 6; int INF = 100000000; int a[6][6] = { {0, 2, 5, 1, INF, INF}, {2, 0, 3, 2, INF, INF}, {5, 3, 0, 3, 1, 5}, {1, 2, 3, 0, 1, INF}, {INF, INF, 1, 1, 0, 2}, {INF, INF, 5, INF, 2, 0}, }; bool v[6];//방문한 노드인지 확인하는 배열 int d[6];// 거리 //가장 최소 거리 정점 반환 int getSmallIndex() { int min = INF; int index = 0; fo..

정의 다익스트라 알고리즘은 방향그래프에서 단일 출발점에서의 각 정점으로의 최단 경로를 구하는 알고리즘입니다. 알고리즘 문제에서 다익스트라 알고리즘은 가중치 그래프에서의 최단 경로를 탐색하는 문제입니다. 과정 1. 시작 노드에서 각 노드의 최소 비용을 저장한다. 2. 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다. 3. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 4. 위 과정을 반복한다. 위 과정을 진행하기 위해선 인접행렬 그래프를 사용합니다. 위와 같은 그래프가 있다고 가정할 때, 인접행렬로 그래프를 구성하면 아래와 같습니다. 0 2 3 INF INF INF 0 4 5 INF INF INF 0 6 INF INF INF INF 0 INF 1 INF INF IN..

그래프 정의 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조 연결되어있는 객체간의 관계를 표현할 수 있는 자료구조 지도, 지하철 노선도의 최단 경로 등.. 용어 정점 (노드) : 데이터가 저장 됨. 간선 (링크) : 노드간의 관계를 나타냄. 인접 정점 : 간선에 의해 서로 연결된 정점 단순 경로 : 같은 간선을 지나가지 않는 경로 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (몇개가 한 노드에 연결되었는가) 진출 차수 : 방향그래프에서 사용되는 용어로, 한 노드에서 외부로 향하는 간선의 수 진입 차수 : 방향그래프에서 사용되는 용어로 외부 노드에서 들어온 간선의 수 구현 방식 인접행렬 방식 : 그래프의 노드를 2차원 배열로 만든 것. {: width="50%" height..

트리 정의 계층적인 구조를 나타내는 자료구조 비선형 자료구조 (스트 , 스택, 큐 는 선형 구조임.) 트리는 부모 - 자식 관계의 노드들로 이루어짐. 1개 이상의 노드를 갖는 집합으로 노드들은 아래 조건을 만족함. root 라고 불리는 특별한 노드가 있음 다른 노드들은 원소가 중복되지 않는 n 개의 부속 트리 (subtree)임. 저장법 n-링크 표현법 노드에 n개의 링크를 두고 자식의 개수만큼 링크에 저장한다. 모든 노드는 자식 노드 수에 관계없이 최대 n개의 링크를 갖는다. 각 링크는 부속 트리가 저장된 곳을 링크한다. 왼쪽자식노드 - 오른쪽 형제노드 표현방법 (출처 : https://apape1225.tistory.com/57) 첫번째 링크는 첫번째 자식 노드를 표현 하고, 두번째 링크는 자신의 오..

우선순위 큐 정의 우선순위를 가진 항목들을 저장하는 큐 FIFO 가 아닌 우선순위가 높은 데이터가 먼저 나감. 시뮬레이션 시스템 네트워크 트레픽 제어 운영체제의 작업 스케줄링 ADT create() : 우선순위 큐를 생성함 init(q) : 우선순위 큐 q를 초기화 함 is_empty(q) : 우선순위큐 q가 비었는지 검사함 is_full(q) :우선순위큐 q가 가득 찼는지 검사함 insert(q, x) : 우선순위큐 q에 요소 x 를 추가함 delete(q) : 우선순위큐로부터 가장 우선순위가 높은 요소를 삭제함과 동시에 반환함 find(q) : 우선순위가 가장 높은 요소를 반환함 종류 최대 우선순위 큐 최소 우선순위 큐 구현 방법 배열을 이용 연결리스트를 이용 힙을 이용 힙(heap) 노드의 키들이 ..

Postfix2 이전 포스트에선 postfix로 변환되어있는 수식을 계산하는 코드를 작성하였는데, 이번 포스트에선 infix로 표현된 수식을 postfix로 변환하는 소스코드를 작성하고자 한다. Condition 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. Boj-1918 IDEA 문자열을 입력받아 앞에서부터 읽고 연산자는 스택에 넣은 후 뒤로 보낸다. 피연산자는 뒤로 보내지 않고 바로 출력한다. 괄호가 있다면 괄호도 연산자..