WinCNT

A* 알고리즘 다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다 추정치를 안 쓰는 알고리즘 다익스트라 알고리즘으로 탐색하다가 지정한 목적지를 탐색했을 경우 탐색을 종료한다 메모리는 다익스트라보다 더욱 쓰지만 탐색 횟수는 줄어든다 하지만 탐색한 경로가 정말로 최단 경로인지는 보장할 수 없다 추정치를 쓰는 알고리즘 다음 노드로 이동하는 비용을 휴리스틱이라는 추정치로 두고 탐색하는 방법이다 현재의 비용 + 휴리스틱 비용으로 탐색한다 자주 사용하는 휴리스틱 함수는 휴리스틱 유클리드 맨하탄이다 SSS

참고 사이트 https://yabmoons.tistory.com/364 [ 다익스트라 알고리즘 ] 개념과 구현방법 (C++) 그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 사용할 수 있는 대표적인 알고리즘으로는 '다익스트라 알고리즘' , '벨만-포드 알고리즘' , ' 플로이드 워샬 알고리즘' 이 있다. 이번 글에서 yabmoons.tistory.com 다익스트라 (Dijkstra) 알고리즘 출발 정점부터 각 정점까지의 거리(비용)을 계산한 테이블이 필요하다 초기값은 무한대(...)나 음수를 두면 된다 방문하는 순서는 BFS와 같다 하지만 다익스트라는 큐가 아니라 우선순위 큐를 사용한다 (비용이 적은 노드를 먼저 뽑을 수 있게) 또한 방문한 노드나 그리드의 경로의 최소 비용을 알고 있는 테이블 등도..

BFS(너비 우선 탐색) 그래프를 탐색할 때, 깊이를 우선해서 탐색하면 깊이 우선 탐색(DFS, Depth First Search), 넓이를 우선해서 탐색하면 너비 우선 탐색(BFS, Breadth First Search)이라고 한다 BFS와 DFS의 차이 참고 사이트 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 사용처 최단 경로 찾기 미궁 자동 생성 BFS의 설계와 구현 인접한 정점(Vertex)에 대한 방문 규칙이 필요하다 그리드 방식에서 인접한 상하좌우를 방문할 것인지, 대각선도 포함할 것인지 등등 인접 정점들을 인덱스로 관리하면 셀(배열) 방식 인접 정점들을 리스트로 관리하면 노드 방식 어떠한 구조로 되어 있는가 = 자료 구조 어떻게 찾아가는가 = 알고리즘 BFS는 최단 거리를 찾을 때 사용..

보호되어 있는 글입니다.

셀과 노드 자료구조의 기반은 셀이거나, 노드 여러 자료 구조도 결국은 셀이나, 노드를 기반으로 만들었다고 볼 수 있다 cell = 데이터의 집합 = 배열 구조체, 배열... 선형적 인덱스로 찾기 노드 = 포인터로 연결 = 리스트 메모리(물리적)으로는 선형적이 아니지만 논리적으로는 선형적일 수도 있음 포인터로 찾기 트리 힙은 셀을 사용(효율 문제) 이진 트리 등은 노드 사용(효율 문제) 그래프 연관 관계를 만들면 그것이 그래프이다 서로 연결이 되서 탐색할 수 있다 (참고로 트리도 그래프의 일종) 그래프 기반의 탐색 그래프 기반의 탐색 ⇒ 경로 탐색 경로 탐색은 정점과 정점 사이의 경로를 탐색하는 것이므로 정렬은 하지 않는다 여태까지의 알고리즘은 보통 값을 탐색하는 것이었다 그러기 위해 삽입, 삭제, 탐색 ..

데이터는 0과 1(Bit)의 모음이지만 기본적으로 비트 단위로 데이터를 다루는 일은 없다 우리가 다루는 데이터의 최소 단위는 Byte이다 CPU의 레지스터가 가져가는 데이터의 단위 = WORD(2Byte)였다(16비트) 참고로 WORD는 윈도우즈에서만 썼던 단위이며 리눅스에는 없다(short를 씀) 멀티 플랫폼으로 개발할 경우에는 다루는 단위들이 다 다르니 type 재정의를 하는 경우가 많음 일반적으로 데이터는 CPU, 캐시, RAM를 오고 간다 변수는 메모리에 보관하며 메모리 => 캐시 => CPU로 데이터가 이동(Move)할 때 특정 단위로 오고 가고 할 것이다 캐시 메모리에서 이동하는 데이터의 단위를 캐시 라인이라고 한다 (CPU 메모리에서는 프레임(?)이라고 하는 것 같다...아마) 만일 메모리에..

해시 색인(Index)에 해시값을 사용하는 자료 구조 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다 해시 함수 Key를 해시(값)로 매핑하는 함수를 말한다 문제점 해시 함수는 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다 (이러한 경우를 해시 충돌이라고 함) 해시 충돌에 대비하는 방법으로는 개별 체이닝(Separate Chaining)과 오픈 어드레싱(Open Addressing) 등이 있다 개별 체이닝(Separate Chaining) 리스트의 각각의 색인을 연결 리스트로 만든다 새로 입력이 될 때마다 같은 해시를 가진다 하더라도 색인이 연결리스트로 구현되어 있기 때문에 원하는 데이터의 접근이 가능해진다 오픈..

페이지 교체 알고리즘은 왜 필요한가 프로그램을 실행(프로세스)시키거나 저장된 데이터를 오픈하거나 결국은 모두 메모리에 로드해야 한다 기준 - 실행 코드, 데이터 코드를 관리하는 메모리 영역과 데이터를 관리하는 메모리 영역은 다르다 메모장을 두 번 실행하면 OS가 각각 다른 프로세스 영역을 만든다 그리고 CPU 내부 메모리 영역(레지스터)에 가져와서 실제로 처리를 한다 레지스터도 실행(수행), 버퍼(데이터)로 나눠진다 하드 디스크는 느리고 크다 메모리는 프로세스 실행에 필요한 것을 자져온다 CPU는 당장 수행에 필요한 데이터를 가져온다 CPU가 메모리에서 데이터를 가져오는 데에도 시간이 걸린다 그래서 메모리보다 빠른 Cache라는 곳에 미리 필요한, 혹은 최근에 사용한 코드나 데이터를 넣어둬서 데이터를 가..

자료 구조를 선택할 때에는 그 목적을 확실히 할 필요가 있다 목적은 W(Insert, Update)과 R(Search)가 있다 자료 구조(Data Structure)는 선형적/비선형적으로 나뉜다 하지만 선형/비선형은 물리적인 구조 외에도 논리적인 구조도 포함할 수 있다 즉, List는 물리적으로는 비선형적이나 논리적으로는 선형적인 구조으로 볼 수 있다 (물리적인 구조로만 보면 Array만 선형적인 자료구조일 것이다...) 가장 자주 쓰는 것은 Quick Sort, 정확히는 STL의 std::sort (부분을 나눠서(Partial) 정렬하는 분할 정렬) Don't reinvent the WHEEL 하지만 툴을 제대로 사용하기 위해서는 제대로 알아야 한다 Tree는 논리적으로 비선형적인 자료 구조이다 트리는..

힙 정렬(Heap sort)이란 원소들을 전부 힙에 삽입한다. 힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다. 힙이 빌 때까지 2의 과정을 반복한다. B Tree B Tree는 이진 트리를 확장한 것으로 이진 트리는 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개지만 B-tree는 2개 이상을 가질 수 있다 모든 노드에 있는 값들은 정렬되어 있는 상태이며 order를 나타내는 숫자인 m을 가질 수 있다 이 B-tree 를 B-tree of order m 이라고 한다 B-tree of order m은 다음과 같은 조건을 만족 시킨다. 모든 노드가 가질 수 있는 자식 노드의 최대 수는 m이다. 루트 노드를 제외한 내부 노드 들은 적어도 [m..