Develop Develop

현존하는 정렬 알고리즘들 중에서 가장 느리다.이것은 일종의 잘 될 때까지 "무작정" 시도하는 알고리즘이라고 할 수 있다.마치 거품이 물 위로 떠오르는 것처럼 정렬이 된다고 해서 거품정렬..(오른차순으로 정렬을 할 경우) * 거품 정렬의 최악의 경우 오른차순 정렬인데 내림차순으로 되어 있는 경우.. 본질적으로 이중for루프 사용하고 정렬 알고리즘은 n^2에 속한다. 거품 정렬의 최적화2가지 염두해야할 사항이 있다.1. 함수가 하나의 반복에서 색인들을 한 번도 바꾸지 않았다면 이미 정렬된것이다.2. 알고리즘이 ?번 반복되었다면 상위 ?개의 색인들은 이미 정렬된 상태이다. 알고리즘 의사코드Bubblesort(Array)int swaps=1int top=Array.size-1;int indexwhile(top!..

DLDFS라고 불리우며 탐색이 어느 깊이까지 이루어질 것인지를 제어할 수 있다. 흔히 이야기하는 가시성판단?!알고리즘과 비슷하다고 하는데.. 주어진 구역과 주어진 시점에서 보이는 다른 구역들을 식별하기 위해서 쓴다. DepthFirst(Node, depth) if depth==0 then return Process(Node) Mark(Node) For Every Chlid of Node If NotMarked(Child) DepthFirst(Child, depth-1) End If End For End Function 굵은 글씨체로 나타는 코드가 원래의 깊이 우선 탐색과 다른 부분이다. 이 알고리즘은 깊이가 0이면 더이상 처리하지 않고 즉시 반환한다. 이후 함수가 자신을 재귀적으로 호출할 때에는 dept..

연결된 목록을 좀 더 융통성 있게 만들면 트리가 된다. (트리 역시 노드 기반 자료구조이고 연결된 목록과는 달리 각 노드가 여러 개의 자식 노드들이 있기때문에) (오직 하나의 자식만들 가진 트리가 연결된 목록이다) 트리를좀 더 융통성있게 만들면? 그것은 바로 그래프가 된다. 트리의 각 노드는 자시의 아래 수준의 노드만을 가리킨다. 이런 제한을 없애서 어떤 노드도 가리킬 수 있도록 하면? 그래프다. 그럼 역으로 .. 그래프에 수준(높이)라는 제한을 적용하면 트리가 되고, 트리에 하나의 자식 노드라는 제한을 적용하면 연결된 목록이 된다. 그래프의 종류 양방향 그래프 단방향 그래프 가중 그래프 타일맵(사이사이가 서로 양방향으로 연결..) 그래프의 구현방법 1. 2차원 배열 : 2차원 배열로 구현된 그래프의 호..

우선순위 대기열과 힙은 대기열와(큐) 이진트리에서 나온 이진트리에 기반을 둔 것이다. 우선순위 대기열과 힙은 게임프로그래밍에서 상당히 자주사용되긴하나 직접적으로 쓰이는것은 아니다. 어떤 문제의 해결에 도움을 주는 보조적인 자료구조로 쓰인다. 우선순위 대기열에서는 항목이 그냥 대기열의 끝에 차례로 추가되는 것이 아니다. 항목의 위치는 그 항목의 우선순위에 따라 달라진다.(즉 좀더 중요한 항목이 앞쪽에 위치함) 뽑는것은 일반 대기열과 같음 구현하는 방법중 가장 쉬운것은 연결된 목록(list)사용 그런데..느리다 이런 방법으로 우선순위 큐를 구현하는 경우는 거의없다 힙이라고하는 특별한 이진트리를 사용하면 좀 더 빠르고 효율적인 우선순위 대기열을 만들 수 있다. (그런데 이진트리를 또 연결된 목록으로 구현하면 ..

이진 검색트리(BST) 일반 트리와 달리 BST의 재귀는 자료가 어떻게 접근되는가가 아니라 자료가 어떻게 정렬되는가에서 더 중요 BST의 정렬에서 핵심은 자료를 반으로 나눔으로써 검색 공간을 줄인다. 검색하고자 하는 자료들이 대기열에 들어가 있다고 하자. 대기열에서 첫번째 항목을 뽑아 그것을 트리의 루트로 한다. 대기열에서 다음 항목을 뽑아서 루트와 비교하고 그것보다 작으면 왼쪽자식으로 크면 오른쪽 자식으로 만든다. 나머지 항목들도 동일한 과정반복 현재 노드보다 작으면 왼쪽, 크면 오른쪽 따라가다가 자식이 없는 노드를 만나면 그 노드랑 비교 왼쪽 오른쪽 자식에 추가 자료검색또한 위의 과정과 동일하게 하면된다. 3을 찾는과정이라면 루트가 만약 4라면 3과 4를 비교해서 왼쪽으로 가고 등등... BST검색 ..

트리는 확장성이 좋은 자료구조가 필요하다. 연결된 목록이 필요하지..(list) 트리의 각 노드는 하나의 연결 목록이 되고 목록의 각 노드는 트리의 다른 노드들을 가리키도록 하자. 트리를 탐색할때는 두종류의 반복자가 필요함. 1. 트리의 현재 노드 2. 현재 노드의 현재 자식노드 트리 반복자는 이전에 나왔던 연결 목록 반복자와는 다르다 연결 목록 반복자는 연결 목록에서 뽑아내는 식으로 생성 트리 반복자의 경우 가리키고자 하는 트리 노드를 생성자에 전달 이진트리 일반적 트리에는 없는 몇가지 특성 1. 포화성(새로운 수준을 하나 더 추가하지 않는 한 더 이상 노드들을 추가할 수 없음) 2. 조밀성(최하위 수준바로 전까지는 꽉 차 있으며 최하위 수준의 모든 말단 노드들이 왼쪽부터 채워져 있는 것) * AVL ..

1. 포인터 선언을 읽는 방법 포인터 선언을 뒤에서부터 읽음으로써 선언을 점차적으로 이해할 수 있음. const int *pci 이것은?? (뭐 지금까지 공부한 내용으로는 const *왼쪽에 있으니 int* 값이 상수다..이미 결론이 나오지만..) (*pci=값 수정 안됨) const int *pci; // 변수 pci const int *pci // 포인터 변수 pci const int *pci //정수를 가리키는 포인터 변수 pci const int *pci //상수 정수를 가리키는 포인터 변수 pci 2. 정수와 포인터를 저장하는데 같은 크기의 바이트를 사용하지만..이 둘은 같은 데이터 타입이 아니다. 그러나 정수를 정수 포인터로 캐스팅하는 것은 가능하다.. int *pt; int num=1; pt..

//IDIM * JDIM 배열 8*6 배열 const int IDIM = 8; const int JDIM = 6; const int NDIR = 4; const int iDir[NDIR] = { 1, 0, -1, 0 }; const int jDir[NDIR] = { 0, 1, 0, -1 }; int squares[IDIM][JDIM]; //닫힌목록 int clostNodes[IDIM][JDIM]; //열린목록 int openNodes[IDIM][JDIM]; //방향표시 맵..동쪽 0, 북쪽 1, 서쪽 2, 남쪽 3 int dirMap[IDIM][JDIM]; //x,y좌표를 대신하는것...row열과 col행으로.. struct Location { int row, col; Location() { row = ..