장윤's 개발세상

Dijikstra Algorithm이란?다익스트라 알고리즘은, 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다.일반적으로 잘 알려져 있는 방식은, 한 꼭짓점을 '소스' 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지 최단경로를 찾는다.알고리즘 구현 방식시작할 노드를 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 다익스트라 알고리즘은 초기 거리값을 부여하고,단계를 거듭하며 개선시킨다. 이 것을 간선완화(edge relaxation)이라고 한다.1. 모든 노드를 미방문상태(NULL)로 표기.2.모든 노드에서 미방문 인접 꼭짓점을 찾아 그 시험적거리를 현재 노드에서 계산한다. 새로 계산한 시험적거리를 현재 부여된값과 비교하여 더 작은 값을 추적한다.4.만약 현재 노드에 인접한 모든..

이진트리 데이터란?각 노드가 최대 두개의 자식을 갖는 계층적 데이터 구조입니다.이를 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)이라고 합니다.삽입, 삭제, 순회와 같은 다양한 작업을 통해 데이터를 효율적으로 저장하고 검색하는데 용이합니다. # Python3를 활용하여 배열을 사용한 트리 구현# 0~n-1까지 넘버링 시작tree = [None] * 10def root(key): if tree[0] != None: print("Tree already had root") else: tree[0] = keydef set_left(key, parent): if tree[parent] == None: print("Can't set child at", (parent * 2) + 1..

스택(Stack)은 연산이 수행되는 특정 순서를 따르는 선형 데이터 구조입니다.두가지 유형 FIFO(First in First Out)과 LIFO(Last in First Out)이 있습니다. 옆의 사진이 LIFO의 대표적인 구조입니다. 바구니와 같은 구조를 띄는 Stack에 데이터를 넣는(push) 구조입니다.  오른쪽의 사진이 FIFO의 대표적인 구조입니다. 사람이 옆으로 밀어넣는 구조를 띕니다.처음 넣은(push)데이터가 가장 먼저 나오는 구조입니다.     Stack 관련 용어는 카테고리에 게시하겠습니다.Referencegeeksforgeeks

DFS(Depth First Traversal)는 트리의 DFS와 유사합니다. 트리와 마찬가지로 모든 인접한 노드를 하나씩 탐색합니다.인접한 노드를 탐색할 때 마다 도달 할 수 있는 모든 노드를 탐색합니다.모든 노드를 탐색 한 후에 다음 노드로 넘어가 같은 과정을 반복합니다.이 모든 과정은 왼쪽에서 오른쪽으로 진행됩니다.예를 들면 정점노드가 1번, 1번 산하의 노드 2,3,4가 있다면, 왼쪽의 노드 2번부터 DFS를 실행합니다.하지만 트리와 다른점은, 노드를 두번 이상 반복 방문할 수 있습니다.(BFS와 동일)그렇기 때문에 이전에 올렸던 BFS의 알고리즘과 비슷하게 bool 방문 배열을 사용합니다. 0.초기 스택과 방문배열의 초기값을 NULL로 세팅합니다.1.0을 방문했을때, 방문하지 않은 근접 노드들을..

BFS(Breadth First Search)는 기본적인 그래프 탐색 알고리즘이다. 한 지정 노드에서 출발하고, 먼저, 가장 근접한 노드들부터 방문합니다.그 때, 그 중에서 가장 근접한 노드를 방문합니다.(->DFS와 차이점)그 후, 방문하지 않은 노드가 없을 때 까지 노드를 방문합니다.Kahn's Algorithm, Dijkstra's shortest path 와 같은 알고리즘이 이 BFS알고리즘을 기반으로 합니다. 트리와 마찬가지로 지정 노드에서 시작하는데, 이 때 문제점은 BFS는 지났던 노드를 다시 지나는 단점이 존재합니다.  BFS 작동 방식1. 처음의 큐와 방문한 배열은 비어있습니다.2.0을 큐에 넣고(push) 방문했음을 표기합니다.3.큐의 앞부분(front)에서 앞서 넣은(push)를 제거..