Data Structure

01) 자료구조와 알고리즘

-      자료구조의 개념

문제 해결을 위한 자료의 공간 및 시간적 의미의 효율적 사용(처리)를 위해 구조화한 것.

-      데이터 정보

선형구조(배열), 비선형구조(포인터)

-      정보처리

-      단위

Bit – Byte – Field – Record – File – DB

Bit란 정보표현의 최소단위 (on/off) Binary Digit(2진수)

Byte(= 4 Bit)  문자 표현의 최소단위, 절대 주소가 있음.

Field란 문자가 모인 의미있는 하나의 데이터 단위. (논리적 자료 단위)

Record란 연관된 필드들의 모임.

File이란 연관된 레코드들의 모임. 기억장소에 저장되어 연속적인 문자열들의 모임.

-      표현

수치데이터 : 정수와 실수, 2진법 8진법 16진법 10진법.

-      알고리즘의 정의

어떤 특정 문제를 해결하기 위한 절차와 방법을 명확하게 기술해 놓은 명령들의 집합.

-      알고리즘 5대 조건

입력, 출력, 명확성, 유한성, 실제성

0개 이상 입력데이터 필요, 하나 이상 결과 출력, 명령이 애매모호X 명확하게 존재, 유한 번 실행 후 반드시 종료되어야함, 실질적으로 실행 가능해야함.

-      알고리즘 분석 3개 방법

시간 복잡도(수행량) 으로 알고리즘을 분석함. (수행량을 차수(Degree)로 표현)

big-o 표현법 > 알고리즘 수행에 있어 연산 차수가 가장 높은 것을 알고리즘의 차수로 표현.

big-omega 표현법 > “” 차수가 가장 낮은 것을 알고리즘의 차수로 표현

big-theta 표현법 > 오와 오메가 표현법 교차되는 부분. 최적 알고리즘이라 표현.

 

-      다항시간, 지수시간, 의사코드

다항시간 = 어떠한 문제를 해결하는데 걸리는 시간 (big-O 표현법)

지수시간 = 시간복잡도

 

 

02) 추상 데이터 타입과 배열

-      데이터 추상화 3가지

1.     float f = 3.14; - 데이터 타입. 추상자료형 선언.

2.     #include <stdio.h>

3.     객체(Object) – 데이터 구조와 사용된되는 함수(메소드) 합친 것

캡슐화

-      배열의 정의

연속적인 기억장치에 1개의 블록으로 저장되는 것.

연속적으로 배치된 기억장소의 위치, 인덱스타 값을 mapping하여 사용.

-      배열에서의 원소 위치 (n차원 배열 C언어로 표현, index가 1인경우와 0인 경우 위치계산

<0번지 주소 알때는>

1차원 배열 : A[0]의 위치주소 + (I * 원소크기byte)

2차원 배열 : A(u1,u2)에서 (i1,i2)의 특정 위치는

                     location = i1 * u2 +i2

3차원 배열 : A(u1,u2,u3)에서 (i1,i2,i3)의 특정 위치는

                     location = i*u2*u3 + i2*u3 + i3

(문자형 = 1Byte, 정수형 = 2Byte, 실수형 = 3Byte)

 

<상대 특정위치알 때>

2차원 배열 : location(row) = u2*(i1-1)+i2

                     location(column) =

-      희소행렬의 특성

2차원 배열에서 0인 요소가 많은 배열. m*n의 행렬에서 0이 아닌 원소들로만 골라 행렬을 다시 구성하기에  데이터가 m*n개 보다 훨씬 적으므로 기억장소를 절약하고 빠른 탐색을 수행할 수 있다.

 

03) 리스트

-      선형리스트 정의

데이터가 기억장소에 연속적으로 저장되어, 순차적으로 처리됨으로 기억장소 활용도가 높으며, 자주 변경하지 않는 데이터의 저장에 유리하다.

데이터 추가시에 여분의 기억공간을 확보해야 하고, 데이터의 추가와 삭제시 많은 데이터의 이동이 필요하다.

순차리스트란 배열을 이용하여 선형리스트 구조로 표현한 것.

-      삽입과 삭제방법

n개의 데이터가 존재하는 선형리스트에서 k번째에 데이터 추가시 (n-k+1) 데이터 이동 발생.

n개의 데이터가 존재하는 선형리스트에서 k번째에 데이터 삭제시 (n-k) 데이터 이동 발생.

-      데이터 이동의 문제점

평균적으로 n/2 만큼 (절반) 이동함으로, 많은 시간 낭비.

다양한 크기의 원소를 리스트 표현을 위해 최대공간을 갖는 기억장소를 할당하면서 기억공간의 낭비.

만일 기억장소를 작게했다면, 리스트에서 삽입 연산이 발생하여 리스트의 크기를 초과하면 사용 가능한 영역을 초과한 것으로 오버플로우가 발생된다.

-      연결리스트의 개념

특정 데이터를 가진 노드가 다음의 데이터를 처리하기 위한 포인터(주소)를 가지고 처리하는 구조.

포인터는 다음 데이터의 주소를 가지며, 데이터와 주소를 하나의 노드에 표현함으로 구조체를 사용.

데이터의 추가와 삭제가 간단하며, 데이터 이동이 필요없다.

-      연결리스트 종류

단순 연결리스트

환형 연결리스트

이중 연결리스트

이중 환형 연결리스트

-      추가, 삭제 알고리즘 + 기억공간 할당해제

 

 

04) 스택과 큐

-      스택의 개념

데이터의 입출력이 한쪽방향에서만 수행되는 데이터 구조 (LIFO)

Top 포인터 사용하며, Push는 입력, Pop은 출력.

-      추가 삭제 알고리즘

<추가> if(TOP>=N) {printf(“Overflow”);

else{

                     s[top] = data;

                     top = top+1;

                     }

<삭제>

                     if(top==0) {printf(“Underflow”)}

                     else{

                     top=top-1;

                     s[top]=NULL;

-      스택의 이용분야

자동 변수의 사용. (c언어 변수의 사용범위 지정)

수식 연산에 이용. (연산자 스택과 피연산자 스택을 사용)

수식의 표현과 연산에 사용.

-      큐의 개념

데이터의 입출력이 선형리스트의 양쪽 끝에서 모두 수행이 되는 데이터 구조(FIFO)

입력시 tail 포인터 사용, 출력시 head 포인터 사용.

-      큐의 추가 삭제 알고리즘

<추가> if(tail>=n) printf(“Overflow”)

                     Q[tail]=data;

tail= tail+1

<삭제> if(head == 0 && tail ==0) {printf(“Underflow”)}

                     if(head < tail){

                                Q[head] = NULL;

                                head = head +1;

                                if (head == tail) { //언더플로우

                                           return

                                           }

                                }

 

circular queue

추가

                     tail=(tail+1)%n

if(head==tail){

                                if(Q[tail]==NULL){

                                           Q[tail] = data

                                           printf(“overflow”);

                                           return}

 

05) 트리

- 트리의 정의

링크드리스트 사용하여 정보의 각 항목들을 계층적으로 연관되도록 구조화 시키는 비선형 자료구조.

단하나의 루트노드가 존재, 루트노드에서 간선(edge)으로 다른 노드 연결.

-      트리의 종류

일반트리 : 3개 이상의 링크를 가진 트리

이진트리 : 트리의 차수가 2 이하인 트리.

           정이진트리(full binary) : 노드의 수가 2^k – 1 인 트리

           전이진트리(complete binary) : 노드의 수가 s^(k-1) < n < s^k -1 인 트리

           skwed tree : 한쪽방향으로 치우친 트리.

Threaded binary tree : 트리에서 사용되지 않는 NULL 포인터 값을 트리 운행에 사용.

                     정상연결이면 1, 아니면 0.  표보셈.

-      트리의 구현(표현)

배열을 이용하는 방법 :          

부모노드 접근 용이. 정이진 트리는 기억장소낭비 적음. 데이터 추가삭제시 데이터 이동 발생. 사향이진트리는 기억장소 낭비.

링크드리스트 이용하는 방법 :

노드에 포인터 값을 사용하며 트리를 구현하는 방법.

n개의 노드를 가진 k진 트리는 n*k개의 링크수를 가짐. n(k-1)+1 개의 널(NULL) 링크 수를 가짐.(Threaded binary tree 표)

-      트리의 운행(순회)

트리 내 특정 노드를 탐색하는 순서를 결정하며, 트리 내의 특정 노드는 1번만 참조.

Inorder :  Left, Root, Right  node 순으로 방문.

Preorder : Root, Left, Right  node 순으로 방문.

Postorder : Left, Right, Root  nood 순으로 방문.

 

 

06) 그래프

- 정의

각 단위 정보를 정점으로 표현. 각 정점을 간선으로 연결하여 구조화시킨 자료구조.

그래프 G는 정점(Vertex)과 간선(edge)로 구성됌. Cycle을 형성함.

           - 용어

Adjacency(인접), Path(경로), length(간선의 수), loop(경로길이=1, 자기자신), cycle(시작점에서 돌아오는 경우), distancy(최단경로길이), degree(차수. 한 정점이 가지는 간선의 수)

-      그래프의 표현

인접행렬 : 그래프를 2차원 배열로 표현. 인접행렬이 A라 할 때 A(i,j) 가 1이면 i와 j 정점 연결, 그렇지 않으면 0으로 표현

-      그래프의 운행(구현)

DFS(Depth First Search) 깊이우선탐색

1.     시작정점 v를 결정하고 방문

2.     V에 인접한 정점 가운데 방문되지 않은 정점 방문.

3.     모든 정점 방문하면, 방문되지 않은 인접한 마지막 정점 방문.

4.     모든 정점 방문하면 종료

BFS(Breadth First Search) 너비우선탐색

1.     시작정점 v를 결정하고 방문

2.     V를 큐에 저장하고 내용 출력

3.     큐에 인접한 정점을 가지고 (2)수행

4.     큐가 Underflow 되면 종료.

-      그 외

신장트리(Spanning Tree) : 그래프 G의 모든 정점을 포함한 트리

최단경로(Shortest Path) : 한 정점에서 임의의 정점 최단 경로의 값.

                                           A^k[i][j]  > k보다 큰 정점 지나지 않고 i에서 j로 가는 경로.

07) 탐색

           - 탐색종류

순차탐색(Sequential Search) : 인덱스 증가or감소 시켜 차례대로 비교탐색

Binary 탐색  : 정렬된 상태에서 1/2씩 범위 줄이면서 탐색

Fibonacci 탐색 : 피보나치 수열 값 인덱스로 사용해 탐색

Interpolation 탐색 : 정렬된 데이터의 편차범위가 일정할 때 효율적

Block 탐색 : 정렬된 데이터를 블록단위로 구분. 블록내 가장 큰값을 저장하여 이 값과 찾고자하는 값이 어느 블록에 포함되어 있는지 판단후 순차탐색한다.

 

08) 이진탐색 트리  - 개념만 알기

좌측은 루트보다 작은값, 우측은 루트보다 큰값.

09) 해싱

-      해싱의 개념

해시함수에 의하여 계산된 키 값의 주소로 직접 접근.

“key-to-address transformation”

 특정 규칙에 따라 주어진 키 값을 주소로 변환하여 해시 테이블이라는 기억공간에 키의 레코드를 저장.

해시함수를 이용하여 필요한 레코드의 주소를 산출함으로서 검색작업 수행.

-      해시 함수 설명

입력된 키 값을 해시 테이블의 주소로 변환시키는 함수.

중간제곱함수, 나누기함수, Folding함수, 기수변환법, 숫자분석법

-      충돌시 오버플로 해결 방법

버킷이 여러 슬롯으로 구성되어 있으면 다른 슬롯에 저장.

그러나 모든 슬롯이 채워졌다면 다른 기억장소를 찾아 키 값을 저장함.

개방주소법 : 한 레코드(Data)의 키로부터 관련된 일련의 버킷 주소 생성.

                     충돌 발생하면 그 버킷의 주소로부터 비어있는 버킷 발견할때까지 찾음.

폐쇄주소법(체인법) : 충돌이 발생하는 동의어 별로 연결리스트로 저장하는 방법.

                                합병 체인법, 분리 체인법 으로 나뉨.

 

11) 정렬

           - 정렬의 정의

무질서한 데이터를 일정한 key값에 의해 재분류하는 과정.

작업결과를 오름차순, 내림차순으로 구분.

-      정렬의 종류

삽입법 : insertion sort, shell

교환법 : bubble, selection, quick

선택법 : heap

병합법 : z-way-merge

분배법 : radix

-      8가지 중 5개 방법론 + 코딩방법

Bubble Sort : 가장 큰값을 맨 뒤로 이동해가면서 정렬하는 방법. 단계적으로 큰 값을 제외한다.

Select Sort : 가장 작은값을 맨 앞으로 이동해가면서 정렬하는 방법. 단계적으로 작은값을 제외한다.

Quick Sort (재귀함수) : 특정키값인 피벗설정하여 작은값 큰값 레코드 분리하여 서브리스트 구성. 가장빠른정렬수행.

Insertion Sort( 삽입정렬) 임시값 정해서 작은지 큰지 비교.

Shell Sort : 일정한 거리만큼 떨어진 2개의 데이터 비교하여 크면 보관하는 과정을 반복해 정렬.

 

Heap Sort : 데이터를 트리로 표현. 최하위 레벨의 우측 노드부터 부모노드와 비교. 자노드 값이 오면 부모노드와 교환.

루트노드에 가장 큰값이 위치하면 최하위 레벨의 우측 마지막 노드와 교환 뒤 , 이 값을 다음 heap에서 제외한다.