Develop Develop

선택 정렬은 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식이다.80, 50, 70, 10, 60, 20, 40, 30위의 데이터 그룹이 있을때 그리고 오름차순 정렬이라면, 첫 번째 위치는 키 값이 가장 작은 자료의 위치이다.이렇게 작동한다. 처음 인덱스에서 출발을 해서 자료의 전체 크기를 돌면서 가장 작은 자료를 찾아 첫번째 인덱스와 교환을 하고다시 두번째인덱스부터 출발해서 가장 작은 값을 찾으면 두번째 인덱스와 교환해서 넣고..반복하다가 위에 데이터 그룹을 기준으로 마지막 8번째라면 그건 그냥 가장 큰값이 될테니 추가적인 위치교환없이 정렬이 마무리 된다. C#using System;using System.Collections.Generic;using Sys..

자료를 정렬하는데 사용하는 자료의 값을 키라고 한다. Key파일크기에 따라 정렬이 되면 파일크기가 키다.정렬의 효율성은 정렬 대상이 되는 자료가 비교연산과 자료 이동연산의 횟수에 의해 결정된다.(퀵 정렬은 O(nlogn)이다 ) 아래는 시간복잡도에 따른 성능 우선순위다. 알고리즘에 따라 비교 연산이 많이 수행되는 경우와 자료 이동의 연산이 많이 수행되는 경우로 나눌 수 있다. 정렬을 수행해야 하는 자료의 크기가 크다면 같은 횟수의 연산이라 하더라도 비교연산이 많은 알고리즘이 이동 연산이 많은 알고리즘보다 성능이 우수(자료크기가 큼, 비교연산 > 이동연산 이렇게 되는 알고리즘이 더 낫다, 왜냐면 자료의 크기가 클 경우 이동해야하는 데이터의 크기가 증가하기 때문)그리고 저장된 자료의 상태에 따라 평균 효율성..

2-3-4 트리기본적인 구조 : 자식을 2 ~ 4개까지 가질 수 있다.각 정점의 데이터의 갯수는 1 ~ 3개까지 가질 수 있다.각각의 잎의 깊이는 모두 같다3종류의 정점이 존재한다. 2노드 : 한개의 데이터와 2개의 자식노드3노드 두개의 데이터와 3개의 자식노드4노드 세개의 키와 4개의 자식노드(부모와

z균형 이진 탐색트리VL트리는 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. AVL 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. 따라서 AVL트리는 균형 트리가 항상 보장되기 때문에 탐색시간이 O(log₂n)시간안에 끝나게 된다. 또한 삽입과 삭제 연산도 O(log₂n)시간안에 할 수 있다. AVL트리에서 균형인수는 매우 중요하다. 균형인수란 왼쪽서브트리의 높이 - 오른쪽 서브트리의 높이로 정의된다. 모든 노드의 균형인수가 ±1 이하이면 AVL 트리이다. (그림 출처 : SafariBooks ) * 균형 인수여기서 노드 아래의 숫자..

배열은 고정된 크기의 연속된 배열요소들의 집합이므로 배열을 초기화 할 때 총 배열 요소의 수를 미리 지정해야 한다. 하지만 경우에 따라 배열요소가 몇 개나 필요한 지 미리 알 수 없는 경우가 있으며, 중간에 필요에 따라 배열을 확장해야 하는 경우도 있다. .NET에는 이러한 동적 배열을 지원하는 클래스로 ArrayList와 List이 있다. 이들 동적 배열 클래스들은 배열 확장이 필요한 경우, 내부적으로 배열 크기가 2배인 새로운 배열을 생성하고 모든 기존 배열 요소들을 새로운 배열에 복사한 후 기존 배열을 해제한다. 동적 배열의 Time Complexity는 배열과 같이 인덱스를 통할 경우 O(1), 값으로 검색할 경우 O(n)을 갖는다. ArrayList 클래스 ArrayList는 모든 배열 요소가 ..

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)사용 그런데..느리다 이런 방법으로 우선순위 큐를 구현하는 경우는 거의없다 힙이라고하는 특별한 이진트리를 사용하면 좀 더 빠르고 효율적인 우선순위 대기열을 만들 수 있다. (그런데 이진트리를 또 연결된 목록으로 구현하면 ..