기억을 위한 기록들

다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다. 다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능. 동작 방식 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. 그래프에서 진입 간선이 없는 정점을 리..

배열이나 링크드리스트에서는 특정 데이터를 찾기위해 순차 탐색, 이진 탐색을 사용. 이진 탐색트리에서도 이진탐색을 사용한다. 근데 그래프에서는?? 이와같은 방법들이 쉽게 통하지 않는다. 대표적인 기법 2가지가 있다. 바로 깊이우선탐색과 너비우선탐색이다. 깊이 우선 탐색(DFS) (길 끝까지 깊이 들어간다.) 재귀활용 (or stack stl를 활용) 설명 : 최상단노드부터 말단 노드까지 빠르게 내려가면서 탐색하는 방법으로 보통 경우의 수를 확인 할 때 (사용 예: 바둑, 장기 등) 1. 시작정점을 방문표시 2. 해당 정점과 이웃하고 있는 정점중 아직 방문표시 없는곳을 선택하고 시작정점으로 삼고 dfs시작 다시 1번. 3. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2번. 4. ..

순차탐색 - 데이터집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘. - 한쪽 방향으로만 탐색을 수행한다고해서 선형 탐색이라고 부르기도 함. - 효율이 좋진 않지만, 높은 성능을 필요로 하지 않거나, 데이터집합의 크기가 작을 때 유용 자기구성 순차탐색 - 자주 찾는, 자주 사용하는 항목들을 다른 항목들보다 우선하여 접근하게 가까운곳에 배치한다. - 자주 사용되는 항목을 어떻게 선별하는가에 대한 세가지 방법 1. 전진 이동법(Move To Front) : 한번 탐색되면 무조건 가장 앞에 위치 시킴. 2. 전위법(Transpose) : 한번 탐색되면 앞칸으로 한칸씩 이동. 자주 탐색되면 앞으로 몰림 3. 빈도 계수법(Frequency Count) : 각 요소들이 탐색되는 횟수..

Least Recently Used 알고리즘이란? - 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법 - 컴퓨터의 자원은 한정적이며, 한도내에서 최고의 효율을 얻기 위해 여러 알고리즘이 존재, 그 중에 하나. (FIFO,OPT,LRU,LFU,MFU 등등..) 방법 첫번째 : 페이지에 저장 된 데이터가 언제 사용되었는지를 알 수 있게하는 부분을 구현해서 제일 오랫동안 참조되지 않는 데이터를 제거 하는 방법. 두번째 : 페이지에 데이터를 큐 형식으로 저장하는 방식. 페이지내에 데이터가 존재한다면 데이터를 페이지 내에서 제거하고 맨 위로 다시 올리고, 존재하지 않는다면, 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 과정을 진행. 예제 그림 위 그림에서 7번, 9번같은 상황은 참조하는 값이 이미 페이지에..

이런 표가 머릿속에서 저절로 떠오르면 참 좋을텐데... 아래 사이트에서 직접 해볼 수 있다. www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com

오름차순or 내림차순으로 정렬되어 배열이 있다고 하고, 정렬 되어 있는 배열에 특정값이 몇번 인덱스에 있는지 찾는 이진검색 알고리즘이 존재한다. 변수명 arr 배열(오름차순)을 넣고 15을 찾는다면 변수명 arr2배열에 주석부분을 서로 바꿔준 뒤 마찬가지로 15을 찾으면 사실 여기까지는 인터넷에 찾아보면 더 자세한 설명도 많이 나온다. 근데 내가 글을 쓴 이유는 순위 시스템에서 새로운 점수를 받았을때 해당 점수가 등수에 반영 가능한 여부를 판단하기 위해서 이다. 그러기 위해 이진검색을 조금 변경 해보았다. 내림차순인 변수명 arr2 배열에서 targetValue 새로운 점수인 70점이 순위에 드는지 여부를 확인하기 위함이다. 결과이다. 출력에 result+1은 실제 배열 인덱스와 우리가 인식하는 등수(1..

이전에 작성하였던 넓이우선탐색(BFS)은 말그대로 해당 그래프에 어떤 요소가 있는지 전체적으로 탐색한것이였다. 이제 여기서 좀 더 나아가 해당 그래프에서 시작점과 목표점를 정하여 해당 두 점이 이어져 있는지 확인하는 알고리즘을 확인해보자 . 이전에 작성했던 Graph 클래스에서 새롭게 추가 된 bool형을 반환하는 Search함수이다. 이제 이 함수를 이용해서 확인해보자. 이런 그래프가 있다고 하면 6과7이 나머지 노드들과 떨어져 있는 상태이다. 예를 들어 1에서 7까지 갈수 있는지 여부를 확인한다고 하면 결과가 0이 나온다(실패) 이제 이 노드들을 이어준다. 이렇게 5번과 6번 노드를 추가로 이어주고, AddEdget(5,6)을 추가해준 뒤 확인해보면 결과는 1로 출력된다.(성공) 여기까지는 이제 갈수..