본문 바로가기
ALGORITHM/자료구조

자료구조 총정리

by sjs_2215 2019. 5. 12.

출처: 윤성우의 열혈 자료구조 Introduction to Data Structures Using C

자료구조는 근본적으로 무엇인가를 '표현'하는 도구. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

  • 순차 탐색 = 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘
  • 이진 탐색 = 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘

(이진 탐색 조건: 정렬되어 있어야 함)

  • 재귀 = 함수 내에서 자기 자신을 다시 호출하는 함수를 의미

(일련의 과정을 반복한다고? 재귀구나! 그렇다면 그 일련의 과정만 파악하면 되겠네)

시간 복잡도

최악의 경우를 시간 복잡도의 기준으로 삼는다. (평균적인 경우는 각 알고리즘마다 가정을 설정하기 어렵고 객관적인 판단이 어렵기 때문)

O(1) < O(logn) < o(n) < o(nlogn) < o(n2) < o(n3) < o(2의 n승)

  • 추상 자료형(Abstract Data Type. ADT) = 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것 (기능들의 연속)

'자료구조의 구현'과 '구현된 자료구조의 활용'은 완전히 구분되도록 ADT를 정의해야 함을 기억하자.

EX) 지갑

카드의 삽입, 카드의 추출, 동전의 삽입, 동전의 추출, 지폐의 삽입, 지폐의 추출 (O)

지갑을 열고 동전 주머니를 찾아서 동전 주머니의 지퍼를 내린다. 그리고 동전 주머니에 동전을 넣는다. 이어서 동전 주머니의 지퍼를 올린 다음 마지막으로 지갑을 닫는다 (X)

리스트 -> 대표적인 선형 자료구조

순차 리스트, 연결 리스트, 원형 리스트, 양방향 연결 리스트

리스트 ADT
void ListInt(List *plist);
void LInsert(List *plist, LData data);
int LFirst(List *plist, Ldata data);
int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);
LData LRemove(List *plist);
int LCount(List *plist);
  • 리스트 자료구조 = 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 마지 않는다.

데이터를 어떻게 나란히 저장할지 (x)

나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의 (o)

  • 배열 기반의 리스트 구현 = 데이터의 저장공간이 배열로 선언

장점: 데이터 참조가 쉽다. 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다

단점: 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

: 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.
  • 연결 기반의 리스트(연결 리스트) 구현 = 필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다.

정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 그래서 등장한 것이 '동적인 메모리의 구성'이다.

  • 단순 연결 리스트 = 연결의 형태가 한쪽 방향으로 전개되고 시작과 끝이 분명히 존재하는 단순 연결 리스트
  • 더미 노드 기반의 단순 연결 리스트 = 처음 추가되는 노드가 구조상 두 번째 노드가 되므로 노드의 추가, 삭제 및 조회의 과정을 일관된 형태로 구성할 수 있다.
  • 연결 리스트의 정렬 삽입의 구현도 가능 = SetSortRule 함수가 호출되면서 정렬의 기준이 리스트의 멤버 comp에 등록되면, SInsert 함수 내에서는 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다.
  • 원형 연결 리스트 = 앞서 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다.
  • 양방향 연결 리스트 = 노드가 양쪽 방향으로 연결된 구조의 리스트. 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

스택 -> 선형 자료구조의 일종

스택, 큐, 덱

스택 ADT
void StackIni(Stack *pstack);
int SIsEmpty(Stack *psatck);
void SPush(Stack *pstack, Data data);
Data SPop(Stack *pstack);
Data SPeek(Stack *pstack);
  • 스택 = 나중에 들어간 것이 먼저 나오는 구조이다 보니 last-in-first-out 구조의 자료구조
  • 배열 기반 스택
  • 연결 리스트 기반 스택 - 머리에 노드 추가하는 형태로 구현한 연결 리스트에 push 연산과 pop 연산이 포함된 ADT를 갖게 구현하면 됨
  • 스택을 이용한 계산기 프로그램 구현 - 후위 표기법 기억

후위 표기법 스택으로 구현하기.

피연산자는 그냥 옮긴다 -> 연산자는 쟁반(=스택)으로 옮긴다 -> 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법을 결정한다 -> 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다

(연산자 처리 부분)

우선순위가 높은 연산자는 우선순위가 낮은 연산자 위에 올라서서, 우선순위가 낮은 연산자가 먼저 자리를 잡지 못하게 한다. (사칙연산의 경우 연산자의 우선순위가 동일하면, 먼저 등장한 연산자를 먼저 진행한다. )

(괄호 연산자 처리 부분)

(연산자는 ) 연산자가 등장할 때까지 쟁반에 남아서 소괄호의 경계를 구분하는 도구로 사용되어야 한다. 따라서 ( 연산자의 우선수위는 그 어떤 사칙 연산자들보다 낮다고 간주한다.

후위 표기법으로 표현된 수식을 계산하는 프로그램 구현

피연산자는 무조건 스택으로 옮긴다 -> 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다 -> 계산 결과는 다시 스택에 넣는다

큐 ADT
void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);
void Enqueue(Queue *pq, Data data);
Data Dequeue(Queue *pq);
Data QPeek(Queue *pq);
  • 큐 = 먼저 들어간 데이터가 먼저 나오는 구조인 first in first out 구조의 자료구조
  • 배열 기반 큐 = 배열 기반의 큐라 하면 대부분의 경우 원형 큐를 의미한다고 봐도 무리가 아님
  • 원형 큐 = r과 f를 회전시켜서, 큐를 구성하는 배열을 효율적으로 사용하기 위해 탄생. f과 r이 배열의 끝에 도달했을 때 앞으로 이동시키는 것이 전부

꽉 찬 큐와 텅 빈 큐를 구분하기 위해 배열을 꽉 채우지 않는다. 배열의 길이가 n이라면 데이터가 n-1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다. (-> 꽉 찬 큐-r이 가리키는 위치의 앞을 f가 가리킨다, 텅 빈 큐-f와 r이 동일한 위치를 가리킨다)

  • 연결 리스트 기반 큐

    덱 ADT
    void DequeInit(Deaue *pdeq);
    int DQIsEmpty(Deque *pdeq);
    void DQAddFirst(Deque *pdeq, Data data);
    void DQAddLast(Deque *pdeq, Data data);
    Data DQRemoveFirst(Deque *pdeq);
    Data DQRemoveLast(Deque *pdeq);
    Data DQGetFirst(Deque *pdeq);
    Data DQGetLast(Deque *pdeq);

  • 덱 = 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조. double ended queue. 양방향으로 넣고 뺄 수 있다는 사실

덱의 구현에 가장 어울린다고 알려진 양방향 연결 리스트

트리 -> 비선형 자료구조

  • 트리 = 계층적 관계를 표현하는 자료구조. 가지를 늘려가며 뻗어나간다. (하늘로 뻗든 땅으로 뻗든 상관 없.) 의사 결정 트리도 트리 자료구조 유형 중 하나

트리를 공부할 때는,

데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나? (X)

트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나? (O)

이진 트리 ADT
BTreeNode *MakeBTreeNode(void);//생성
BTData GetData(BTreeNode * bt); //반환
void SetData(BTreeNode *bt, BTData data); //저장
BTreeNode *GetLeftSubTree(BTreeNode *bt); //주소 반환
BTreeNode *GetRightSubTree(BTreeNode *bt);
void MakeLeftSubTree(BTreeNode *main, BTreeNode *sub);//서브 트리 연결
void MakeRightSubTree(BTreeNode *main, BTreeNode *sub);
  • 이진트리 = 루트 노드를 중심으로 두 개의 서브 트리로 나뉜다 + 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.(재귀적인 특징이 있음을 알 수 있음) && 물론, 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.
  • 포화 이진 트리 = 노드를 더 추가하려면 레벨을 늘려야 하는. 모든 레벨이 꽉 찬 이진 트리
  • 완전 이진트리 = 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만 노드가 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 채워진 이진 트리

EX) 그냥 이진트리. a의 부모 노드 밑에 b노드 c노드가 있다. 다시 b부모 노드에는 공집합 노드 1개, d노드가 있다. c부모 노드에는 e와 f노드가 있는 경우.

  • 배열 기반 이진트리 - 트리가 완성된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다면 배열 기반 이진 트리 구현하는 게 훨씬 이득. -> 배열이 원체 연결 리스트에 비해 탐색이 매우 용이하고 또 빠르기 때문.
  • 연결 리스트 기반 이진 트리

서브 트리의 노드가 포화 상태라면 순회는 어떻게 할까?

순회의 종류(전위/중위/후위 순회)는 루트 노드를 기준으로 나눈다. 루트 노드를 언제 방문하느냐 이다.

레벨이 올라갈수록 순회를 어떻게 해야 하나 당황스러울 수 있지만, 레벨 1의 순회를 '재귀적'으로 한다고 생각하면 됨.

(중위 순회의 경우) 왼쪽 서브 트리의 순회 -> 루트 노드의 방문 -> 오른쪽 서브 트리의 순회

탈출조건까지 갖춘 트리 순회 재귀적 구조 코드(노드 방문=출력해보기) 참고
void 재귀순회(BTreeNode *bt) {
 if(bt == NULL)
 return;

 재귀순회(bt->left);
 printf("%d \n", bt->data);
 재귀순회(bt->right);
 //다른 순회 종류 구현하고 싶으면 위 3줄 순서만 바꾸면 됨
}

우선순위 큐와 힙

  • 우선순위 큐 = 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다
  • 배열 기반 우선순위 큐

단점 1: 데이터 삽입/삭제 시 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산 수반해야 함

단점 2: 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위의 비료를 진행해야 할 수도 있음

  • 연결 리스트 기반 우선순위 큐

단점 1: 삽입의 위치를 찾기 위해 첫 번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다

  • 힙(heap)을 이용한 우선순위 큐

위 두 개의 자료구조로 구현하면 위와 같은 단점이 발생하기에(데이터 수가 많으면 성능 저하 주원인이 됨) '힙'이라는 자료구조를 이용하는 것이 일반적

힙은 완전 이진트리이므로, 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가한다. 때문에 데이터의 수가 두 배 늘 때마다, 비교 연산의 횟수는 1회 증가한다.

-> 힙 기반 데이터 저장 시간 복잡도 o(log2n)

-> 힙 기반 데이터 삭제의 시간 복잡도 o(log2n)

연결 리스트, 배열은 저작/삭제 시간 복잡도 각각 o(n), o(1)

  • 힙 = 이진트리이되 완전 이진트리이다. && 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 저장된 값이 가장 커야 한다. (여기서 값은 우선순위라고 봐도 무방)
    = 우선순위 큐의 구현에 딱 어울리는, 완전 이진트리의 일종. (힙과 우선순위 큐를 동일하게 인식하는 것은 정확하지 않은 것)

힙을 구현할 때는, 새로운 노드를 추가한 이후에도 완전 이진트리를 유지해야 하는 경우에는 연결 리스트(새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문)가 아닌 배열을 기반으로 트리를 구현해야 함

버블/선택/삽입 정렬 -> 정렬 대상의 수가 적은 경우 효율적으로 사용할 수 있다.

  • 버블 정렬 = 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식

     

    #include <stdio.h>

void BubbleSort(int arr[], int n)
{
  int i, j;
  int temp;

  for(i=0; i<n-1; i++)
  {
      for(j=0; j<(n-i)-1; j++)
      {
          if(arr[j] > arr[j+1])
          {
              temp = arr[j];
              arr[j] = arr[j+1];
              arr[j+1] = temp;
          }
      }
  }
  }

int main(void)
{
  int arr[4] = {3, 2, 4, 1};
  int i;

  BubbleSort(arr, sizeof(arr)/sizeof(int));

  for(i=0; i<4; i++)
      printf("%d ", arr[i]);

  printf("\n");
  return 0;
  }

     

버블 정렬 성능평가(비교의 횟수, 이동의 횟수) pg.377

  • 선택 정렬 = 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘

  • 별도의 메모리 공간이 필요하지 않은 개선된 선택 정렬 = 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈자리에 가져다 놓는다.

    #include <stdio.h>

    void SelSort(int arr[], int n)
    {

      int i, j;
  int maxIdx;
  int temp;

  for(i=0; i<n-1; i++)
  {
      maxIdx = i;    // 정렬 순서상 가장 앞서는 데이터의 index

      for(j=i+1; j<n; j++)   // 최소값 탐색
      {
          if(arr[j] < arr[maxIdx])
              maxIdx = j;
      }

      /* 교환 */
      temp = arr[i];
      arr[i] = arr[maxIdx];
      arr[maxIdx] = temp;
  }

    }

    int main(void)
    {

      int arr[4] = {3, 4, 2, 1};
  int i;

  SelSort(arr, sizeof(arr)/sizeof(int));

  for(i=0; i<4; i++)
      printf("%d ", arr[i]);

  printf("\n");
  return 0;

    }

선택 정렬 성능평가(비교의 횟수, 이동의 횟수) pg. 380

  • 삽입 정렬 = 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬된 부분의 특정 위치에 '삽입'해 가면서 정렬을 진행하는 알고리즘

삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다 -> 삽입 위치를 찾는 과정과 삽입을 위한 공간 마련의 과정을 구분할 필요 x

#include <stdio.h>

void InserSort(int arr[], int n)
{
    int i, j;
    int insData;

    for(i=1; i<n; i++)
    {
        insData = arr[i];   // 정렬 대상을 insData에 저장

        for(j=i-1; j>=0 ; j--)
        {
            if(arr[j] > insData) 
                arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기
            else
                break;   // 삽입 위치 찾았으니 탈출!
        }

        arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입!
    }
}

int main(void)
{
    int arr[5] = {5, 3, 2, 4, 1};
    int i;

    InserSort(arr, sizeof(arr)/sizeof(int));

    for(i=0; i<5; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

삽입 정렬 성능 평가(비교의 횟수, 이동의 횟수) pg.384

힙/병합/퀵/기수 정렬 -> 정렬 대상의 수가 적지 않은 경우에는 보다 만족스러운 결과를 보장하는 알고리즘 필요. 이것들이 그러한 알고리즘

  • 힙 정렬 = 힙의 특성 '힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다'을 활용하여 정렬하는 알고리즘

정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부. 그럼에도 정렬이 완료되는 이유는, 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문

정렬 부분 코드
#include <stdio.h>
#include "UsefulHeap.h"

int PriComp(int n1, int n2)
{
    return n2-n1; //오름차순
//    return n1-n2; //내림차순
}

void HeapSort(int arr[], int n, PriorityComp pc)
{
    Heap heap;
    int i;

    HeapInit(&heap, pc);

    // 정렬 대상을 가지고 힙을 구성한다.
    for(i=0; i<n; i++)
        HInsert(&heap, arr[i]);

    // 순서대로 하나씩 꺼내서 정렬을 완성한다.
    for(i=0; i<n; i++)
        arr[i] = HDelete(&heap);
}

int main(void)
{
    int arr[4] = {3, 4, 2, 1};
    int i;

    HeapSort(arr, sizeof(arr)/sizeof(int), PriComp);

    for(i=0; i<4; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

힙 정렬 성능 평가(데이터 저장, 데이터 삭제) pg.388

  • 병합 정렬 (merge sort) = divide and conquer 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법. 분할 -> 정복 -> 결합의 원리를 가짐.

*divide and conquer = 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법.

병합 정렬은 데이터가 1개만 남을 때까지 분할. 데이터가 2개만 남아도 정렬을 할 필요가 있지만, 데이터가 1개만 남으면 그 조차 불필요.

+실제 정렬은 나는 것을 병합하는 과정(이 과정 그림 설명 pg.396)에서 이루어짐(그냥 묶는 게 아닌, 정렬순서를 고려해서 묶음). 그래서 이름이 병합 정렬~

1개만 남을 때까지 분할하는 과정은 재귀적으로 구현하면 됨. 그렇기에 함수 원형 선언 형태가 남들과 좀 다름. (정렬의 범위를 지정해 줌)

#include <stdio.h>
#include <stdlib.h>

void MergeTwoArea(int arr[], int left, int mid, int right)
{
//fIdx, rIdx는 각각 분할할 영역의 첫 번째 위치 정보
    int fIdx = left;
    int rIdx = mid+1;
    int i;

    int * sortArr = (int*)malloc(sizeof(int)*(right+1));
    int sIdx = left;

    while(fIdx<=mid && rIdx<=right) //fIdx, rIdx가 각각++ 해주는 한도를 정해주는 조건 + 탈출 조건
    {
        if(arr[fIdx] <= arr[rIdx])
            sortArr[sIdx] = arr[fIdx++];
        else
            sortArr[sIdx] = arr[rIdx++];

        sIdx++;
    }

//아래 if-else문 -> 미쳐 처리 안된 것들은 그대로 sortArr에 집어넣기(이미 정렬되어 있으므로 sort 안해도 됨)
    if(fIdx > mid)
    {
        for(i=rIdx; i<=right; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }
    else
    {
        for(i=fIdx; i<=mid; i++, sIdx++)
            sortArr[sIdx] = arr[i];
    }

    for(i=left; i<=right; i++)
        arr[i] = sortArr[i];

    free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
    int mid;

    if(left < right)
    {
        // 중간 지점을 계산한다.
        mid = (left+right) / 2;

        // 둘로 나눠서 각각을 정렬한다.
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);

        // 정렬된 두 배열을 병합한다.
        MergeTwoArea(arr, left, mid, right);
    }
}

int main(void)
{
    int arr[7] = {3, 2, 4, 1, 7, 6, 5};
    int i;

    // 배열 arr의 전체 영역 정렬 
    MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1);

    for(i=0; i<7; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

병합 정렬 성능 평가(데이터 저장, 데이터 삭제) pg.398 -> 어려워. 뭔 소린지 몰겠음

  • 퀵 정렬 = divide and conquer 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법.

pivot을 정한다. low를 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 오른쪽 방향으로 이동. high를 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지 왼쪽 방향으로 이동. 교환이 완료되면, pivot과 high 데이터를 swap. -> 그러면 pivot은 홀로 정렬이 완성되었다. 이제는 pivot을 중심으로 두 파트로 나뉘어서 앞서 한 것을 각 두 부분에서 반복하면 됨.

#include <stdio.h>

void Swap(int arr[], int idx1, int idx2)
{
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;
}    

int Partition(int arr[], int left, int right)
{
    int pivot = arr[left];    // 피벗의 위치는 가장 왼쪽! 
    int low = left+1; //피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름
    int high = right; //피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

    while(low <= high)    // 교차되지 않을 때까지 반복
    {    
        while(pivot > arr[low]) // low를 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 오른쪽 방향으로 이동
            low++;

        while(pivot < arr[high]) //high를 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지 왼쪽 방향으로 이동
            high--;

        if(low <= high)    // 교차되지 않은 상태라면 Swap 실행
            Swap(arr, low, high);    // low와 high가 가리키는 대상 교환
    }

    Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
    return high;    // 옮겨진 피벗의 위치 정보 반환
}

void QuickSort(int arr[], int left, int right)
{
    if(left <= right)
    {
        int pivot = Partition(arr, left, right);    // 둘로 나눠서 
        QuickSort(arr, left, pivot-1);    // 왼쪽 영역을 정렬
        QuickSort(arr, pivot+1, right);    // 오른쪽 영역을 정렬
    }
}

int main(void)
{
//    int arr[7] = {3, 2, 4, 1, 7, 6, 5};
    int arr[3] = {3, 3, 3};

    int len = sizeof(arr) / sizeof(int);
    int i;

    QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);

    for(i=0; i<len; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

퀵 정렬 성능 평가(비교 연산) pg.409

테이블, 해쉬

  • 테이블 = 원하는 바를 '단번에' 찾아내는 방식. 키와 값이 하나의 쌍을 이루어 저장되는 데이터의 유형. '사전 구조', '맵'이라고도 불린다.

저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다. 키가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다.

  • 배열을 기반으로 하는 테이블

문제점: 키의 범위가 배열의 인덱스 값으로 사용하기 적당하지 않다 + 키의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

-> 해결책: 해쉬 함수

  • 해쉬 함수 = 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다. 키의 특성과 저장공간의 크기를 고려하는 것이 우선

     

    int GetHashValue(int impNum)
{ 
 	return empNum %100;
   }


    //empNum이 입사 연도 네 자리와 입사 순서 네 자리로 구성되고, 해쉬 함수를 거친다면 20120003은 03이라는 키로 변경됨.

좋은 해쉬 함수: 적은 수의 데이터를 조합하여 (키의 일부분을 조합하여) 해쉬 값을 생성하는 것보다 많은 수의 데이터를 조합하여 (키 전부를 조합하여) 해쉬 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있을 것.

  • 충돌 해결 방법 (해결 순: 선형 조사법 -> 이차 조사법-> 이중 해쉬)

서로 다른 두 개의 키가 해쉬 함수를 통과하였는데, 그 결과가 모두 동일한 경우를 충돌(collision)이라고 한다.

저작자표시 비영리 변경금지

Comments

티스토리툴바