Computer Science and Engineering/Data Structure

셸 정렬  어느 정도 정렬된 상태에서 삽입 정렬이 효율적인 것에 착안하여 만들어진 정렬 방법이다. 삽입 정렬은 요소들이 이웃한 위치와만 교환이 이뤄지기 때문에 특정 값이 멀리 이동하는 데에 많은 교환이 필요하다. 이때 요소를 멀리 떨어진 위치와 교환할 수 있다면 더 적은 교환으로 요소를 이동시킬 수 있을 것이다. 즉 삽입 정렬에서 한 칸이면 간격을 늘린다면 더 멀리 떨어진 요소를 효율적으로 옮길 수 있다는 것인데, 이런 방식의 정렬을 사용하는 것이 셸 정렬이다.먼저 정렬 대상 리스트를 일정 간격의 부분 리스트로 나누고 나뉜 각 부분 리스트를 삽입 정렬한다. 정렬이 끝난 후 다시 간격을 줄이고 정렬하고, 반복하여 간격이 1인, 즉 원래의 삽입 정렬과 똑같이 될 때까지 부분으로 나누고 정렬한다. 마지막 간격..

삽입 정렬  차례에 해당하는 수를 앞쪽 올바른 자리에 삽입하는 정렬 방식이다. 이미 정렬되어 있다면 정렬된 것을 확인하고 정렬이 종료된다는 장점이 있다.정렬은 두번째 자리의 값부터 확인한다. 두번째 자리의 값의 바로 앞 값이 자신보다 크다면 그 값을 교환한다. 그 후 세번째 자리의 값을 선택하여 자신의 앞의 값과 비교하고 자신보다 크다면 교환한다. 만약 교환되었다면 다시 자신의 앞의 값과 비교하고, 크다면 교환한다. 이를 끝까지 반복하면 정렬이 완료된다.따라서 만약 자신의 앞의 값이 자신보다 작다는 것이 확인된다면 정렬되어 있다는 뜻이기 때문에 따로 교환이 일어나지 않고 넘어간다. 즉 이미 정렬되어 있다면 모든 값이 정렬되어 있다는 것을 확인하고 정렬 알고리즘이 종료되기 때문에 버블 정렬, 선택 정렬이 ..

선택 정렬  작은 수를 선택해서 앞쪽에 배치하는 정렬 방식이라 선택 정렬이다. 효율적이지는 않지만, 버블 정렬과 함께 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 가장 앞 수를 선택한 후 자신보다 작은 수가 나오면 교환하는 방식으로 진행된다. 끝의 수까지 비교하고, 작을 때 교환했다면 가장 앞에는 리스트에서 가장 작은 수가 올 것이다. 이제 두번째 수를 선택하고 다시 비교, 교환하고, 그 후에는 세번째 수를 선택하고, ... 반복하여 마지막 수 직전에 도달하면 모든 수가 정렬된다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자.먼저 위와 같이 가장 앞을 선택하고 그 다음 수와 비교한다. 선택된 수인 9가 비교 대상인 2보다 크다.그러므로 두 수를 바꿔준다. 그 후 아래와 같이 다..

버블 정렬  정렬할 때 큰 수를 뒤로 미루는 것 때문에 거품이 올라오는 것 같아 이름 붙여진 정렬 방식이다. 효율적이지는 않지만, 구현이 쉽고, 가장 쉽게 생각할 수 있는 정렬 방식이다.정렬은 인접한 두 수를 선택한 후 비교하고, 큰 수가 앞에 있다면 두 수를 교환하는 방식이 반복되며 일어난다. 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, ... 반복하여 마지막 수에 도달한다면 가장 큰 수가 가장 마지막 자리에 도달하게 된다.이제 다시 첫번째 수와 두번째 수를 선택한 후 비교, 교환하고, 두번째 수와 세번째 수를 선택한 후 비교, 교환하고, .. 반복하여 마지막 수 앞 칸에 도달하면 뒤 두 수가 정렬된다. 앞선 정렬을 통해 마지막 수가 정렬되..

정렬  여러가지 값들이 규칙없이 모여있을 때 이를 규칙에 맞게 정렬해야 한다면 여러가지 정렬 알고리즘을 사용할 수 있다. 위 영상은 여러가지 정렬 알고리즘을 시각화한 것이다.정렬은 효율적인 탐색에도 필수적인데, 예를 들어 사전에서 단어들이 알파벳 순서가 아니라 랜덤으로 섞여 있다고 가정해보자. 알파벳 순으로 정렬되어 있을 때는 우리는 알파벳이 어디 있는지 알 수 있지만, 랜덤으로 섞여 있다면 사전의 모든 페이지를 확인해야 할 것이다.일반적으로 정렬 대상을 레코드(record)라 하고, 레코드는 필드(field)라는 레코드보다 작은 단위로 구성된다. 이때 키필드(key field)를 기준으로 레코드를 구별하고 정렬한다.모든 경우에 최적인 정렬 알고리즘은 없다. 레코드 수, 레코드의 크기, 키의 특성, 가용..

탐색 그래프의 어떤 정점에서 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다. 효율적인 구간을 찾거나, 특정 정점에 도달 가능한지 알아볼 때 자주 사용된다.탐색은 대표적으로 깊이 우선 탐색과 너비 우선 탐색이 존재한다. 말 그대로 깊이를 먼저 탐색하면 깊이 우선 탐색이고, 너비를 우선 탐색하면 너비 우선 탐색이다. 트리에서 전위, 중위, 후위 순환이 깊이 우선 탐색의 일종이고, 레벨 순회가 너비 우선 탐색의 일종이다. DFS 한 방향으로 탐색 가능한 곳까지 가다가 더 이상 갈 수 있는 정점이 없다면 다시 가장 가까운 갈림길로 돌아와 그 갈림길부터 다시 안 간 방향으로 탐색을 진행하는 것을 말한다. 되돌아가기 위해 스택이 필요한데, 재귀를 이용하여 묵시적 스택 이용이 가능하다.위 그래프에서 빨..

그래프  연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 트리 역시 그래프의 특수한 형태이다.다음은 그래프의 기본적인 용어이다.정점(vertex) 혹은 노드(node): 각 객체간선(edge) 혹은 링크(link): 각 정점을 연결하는 선 혹은 관계부분 그래프(sub graph): 어떤 그래프의 정점과 간선의 부분집합으로 이루어진 그래프인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점차수(degree): 무방향 그래프에서 하나의 정점에 연결된 다른 정점의 수진입 차수(in-degree): 방향 그래프에서 하나의 정점으로 오는 간선의 수진출 차수(out-degree): 방향 그래프에서 하나의 정점에서 외부로 향하는 간선의 수경로(path): 한 정점에서 다른 ..

우선순위 큐 우선순위 큐는 일반적인 큐와 달리 우선순위가 높은 데이터가 먼저 나가는 큐이다. 따라서 일반적인 큐처럼 리스트로 구현하면 우선순위가 높은 데이터를 이동시킬 때, 즉 삽입, 삭제를 할 때 시간복잡도가 커지므로 트리를 이용한 힙으로 구현하는 것이 일반적이다. ADT 객체 (Object)0 개 이상의 우선순위를 가진 요소들의 모임연산 (Operation)create() ::= 우선순위 큐를 생성한다.init() ::= 우선순위 큐를 초기화한다.is_full() ::= 우선순위 큐가 가득 차 있다면 true 를, 아니라면 false 를 반환한다.is_empty() ::= 우선순위 큐가 비어있다면 true 를, 아니라면 false 를 반환한다.insert(item) ::= 우선순위 큐에 item을 추..

이진 탐색 트리 탐색작업을 효율적으로 하기 위해 정렬한 이진 트리이다.루트 노드의 값보다 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 있는 것이 특징이다. 이러한 특징 때문에 이진 탐색 트리를 최상위 노드부터 중위순회한다면 오름차순으로 정렬된 값을 얻을 수 있다. 탐색 탐색 연산은 이진 탐색 트리의 정렬을 이용한다. 최상위 노드의 값부터 비교를 시작하는데, 탐색하고자 하는 값과 같다면 탐색 종료, 탐색하고자 하는 값보다 크다면 그보다 더 작은 값을 찾아야 하기 때문에 외쪽 서브트리로 이동, 반대로 탐색하고자 하는 값보다 작다면 그보다 더 큰 값을 찾아야 하기 때문에 오른쪽 서브트리로 이동하여 탐색을 진행한다.예를 들어 트리에서 5를 탐색한다고 하면 아래와 같이 탐색한다. 탐색 값을 찾으면 해당..

스레드 이진 트리 이진 트리의 빈 포인터를 활용하여 트리 순회 속도를 향상시키기 위해 고안된 자료구조이다. 순회시 이진 트리에서 자식이 없는 노드를 만나면 일반적으로 부모노드로 돌아가지만, 스레드 이진 트리에서는 이 빈 포인터를 활용하여 그 다음 순회에 필요한 노드로 바로 찾아갈 수 있다.때문에 재귀 호출이나 스택 없이 순회가 가능하여 함수 호출에 필요한 시간을 효율적으로 절약할 수 있다.빈 포인터를 다음 순회 노드인 후속 노드(successor)를 가리키는 스레드로 활용하게 되면 해당 포인터가 더이상 빈 포인터가 아니기 때문에 일반적인 포인터인지 스레드인지가 구분 불가능해진다. 따라서 스레드 이진 트리의 노드는 해당 포인터가 스레드인지 아닌지를 나타내는 변수가 들어간다.이진 트리에서는 왼쪽과 오른쪽 자..