Data Structure 썸네일형 리스트형 퀵 정렬(Quick sort) 이번에는 정렬 방법의 마지막 포스팅이자평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법 인 퀵 정렬(Quick sort)에 대해 알아 보겠습니다. 퀵 정렬(Quick sort)은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고,각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다.그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다.먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다.여기서 피벗을 선택하는 방법은 여러가지가 있는데1. 리스트의 가장 왼쪽(처음)2. 리스트의 가장 오른쪽(마지막)3. 리스트의 가운데4. 가장 왼쪽, 가장 오른쪽, 가운데 값 중 중간 값등 여러가지의 방법으로 피벗을 결정한다.이렇게 피.. 더보기 합병 정렬(Merge sort) 이번 포스팅에서는 합병 정렬(Merge sort)에 대해 알아 보겠습니다. 합병 정렬(Merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고,분할 된 두 부분 리스트를 정렬한 다음, 두 개의 정렬 된 부분 리스트를 합하여전체가 정렬 된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 정복(Divide and Conquer)방법에 바탕을 두고 있다.분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서원래의 문제를 해결하는 전략이다. 분리 된 문제가 아직도 해결하기 힘들다면,즉 충분히 작아지지 않았다면 분할 정복 방법을 연속하여 다시 적용한다.분할 정복 방법은 대개 순환 호출을 이용하여 구현 된다.간단히 설명하자면 아래와 같은 단계로 이루어 진다.1. 분할.. 더보기 셸 정렬(Shell sort) 이번 포스팅은 삽입 정렬(Insertion sort)의 단점을 보완 하기 위해 고안 된 정렬 방법 인 셸 정렬(Shell sort)에 대해 알아 보겠습니다. 셸 정렬(Shell sort)은 삽입 정렬(Insertion sort)의 단점인 레코드를 적합한 위치에 삽입하는 과정에서레코드들을 뒤로 옮기는 연산은 줄이기 위해, 특정한 거리씩 떨어진 레코드들끼리 삽입 정렬을 하고,그 거기를 차츰 줄여나가면서 최종적으로는 전체 레코들에 대해 삽입 정렬을 하는 정렬 방법이다. 위 그림을 보면 어느 정도 이해가 될 것이다.과정을 간단하게 설명하자면1. 레코드를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.2. 레코드를 다시 잘게 나누어서 삽입 정렿나다.3. 이러한 방법을 반복하여 모든 레코드들이 정렬 될 때까지 반복.. 더보기 버블 정렬(Bubble sort) 이번 포스팅은 버블 정렬(bubble sort)에 대해 알아보겠습니다. 버블 정렬(bubble sort)은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하는 정렬이다.이러한 비교-교환 과정을 스캔이라 하며 스캔이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다.이러한 레코드의 이동 과정이 마치 물속에서 거품(bubble)이 보글보글 떠오르는 것과 유사하여 버블 정렬이라 부른다.이러한 비교-교환 과정은 전체 레코드가 정렬 될 때까지 계속된다. 버블 정렬의 가장 기본적인 원리는 두 레코드를 비교하여 큰 레코드를 리스트의 우측으로 밀어내는 것이다.위 그림은 두 레코드를 비교하여 만약 앞의 레코.. 더보기 삽입 정렬(Insertion sort) 이번 포스팅은 선택 정렬에 이어 삽입 정렬에 대해 알아보겠습니다. 삽입 정렬(insertion sort)란 아직 정렬 되지 않은 임의의 데이터를 이미 정렬 된 부분의 적절한 위치에 삽입해가며 정렬하는 방식이다.예를 들면 카드 게임을 할 때 이미 내 손에는 정렬 된 카드가 있다고 할 때새로운 카드를 받아 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지 되게 하는 것이다. 1회전의 경우 첫번째 데이터는 정렬이 된 리스트라고 가정을 하고, 두번째 데이터를 기준으로 하여앞에있는 데이터와 비교를 하여 값을 swap한다.2회전의 경우 세번째 데이터는 앞에 있는 두번째 데이터와 비교후 자신의 데이터가 더 작으므로그 앞의 첫번째 데이터와 한번 더 비교를 하게 된다.첫번째 데이터와 비교후 자신의 데이터가 더 크.. 더보기 선택 정렬(Selection sort) 지난 포스팅에서 정렬에 대해 알아보았습니다. 이번 포스팅부터 각 정렬의 정의와 원리, 그리고 성능 분석을 하여 시간복잡도를 빅오 표기법으로 표현해보겠습니다. 선택 정렬(selection sort)은 정렬 되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 위 그림은 위키백과에 있는 선택 정렬 애니메이션 모습이다. 선택 정렬의 순서를 설명하자면1. 주어진 리스트 중 최소 값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 교체한다.3. 가장 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다.이러한 과정을 반복하여 수행하게 된다. 위 그림을 보면 더 이해하기 쉬울 것이다.좌측에 노란 리스트는 이미 정렬이 완료 된 리스트이고, 우측에 파란 리스트는 정렬이 되지 .. 더보기 정렬(Sorting) 지금까지 형태에 따른 자료구조의 종류와 정의에 대해 알아보았습니다.이번 포스팅부터는 정렬에 대해 알아보겠습니다. 정렬(Sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다.예를 들어 책들은 제목 순, 저자 순, 발간 연도 순으로 정렬이 가능하다. 사람도 나이, 키, 이름 등을 이용하여 정렬할 수 있다.물건뿐만 아니라 어떤 형태의 것도 서로 비교만 가능하면 정렬할 수 있다.정렬은 컴퓨터 공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용된다. 또한 정렬은 자료 탐색에 있어서 필수적이다.예를 들면 영어 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 사전 안의 .. 더보기 트리(Tree) 지금까지 선형 자료구조에 대해 포스팅을 했었습니다. 만약 데이터가 선형 구조가 아닌 계층적인 구조(hierarchical structure)를 가지고 있다면 어떻게 해야 할까요?예를 들어 조상과 자손, 전체와 부분, 상사와 부하 직원, 컴퓨터의 디렉터리 구조 등의 계층적인 관계를 표현하고 싶은 경우에는 선형 구조는 적합하지 않습니다.트리(Tree)는 이러한 계층적인 자료를 표현하는 데 이용되는 자료구조 입니다. 컴퓨터 용어 사전에 기재 된 트리의 정의는나무가 하나의 뿌리(root)에서 줄기(trunk)가 나와 가지(branch)로 나누어지는 것처럼, 어떤 하나의 집합으로부터하위 레벨(lower level)로 가지가 나오는 집합 관계를 갖는 계층 구조를 말한다.부분적으로도 결코 루트를 형성하는 경우는 없다.. 더보기 큐(Queue) 이번 포스팅에서는 선형 구조의 또 다른 자료구조 인 큐(Queue)에 대해 알아 보겠습니다. 스택의 경우 나중에 들어 온 데이터가 먼저 나가는 구조인 데 반하여 큐(Queue)는 먼저 들어온 데이터가먼저 나가는 구조로, 이러한 특성을 선입 선출(FIFO : First-In First-Out)이라고 한다.큐의 예로는 매표소에서 표를 사기 위해 줄을 서는 것을 들 수 있다. 줄에 있는 사람들 중 가장 앞에 있는 사람이가장 먼저 표를 사게 될 것이다. 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다. 컴퓨터 용어 사전에 기재 된 큐는리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화 된 리스트.라고 정의 한.. 더보기 스택(stack) 앞서 형태에 따른 자료구조의 종류를 살펴 보았습니다.이번에는 선형구조의 가장 기본이 되는 스택에 대해 살펴보겠습니다. 스택(stack)은 영어 사전에서 찾아보면 '(건초, 밀집 따위를 쌓아 놓은) 더미, 낟가리'를 의미한다고 되어 있다.스택의 예를 들면 식당에 쌓여 있는 접시 더미, 책상에 쌓여 있는 책, 창고에 쌓여 있는 상자 등을 들 수 있다.스택을 창고에 쌓여 있는 상자를 이용하여 설명하자면,우리는 보통 창고에서 새로운 상자들을 쌓을 때는 상자 더미의 맨 윗부분에 놓는다.또 상자가 필요하면 상자 더미의 맨 위에 있는 상자를 꺼낸다. 만약 중간에서 상자를 꺼내면 전체 상자가 붕괴 될 것이다.따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다.이러한 입출력 형태를 후입 선출(.. 더보기 이전 1 2 다음
