Algorithm(2) - Data Structure

 on

read

“어떻게 소프트웨어 시스템의 복잡성을 관리할 것인가?”

알고리즘을 구현할 때 적절한 자료구조를 통하여 프로그램의 복잡성을 관리하는 경우가 대다수이다. 이를 위하여 각 자료구조가 가지는 특징과 구조를 아는 것은 좋은 알고리즘을 짜는데 도움이 된다.

정의

  • 추상 데이터 타입을 프로그래밍 언어로 구현한 것.

추상 데이터 타입

  • 사용자들은 추상 데이터 타입이 제공하는 연산만을 사용 가능.
  • 사용자들은 제공되는 추상데이터 타입이 어떻게 사용하는지를 알아야함.
  • 사용자들은 추상 데이터 타입의 내부 데이터에 접근할 수 없다.(캡슐화)
  • 사용자들은 내부의 데이터에 접근할 수 없지만, 추상 데이터 타입을 사용할 수 있음.
  • 만약 다른 사람이 추상 데이터 타입의 구현을 변경하더라도 인터페이스가 변경되지 않으면 사용자들은 추상 데이터 타입을 같은 방식으로 사용할 수 있다.

자료구조 표기법

  1. 상수 상수는 전체를 대문자로 표기
    #define MAX_EMENET 100
    #define MAX_STACK_SIZE 100
  2. 변수의 이름 소문자를 사용, 언더라인을 사용하여 단어 분리. 약어사용은 지양
int add(ListNode* node);         // 혼동이 없는 경우
int list_add(ListNode* node);    // 혼동이 생길 우려가 있는 경우
  1. typedef의 사용 사용자 정의 데이터 타입을 정의
typedef <타입의 정의><타입 이름>;

자료 구조 안의 노드의 구조 등에 대해서 이름을 부여할 때 사용.

typedef int element;
typedef struct ListNode{
element data;
struct ListNode* link;
} ListNode;

자료구조의 표기방법

  • 자료구조의 요소
    • 자료구조는 요c소들의 집합.
    • 요소들은 다양한 변수값으로 정의 가능.
  • 자료 구조에 관련된 데이터
    • C언어는 객체 지향이 아니라 하나의 클래스로 연산 불가
    • 구조체의 포인터를 전달받아 자료구조를 구현

순환(Recursion)

순환(Recursion)은 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법.

example

int factorial(int n)
{
	if n<1 return 1;
    else return(n * factorial(n-1));
}

순환 알고리즘의 구조

순환 알고리즘은 자기 자신을 순환적으로 호출하므로, 순환을 멈추는 부분, 순환을 호출하는 부분 이 존재한다.

꼬리순환(tail recursion)

순환 호출이 순환 함수의 맨 끝에서 이루어지는 형태의 순환.

머리 순환(head recursion)

순환 호출이 순환 함수의 맨 앞에서 이루어지는 형태의 순환.

피보나치 수열

int fib(int n){
	if(n==0) return 0;
    else if (n==1) return 1;
	else return (fib(n-1) + fib(n-2));
}

하노이의 탑

void hanoi_tower(int n, char from, char tmp, char to){
	if(n==1){
	printf("%c에서 %c로 옮긴다",from,to);
    }
    else{
        hanoi_tower(n-1,from,to, tmp);
        printf("원판 %d을 %%c에서 %c로 옮긴다.",n,from,to );
        hanoi_tower(n-1, tmp,from, to);
    }
}

용어 정리

정점(Vertex)
위치 개념
간선(Edge)
위치 간의 관계인 다리
오일러 경로(Eulerian tour)
모든 경로를 한번만 통과하여 처음 정점으로 되돌아오는 경로.
무방향 그래프(Undirected graph)
간선에 방향성이 없는 그래프.
방향 그래프(Directed graph)
간선에 방향성이 있는 그래프.
가중치 그래프(Weighted graph)
간선에 비용아니 가중치가 할당된 그래프.
차수(Degree)
무방향그래 하나의 정점에 인접한 정점의 수
진입 차수(In-degree)
밖에서 한 정점으로 들어오는 간선의 수
진출 차수(Out-degree)
한 정점에서 나가는 모든 간선의 수

리스트(List)

트리(Tree)

트리는 노드와 간선 을 이용하여 계층적으로 구성한 자료구조의 종류로, 나무를 거꾸로 뒤집은 형태와 비슷하여 트리라고 불린다.

특징

  • 계층적인 구조를 나타내기 위한 자료구조.
  • 조직 구조, 디렉토리 구조 등에 사용.

용어

노드(Node)
트리를 구성하고 있는 각각의 구성 요소.
루트 노드(Root Node)
트리의 최상단에 있는 노드.
서브트리(Sub Tree)
트리를 제외한 나머지 노드들.
간선(Edge)
노드 간의 연결선.
차수(Degree)
특정 노드가 가지고 있는 자식 노드의 개수.
레벨(Level)
각 층에 대한 번호.

노드간의 관계

부모 노드(Parent Node)
바로 아래 레벨에 간선으로 연결된 노드.
자식 노드(Children Node)
바로 위 레벨에 간선으로 연결된 노드.
형제 관계(Sibling)
같은 부모 노드를 가진 노드들간의 관계.
조상 노드(Ancestor Node)
루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들.
자손 노드(Descendent Node)
임의의 노듸 하위에 연결된 모든 노드들.
단말 노드(Terminal Node)
자식 노드가 없는 노드.
비단말 노드(Nonterminal Node)
자식 노드가 있는 노드.

이진 트리

공집합 이거나 루트의 왼쪽 서브 트리, 오른쪽 서브 트리 로 구성된 노드들의 유한 집합 으로 정의되며, 이진 트리의 서브 트리들은 모두 이진 트리이다.

특징

  • 트리 중 가장 많이 쓰이는 트리.

  • 모든 트리의 차수는 2이하.

  • 왼쪽 서브트리와 오른쪽 서브트리로 구별.

    ​

성질

  1. 루트를 제외한 나머지 노드들은 하나의 부모 노드를 가짐.
  2. 부모와 자식 간에는 하나의 간선만이 존재.
  3. n개의 노드를 가진 이진트리는 n-1개의 간선을 가짐.
  4. 높이가 h인 이진 트리의 경우, 최대 \(2^h-1\)개의 노드를 가질 수 있다.

이진 트리의 분류

  1. 포화 이진 트리(Full binary tree)
    • 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리.
  2. 완전 이진 트리(Complete binary tree)
    • 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 모두 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진 트리.
    • 포화 이진 트리는 항상 완전 이진트리(역은 성립하지 않음.)
  3. 기타 이진 트리(ETC binary tree)
    • 경사 이진 트리

이진트리의 구현

  1. 배열 표현법
    • 포화 이진 트리나 완전 이진 트리의 경우 자주 쓰임.
    • 일반적인 이진 트리의 경우에는 메모리 공간 낭비가 심함.
  2. 링크 리스트 표현법
    • 노드가 구조체로 구현되고, 각 노드가 포인터를 이용하여 노드와 노드를 연결.
    • 하나의 노드가 데이터를 저장하는 필드와 왼쪽, 오른쪽 자식노드를 가르키는 2개의 포인터 필드를 가짐.

노드 i의 부모 노드 인덱스 = i/2 노드 i의 왼쪽 자식 노드 인덱스 = 2i 노드 i의 오른쪽 자식노드 인덱스 = 2i+1

이진 트리의 순회

이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미.

  • 전위 순회(preorder travelsal) : VLR

    루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문.

  • 중위 순회(inorder traversal) : LVR

    왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문.

  • 후위 순회(postorder traversal) : LRV

    왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문.

  • 트리 레벨 순회

    각 노드를 레벨순으로 검사.

이진 트리의 연산

  • 노드의 개수

    순회를 통하여 전체 각 노드의 수를 합함.

  • 높이 구하기

    서브 트리의 값을 비교하여 가장 큰 값을 높이로 선택.

이진 탐색 트리

이진 트리 기반의 탐색을 위한 자료구조

이진 탐색 트리의 정의

  • 모든 노드의 키는 유일.
  • 왼쪽 서브 트리의 키들은 루트의 키보다 작음.
  • 오른쪽 서브 트리의 키들은 루트의 키보다 큼.
  • 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리로 구성.

이진 탐색 트리의 탐색 알고리즘

  1. 이진 탐색 트리가 공백상태이면 복귀.
  2. 키값과 현재 트리의 값이 같으면 루트를 반환.

이진 탐색 트리의 삽입 연산

  • 트리 T에 값에 대한 탐색을 먼저 수행.
  • 탐색이 실패하면 끝난 지점에 값을 삽입.

이진 탐색 트리의 삭제 연산

  1. 값을 탐색

  2. 삭제하려는 노드에 대한 검사

    삭제하려는 노드가 단말노드일 경우

    값을 바로 삭제

    • 삭제하려는 노드가 하나의 서브 트리만 갖는 경우: 값을 삭제 후, 하위 노드의 값을 위로 올림.
    • 삭제하려는 노드가 두 개의 서브 트리를 갖는 경우: 값을 삭제 후, 왼쪽 서브 트리에서 제일 큰 값 혹은 오른쪽 서브트리에서 제일 작은 값과 교환.

이진 탐색 트리의 분석

  1. 이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이와 같다. $O(h)$
  2. 높이=$log_2n$=$log_2 15$=$4$

우선순위 큐

데이터에 우선순위를 부여하여, 우선순위에 따라 값을 보냄.

자료 구조 삭제되는 요소
스택 가장 최근에 들어온 데이터
큐 가장 먼저 들어온 데이터
우선순위 큐 가장 우선순위가 높은 데이터

우선 순위 큐의 구현

연결 리스트를 사용

  • 삽입의 시간 복잡도 $O(1)$
  • 삭제의 시간 복잡도 $O(n)$

히프를 사용

히프(Heap)는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조.
여러 개의 값들 중에서 가장 큰값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조.
부모 노드의 키값이 자식 노드의 키값보다 항상 큰(작은) 이진트리를 의미.
Key(A)>=key(B)
값의 중복을 허용함.

최대 히프(Max Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리. key(부모 노드) >= key(자식 노드)
  • 루트 노드의 값이 최댓값

최소 히프(Min Heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리. key(부모 노드) <= key(자식 노드)
  • 루트 노드의 값이 최솟값

히프의 삽입 연산

  • 번호 순으로 가장 마지막 위치에 새로운 값 삽입.
  • 부모노드의 값과 비교해가며, 교환을 반복 수행.

히프의 삭제 연산

  • 루트 노드의 값을 삭제
  • 가장 밑단의 값을 루트 노드로 변경.
  • 새로운 루트 노드값에 대하여 교환을 반복 수행.

시간 복잡도는 $log_2 n$

허프만 코드

각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용

그래프(Graph)

연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조

Written by
Blog Logo

Taekyung Han

Published

Supported by
Image

SHEPHEXD

CAN MACHINES THINK LIKE HUMANS?

Back to Overview