기억을 위한 기록들

2021.02.03 첫 작성 2021.03.30 수정 1. 목표점 - 다익스트라는 시작점으로부터 나머지 정점들까지의 최단거리를 구한다. - A* 는 시작점이 정해지고, 목표점이 정해지면 두개의 최단 거리를 구한다. 2. 남은 거리 고려 - 다익스트라는 시작점에서 정점에 이르는 최단 거리만을 고려. 목적 정점이 없기에 남은 거리를 구할수도 없다. - A* 는 고려한다. 3. 최적 경로 - 다익스트라는 임의의 시작점으로부터 시작하여 모든 정점을 탐색. 최적 경로 보장 하지 않는다. (* 이를 해결하기 위해 모든 정점을 시작점으로 가지는 플로이드와샬 알고리즘이다 있다. 하지만 정점의 개수만큼 시간비용이 증가한다.) - A* 는 시작지점부터 목표지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를..

hyo-ue4study.tistory.com/193 [알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로 hyo-ue4study.tistory.com 다익스트라 알고리즘과 비교 다익스트라 알고리즘은 하나의 정점에서 출발해서, 출발한 정점을 제외한 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 하지만, 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 플로이드 와샬 알고리즘이 있다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 ..

트리의 형태로 생성과정으로는 "이진 공간 분할 법은 하나의 공간을 특정한 최종 목적을 만족할 때까지 공간을 재귀적으로 2개씩 분할하는 과정이다. 예를 들면, 충돌 감지를 목적으로 하는 경우에는 원래 물체가 충분히 충돌 검사를 간단하게 할 수 있도록 공간이 분할되며 렌더링을 목적으로 하는 경우에는 화가 알고리즘을 가장 효율적으로 사용할 수 있도록 볼록한 도형으로 공간이 분할된다." 응용 방법 www.youtube.com/watch?v=1syQjkWeRZ0&ab_channel=Seunggeunjo www.youtube.com/watch?v=FO12bZD3a5M&ab_channel=%EC%8B%A0%ED%98%95%EC%A2%85 아직 구현 해본적은 없지만, 나중에 필요로 할 때, 예를 들어 로그라이크 같은 ..

트리의 자식 노드가 4개인 트리를 뜻하고 있다. 3D 데이터를 표현하기 위한 자료구조를 '장면 그래프( Scene Graph )'라고 부르는데, 이도 역시 그에 포함된다. 장면 그래프( Scene Graph )에는 쿼드 트리 이외에도 이진트리(2)와 옥트리(8)가 존재한다. 말 그대로 이진트리는 자식노드가 2개, 옥트리는 자식 노드가 8개가 있는 트리를 의미한다. 쿼드 트리는 일반적으로 상하 개념이 없어서 3차원 세계를 4개의 평면으로 분할하지만, 옥트리는 4개로 분할한 쿼드트리에서 상하의 분할 평면으로 나누어 총 8개의 자식 노드를 갖게 된다. 일반적으로 지형( Terrain )에 사용된다. 정의 : 공간을 재귀적인 호출로(Recursive ) 4개의 자식 노드로 분할하는 방법 지형으로 설명을 하자면 ..

qiao.github.io/PathFinding.js/visual/ PathFinding.js qiao.github.io 길찾기 알고리즘의 다양한 방법들이 있는데 어떻게 동작하는지 보기 쉽게 표현되는 사이트 시작점 도착점을 드래그로 옮길수 있으며, 빈블럭을 클릭 시 벽이 생깁니다. 오른쪽 UI "Start Search"로 시작

"오던 길을 따라 되돌아 나오다"라는 뜻 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘. 후보해 속에서 해를 찾아가는 과정 1. 루트에서부터 출발 2. 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻습니다. 3. 2번에서 얻은 목록의 부분해들을 하나씩 방문합니다. 4. 방문한 부분해가 해가 요구하는 조건을 만족시키면 그 자리에서 2번 3번 과정을 수행, 그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도 5. 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없을음 확인했을 때까지 2~4번 과정을 반복

기존 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조이다. 여기서 새로운 속성인 간선간의 가중치(Weight)를 부여해주게 된다. 최소 신장트리에서 신장트리(Spanning Tree)에서 Spanning는 여러 가지 뜻을 갖고 있지만, 떨어져 있는 둘 사이를 다리 등으로 연결한다는 뜻으로 사용. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리이다. 신장트리는 한편으로 그래프의 하위 개념이기도 합니다. 그래프는 사이클을 형성하는 간선만 제고하면 트리로 됩니다. 최소 신장트리란 결국 최소 가중치 신장트리라고도 불립니다. 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리인것이다. 보통 "최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라"라는 문제..

다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다. 다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능. 동작 방식 1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화한다. 2. 시작 정점의 경로 길이를 0으로 초기화 하고(시작에서 시작까지는 0이므로), 최단 경로에 추가한다. 3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가. 만약 추가하려는 인접 정점이 이미 최..

그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해나가는 것이 특징입니다. 작동 순서 1. 그래프 내의 몯느 간선을 가중치의 오름차순으로 목록을 만듭니다. 2. 1번에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가합니다. 단, 이때 추가 된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안됩니다. 해결해야 할 문제 최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지 할 것인가? 대안 각 정점들을 각각의 집합 안에 입력하고, 간선으로 연결되어 있는 정점들에 대해서는 합집합을 수행. 이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 이 연결은 사이클을 이루게 됨. 예제 사이클 탐지의 문제를 해결 했으니 예제를 통해 ..

최소 신장 트리를 만들어 내는 과정 1. 그래프와 최소 신장 트리를 준비. 이때의 최소 신장트리는 노드가 하나도 없는 상태 2. 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다. 3. 삽입되어 있는 정점들과 모든 인접 정점 사이에 있는 간선의 가중치를 조사. 간선 중 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장트리에 삽입. 단, 새로 삽입되는 정점은 최소 신장트리에 삽입되어 있는 기존의 노드들과 사이클을 형성 하면 안됨. 4. 3의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘 종료 예제 위와 같은 그래프가 있다. 여기서 임의의 정점 B를 시작으로 루트로 정해보자. 그 주위에 정점 A F C 로 가..

플러드 필 혹은 시드 필은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다. -출처: ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84 플러드 필 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 4방향 재귀적 플러드 필 플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그 ko.wikipedia.org

위상이란?? 즉, 어떤 정점이 다른 사물과의 관계 속에서 가지는 위치나 상태를 말한다. 그래프안에서 인접해 있는 정점 사이의 관계의 '위치'라는 속성이 존재. 그러므로 위상 정렬이 가능하려면, 첫째로 그래프에 방향성이 있어야하고, 둘째로는 그래프내에 사이클이 있어야한다. 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다. DAG 그래프 예 위상정렬은 두 정점이 이웃 또는 인접관계에 있다는 사실뿐만 아니라 간선이 방향성을 가지는 경우에는 어느 정점이 선이고 어느 정점이 후인지도 설명합니다. 정점은 두 가지 종류의 방향성 간선을 가질 수 있는데 그중 하나는 정점으로 들어가는 진입간선과 다른 하나는 진출 간선입니다. 1. 리스트 하나를 준비 2. 그래프에서 진입 간선이 없는 정점을 리..