자료구조의 개념, 알고리즘, 성능분석, 배열, 스택과 큐 정리

1. 기본개념 

 

1) 자료구조와 알고리즘

 

* 자료 : 센서를 통해 수집된 현실세계의 값/사실 * 정보 : 의사결정에 사용할 수 있게 자료를 가공한 것

 

 

자료구조

 

(1) 자료구조 : 자료의 처리를 고려하여 표현/저장/처리하는 기술

↳분류 : 단순(정수/실수/문자(열),논리(=불단순(정수/실수/문자(열), 논리(=불)) /선형(리스트/스택/큐/데크) /비선형(트리/그래프) /파일(순차/직접/색인)

↳ 선형자료구조 : 기본선형(리스트,연결리스트기본선형(리스트, 연결리스트) / 제한선형(스택,큐,데크)

↳ * 데크 : 양쪽에서 삽입삭제가능. 제한형 : 스크롤(입력제한데크, 한쪽만 입력),셀프(출력제한데크, 한쪽만 출력)

 

(2) 알고리즘 : 특정문제를 기계로 해결하기 위한 절차를 표현한 것

문제해결방법을 추상화하여 단계적, 논리적으로 기술해 놓은명세서

↳ 조건일명유효한 : 입력 0개이상, 출력 1개이상1개 이상, 일반성/명확성/유효성(일반성/명확성/유효성(모든 과정 기능하는지)/효율성/유한성

↳ 기술방법 : 자연어(명확성↓(∵다의적)), 흐름도(순서도. flow chart), 의사코드(pseudo code), , 프로그래밍 언어

 

 

2) 자료(데이터)추상화

 

* 추상화(ADT로 알고리즘 정의) → 구체화(실제자료형으로 프로그램 구현)

 

(1) 자료추상화 : C언어의 구조체처럼 여러자료형여러 자료형을 하나로 묶어(단순화) 사람의관점(↔컴퓨터관점(bit))사람의 관점(↔컴퓨터관점(bit))으로 표현한 것.

 

(2) 추상자료형(ADT) : 자료와 연산을 하나로 묶어 캡슐화(자료-연산연결, 내부은닉)내부은닉) 한 형태.

↳ C언어로 ADT표현시, 구조체로 자료를 표현하고 함수로 연산을 표현.

 

 

3) SPARKS : 의사코드. 프로그래밍언어(C언어 등)로 쉽게 변경가능. 세미콜론(;)세미콜론(;)으로 문장구분

 

(1) 선언문 : 대상(변수/함수)에게 타입과 이름 부여. 컴파일러는 메모리확보 준비(초기화 시에( 메모리할당) int x;

 

(2) 지정문 : 지정연산자 ‘←’의 오른쪽 값/계산결과/변수를 왼쪽변수에 대입.(‘=’ 아님).(‘=’아님) x←3; x←5+3; x←y;

 

(3) 조건문

① if 문 : if(조건식) 종속문장;

② if~else 문(중첩가능) : if(조건식) 종속문장종속문장 1; else 종속문장2;

③ switch 문 : switch(조건식) {case값 1:문장 1;값1:문장 break; …… case값n:문장case값 n:문장 n; break; default; 문장n+1;}

↳ 조건식의 값과 같은 case값에 도달 시 문장실행하고 break으로 탈출(필수). casecase 중에 없으면 default(기본값)실행.

 

(4) 반복문

① while 문 : while(조건식) 반복문장; 반복문장 내부에 증감식 필요

② do~while 문 : do{반복문장do {반복문장} while(조건식); 조건에 상관없이 한번 실행.. 반복문장 내부에 증감식 필요

③ for 문 : for(초기식; 조건식; 증감식) 반복문장; for의 괄호‘()’내부는 세미콜론‘;’으로 구분

 

(5) 함수 : 부프로그램(sub-). 추상화한 프로세스 블록(명령어들의 묶음).

↳ 서브루틴과 차이 : 함수는 보통 1개의 리턴값을 반환(like 수학함수)하지만, 서브루틴은 반환하지 않을 수 있음.

* 프로시저 : 상세절차기술. 부프로그램/함수/서브루틴 포함하는 개념.

↳ 프로시저간 자료전달방법 : call by value(값전달), call by reference(매개변수주소(&) 전달),(매개변수주소(&)전달), call by address(포인터 전달), call by name(형식 매개변수->실 매개변수 이름으로 변경)

 

(6) 기타 : 입력(read), 출력(write), 프로그램중지(stop), 주석(// or /* ~ */)

 

 

4) 순환알고리즘

 

(1) 순환(reculsive)알고리즘 : 반복적 내포구조에 적합. 트리, 연결리스트 자료구조 사용.

① 팩토리얼 : factorial(n) = n*factorial(n-1); (단 factorial(1) = 1)

② 피보나치수열 : fib(n) = fib(n-1) + fib(n-2); (단 fib(1) = 1, fib(0) = 0)

 

5) 성능분석

 

(1) 성능분석 방법 : 시간복잡도 > 공간복잡도 (∵공간복잡도는 기술적으로 해결가능)

* 알고리즘과 관련된 부분에 대해서만 분석(일반적인 연산 부분은 제외).

① 시간복잡도 : 연산횟수연산 횟수를 의미(실제소요시간 X),(실제소요시간X),

② 공간복잡도 : 총공간요구 = 고정공간요구 + 가변공간요구(입/출력과 관련)

↳ 예시 : 팩토리얼의 경우 재귀함수로 구현시 O(n)이고, 반복문으로 구현(변숫값( 변경) 시)시 O(1)이다.

*

 

 

(2) 복잡도 표기법(점근적 표기법( 사용)

- 빅오(big-O)표기법 : 성능(함수)의 상한(최악). 알고리즘 성능이 아무리 나빠도 빅오보다는 시간이 적게걸림.

- 빅오메가(big-Ω)표기법 : 성능의 하한(최선). 알고리즘 성능이 아무리 좋아도 빅오메가보다는 시간이 많이 걸림..

- 빅세타(big-Θ)

표기법 : 빅오와 빅오메가의 중간값 표기.

 

 

 

2. 배열

 

(1) 배열(= 순차/순서/선형리스트) : 동일한 데이터형의 값들을 메모리에 순서대로 저장(물리적 순서=논리적 순서).(물리적순서=논리적순서).

↳ 특징 : 인덱스(=배열인수, 0부터)를 사용하므로 해당 배열요소에 바로 접근 가능(O(1)).

메모리공간 연속할당∵중간 삽입/삭제가 힘듦

 

① 1차원배열 : 자료형 배열명[원소개수];[원소갯수]; ex) int Arr [3]; int Arr [2] = {1,2};

② 2차원배열 : 자료형 배열명[행개수][열개수];[행갯수][열갯수]; ex) int Arr [3][3]; int Arr [2][2] = {{1,2}, {3,4}};

③ 3차원배열 : 자료형 배열명[면개수][행개수][열개수];[면갯수][행갯수][열갯수]; ex) int Arr [2][2][2] = {{{1,2}, {3,4}}, {{5,6}, {7,8}};

* 배열[n]의 주소 = 배열주소 + {자료형의 크기*(n)}자료형의크기*(n)} ex) int형 arr[2]arr [2]의 주소 = arr(=arr [0])의 주소의주소 + {4*2}

 

(2) 배열의 표현

* 저장순서 : 논리적인 2차원 이상의 다차원 배열을 물리적 순서로 저장할 때, 가장 낮은 차원부터 채워진 후 다음 차원이 채워지게(열->행->면->…) 주소가 할당된다. ex) 배열 a[2][3]a [2][3]의 a[0][2] 다음에는 a[1][0]a [1][0]이 저장됨..

 

* 우선순서방법 : 기본적인 n차원배열은 (최고차원)우선순서방법(최고차원) 우선순서방법으로 표현한다.

즉, 기본적 2차원배열은 행우선(기준)(row major) 순서방법,순서방법, 기본적 3차원배열은 면우선(기준) 순서방법이라(기준) 한다.

↳ 열 우선 순서방법인 배열 a [1][2][3]은면우선순서배열인 배열 b [3][2][1]와로 저장된다.

 

ex) 데이터형(자료형)이 int이고 배열의 최초주소가 α인 배열 a[3][4][5]a [3][4][5]가 열 우선 순서방법으로 저장된다고 할 때,

a[1][2][3]a [1][2][3]의 주소는?

→ 최초주소가 α인 기본 3차원배열 b[5][4][3]b [5][4][3]의 b[3][2][1]b [3][2][1]의 주소와 같으므로,

a[1][2][3]a [1][2][3]의 주소 = α + 4 * ( 3*(4*3) + 2*(3) + 1 ) = α + 4*(43) = α + 172

 

(2) 희소행렬 : 원소 대부분 값이 0인 행렬. 공간활용이 떨어지므로 00이 아닌 원소의 <행,열,값>을 2차원 배열로 변환.

* 전치행렬 : 행과 열이 바뀐 행렬. ex)

행렬의 전치행렬은

 

 

3. 스택과 큐

 

1) 스택

 

(1) 스택의 특징 : LIFO. 선형구조. TOP(인덱스 or 포인터)사용. PUSH/POP(삽입/삭제). peek(peek(삭제 안 하고 값만반환)

① 배열을 통한 구현 : 첫 번째 원소의 인덱스 0 (empty면 top=-1, full이면 top=n-1. ← n=최대원소개수)

 

- Push(S, x) : if (top==n-1) then overflow; else {top=top+1; S [top]=x;};

- Pop(S) : if (top==-1) then underflow; else return S(top); top=top-1;

 

② 단순연결리스트를 통한 구현 : empty면 top=null. top은 연결리스트의 head에 해당. overflow 없음.

 

(2) 시스템스택 : 함수호출시(순환호출 포함) 스택프레임(복귀주소, 지역변수, 매개변수등의 정보)을 저장.

최초 프로그램 실행 시main함수 스택프레임이 삽입되며, 프로그램 종료 시 시스템스택은 빈 상태.

 

(3) 스택의 적용분야 : 함수호출, 인터럽트(서브루틴), 재귀함수, 수식, 백트래킹(미로), 작업취소(undo) 등.

 

(4) 스택을 사용한 수식계산

① 후위표기식의 연산 : 괄호 필요 없음.. 연산자를 만나면 2개를 poppop 해서 연산결과를 push.

ex) 34*7+4- : push(3)→push(4)→pop()→pop()→push(12)→push(7)→pop()→pop()→push(19)→push(4)→pop()→pop()→push(15)

 

② 중위표기식->후위표기식 : 모든 연산에 괄호 씌움. ‘(’는 무시. 피연산자는 출력. 연산자는 push, ‘)’만나면 pop.

ex) 2*4-6/3 : ((2*4)-(6/3))으로 변환→출력(2)→push(*)→출력(4)→pop()→push(-)→출력(6)→push(/)→출력(3)→pop()→pop()으로변환→출력(2)→push(*)→출력(4)→pop()→push(-)→출력(6)→push(/)→출력(3)→pop()→pop() ← 24*63/-순으로 출력.

 

 

2) 큐(Queue)

 

(1) 큐의 특징 : FIFO. 선형구조. front/rear(첫번째원소(삭제용)/마지막원소(삽입용). enqueue/dequeue(삽입/삭제)

① 배열을 통한 구현 : 첫 번째 원소의 인덱스 0 (초기화 시초기화시 front=rear=-1, 비었으면 front=rear)

- enqueue(Q, x) : if (isFull(Q)) then overflow; else {rear=rear+1; Q [rear]=x;};

- dequeue(Q) : if(front==rear) then underflow; else {front=front+1; return Q [front];};

- isFull(Q) : 일반큐는 rear=n-1일 경우 포화상태이고, 원형큐는 (rear+1) Mod n = front일 경우 포화상태이다,

↳ 원형큐 : Mod연산 사용하여 논리적으로 원형으로 이어 붙인 큐(일반 큐의 잘못된 포화현상 해결)

** 포화상태와 공백상태(front==rear)의 구별로 인해 포화상태에 저장된 원소수는 최대원소수-1이다.

 

② 연결리스트를 통한 구현 : empty면 front=rear=null.

-enqueue(d) : struct listnode *temp=getNode(); temp->data=d; rear->link=temp; rear=temp;

-dequeue() :if(front=null) return(-1); else {temp=front; front=temp->link; printf(“% d”, temp->data); free(temp);};

 

(2) 큐의 적용분야 : CPU스케줄링, 기수정렬(버킷)/BFS(너비우선탐색), 버퍼/스풀링(I/O), 큐잉시스템(대기 시뮬레이션)

 

 

3) 데크(Deque. double-ended Queue)

 

(1) 데크의 특징 : 양끝에서 삽입/삭제(스택장점+큐장점). insert_front/rear, delete_front/rear

이중연결리스트로 구현(배열은 비효율적)

* 제한데크 : 스크롤(scroll. 입력제한데크. 한쪽입력/양쪽출력). 셸프(shelf. 출력제한데크. 양쪽입력/한쪽출력).

 

4) 다중스택과 다중큐

 

(1) 다중스택 : 한 배열에 두 개 이상의 스택이 있는 형태.

① 1차원배열에 2개의 스택 : 배열 양 끝을 bottom으로함. top1=top2일 경우 overflow.

② 1차원배열에 33개 이상의 스택 : top[i]=bottom[i+1]top [i]=bottom [i+1] 일 경우 overflow. top [i]=botton [i] 일op[i]=botton[i] 경우 underflow.

 

(2) 다중큐(우선순위큐) : 두 개 이상의 큐에게 다른 우선순위 부여. 다중큐작업스케줄링, 정렬 등에 사용.

 

 

 

 

4. 연결리스트

 

1) 연결자료구조

 

(1) 연결자료구조(↔순차자료구조) : 논리적순서≠물리적순서(비순차적)논리적 순서≠물리적 순서(비순차적). 오버헤드없음. 공간사용효율적.

 

(2) 연결리스트 : 크기변화가 동적. 연결자료구조. head포인터(처음)/마지막노드=null. 포인터저장공간(링크필드) 필요

 

 

2) 단순연결리스트

 

(1) 정의 : 단방향 연결(노드구성(구조체) : 데이터필드 1개 + 링크필드 1개).

↳ struct listnode {int data; struct listnode* link;}; struct listnode node_s;

(2) 리스트생성(getNode()(노드 동적할당) 사용))사용)

-> strcut listnode형 temp생성 후 temp->data와 temp->link값 지정

↳ getNode() : strcut listnode *temp; temp=(struct listnode*) malloc(size of node_s;) retrun temp;};

① 연결리스트가 공백 : temp->link = null;

② 연결리스트가 공백이 아닐 경우 : temp->link = head; head=temp;

 

(3) 노드삽입 : temp포인터로 동적할당한 노드 가리킨 후 데이터값, 링크값 삽입(인수 x값이 없으면 ① 있으면 ②)

struct listnode *temp=getNode();

if(temp=null) return(-1); else { temp->data=value; 아래 ① or ② };

① 맨앞(head맨 앞(head포인터가 가리키는 노드)에 삽입 : temp->link = head; head=temp;

② x포인터가 가리키는 노드의 다음에 삽입 : temp->link = x->link; x->link=temp;

 

(4) 노드삭제 : 공백확인 후 삭제할 노드를temp포인터가 가리키는 전노드가 다음노드를 가리키게 한 후 동적할당해제.

if(is_empty()) return(–1);

① 맨앞맨 앞노드 삭제 : temp=head; head=temp->link; free(temp);

② x포인터가 가리키는 노드의 다음노드 삭제 : temp=x->link; x->link=temp->link; free(temp);

 

(5) 노드출력(삭제X) : temp포인터로 머리(head)부터 발끝까지(?) 순서대로 출력.

temp=head; while(temp!=null){ printf(“% d”, temp->data); temp=temp->link; };

 

 

 

3) 비사용 기억공간

 

* 가용공간(=자유공간)리스트 : 생성 후 사용되지 않는 노드를 보관하는 공간.(주로 연결리스트형식)

* 순차가용공간(배열형식) : 미리공간을 노드로 분할.. 여러 리스트가 저장되어 있을 경우 overflow가 발생할 수 있음.

(1) 가용공간리스트 생성 = struct listnode *avail;

 

(2) 가용공간리스트로부터 노드획득(for 사용)

getNode() : if(avail=null) then underflow; else {temp=avail; avail=avail->link; return temp;};

 

(3) 가용공간리스트로 반환(사용종료)

returnNode(x) : x->link=avail; avail=x;

 

 

 

4) 연결리스트 응용

 

(1) 다항식 표현 : 노드를 2개의 데이터필드(계수, 지수)와 1개의 링크필드로 구성. (

에서 A=계수, B=지수)

↳ 연산 : 3개의 리스트(피연산 리스트 2개(A,B)2개(A, B)와 결과 저장용 리스트(C))와 3개의 포인터(a, b, c)(a,b,c) 필요.

a,ba, b로 A,B의 head부터 차례대로 지수가 동일한 노드의 계수값을 연산하여 C에 c를 사용해 저장해 나감.

 

(2) 단순연결리스트를 역순으로 : 3개의 포인터 필요(역순으로 바뀐 노드(b)/현재바꿀노드(a)/다음에(b)/현재바꿀노드(a)/ 바꿀노드(lead))

↳ lead=head; a=null;로 시작해서 b=a; a=lead; lead=lead->link; a->link=b; 반복

 

(3) 두 개의 단순연결리스트를 연결 : 한 리스트의 끝(null)을 찾아서, 그 끝이 다음리스트의 처음(head)을 가리키게 함..

 

(4) 원형연결리스트에 노드삽입 : head가 리스트의 끝을 가리키는 것이 뒤에삽입시 효율적

head가 리스트의 처음을 가리킬 경우 리스트뒤에 노드 삽입시 끝까지 찾아가야 함..

① 리스트의 앞에 노드삽입 : temp->link=head->link; head->link=temp;

 

② 리스트의 뒤에 노드삽입 : temp->link=head->link; head->link=temp; head=temp;

 

 

 

5) 이중연결리스트

 

(1) 특징 : 양방향 포인터(한쪽연결이 끊어져도 복구용이, 이전노드탐색 용이) 추가메모리필요(∵링크필드1추가메모리필요(∵링크필드 1개 추가됨)

 

(2) 노드삽입(x오른쪽) : temp=노드생성; temp->data=값; temp->rlink=x->rlink; temp->llink=x; x->rlink=temp;

temp->rlink->llink=temp;

 

(3) 노드삭제 : temp->rlink->llink=temp->llink; temp->llnik->rlink=temp->rlink; free(temp);

 

* 단순연결리스트, 이중연결리스트, 원형연결리스트의 삽입/삭제 연산 시시 탐색의 효율성 비교

삽입연산시	원형연결리스트 > 이중연결리스트	원형연결리스트는 앞,뒤 삽입이 모두 용이
삭제연산시	이중연결리스트 > 단순연결리스트	단순연결리스트는 무조건 처음부터 탐색해야함

 

 

6) 일반(범용)리스트

 

(1) 개념 :

.

공백(널) 리스트(헤드/테일(널)리스트(헤드/ 없음). 리스트명은 대문자, 원소명은 소문자

ex) A=(a, (b, (), c)) -> head(A)=a, tail(A)=((b, (), c)),리스트길이 2(원소a+리스트1개)

B=(a, B) -> 무한리스트(a,(a,(a,…), 리스트길이 2(원소a+리스트B)

 

(2) 노드 : 태그필드(데이터필드가 값(0. 원소)인지 포인터(1. 리스트)인지)+데이터필드(head원소)+링크필드(tail리스트)

 

(3) 활용 – 다중변수다항식

* 노드구성 = 계수필드(계수값 or 변수 or 다른 변수노드를 가리키는 포인터)+지수필드+링크필드.

* 표현방법 : 지수와 변수가 같은 것들을 묶어서 단순화시킨 후 다음노드/리스트로 연결해 가며 표현.

 

 

5. 트리

 

1) 트리

 

(1) 특징 : 비선형. 계층구조. 1:다. 비순환(↔그래프).

↳ 용어 : 루트노드(최상위), 자식(바로아래)/부모(바로위)/형제(같은부모)노드자식(바로아래)/부모(바로 위)/형제(같은 부모) 노드, 자손(아래모든)/조상(위모든)노드.

잎/리프/단말노드(자식노드가 없는 노드), 가지노드(가지(단말노드)를 가지는 노드)

포레스트(루트노드제거로 생성되는 서브트리집합), 서브트리(노드아래트리)

차수(자식노드수), 계수(계수(트리전체 중 가장 높은 차수),), 노드높이/깊이(루트노드부터의 거리), 트리높이(최대높이)

이진트리(차수=계수=2인트리), 편향트리(한쪽으로만 자식노드가 연결된 트리)

 

2) 이진트리

 

(1) 이진트리 : 순환적구성 최대노드수=

(n=최대높이=트리높이). 공백노드도 자식노드.

* 일반트리를 이진트리로 만들기 : 왼쪽자식노드 빼고 간선 제거하고 자식노드의 형제노드들을 연결 후 45도 회전

① 완전이진트리 : 부모,왼쪽,오른쪽순부모, 왼쪽, 오른쪽순으로 채워지는 이진트리. 포화가 아닐 경우 최고레벨 마지막까지는 공백노드. 힙

② 포화이진트리 : 모든레벨(층)모든 레벨(층)이 채워진 이진트리. 완전이진트리의 일종.

   

② 연결리스트로 표현 : 데이터필드1개+링크필드2개(노드구성), 자식노드 없는 방향 링크필드=NULL.

 

(3) 이진트리 순회 : 전체노드방문. 전위순회(루트-좌-우)/중위순회(좌-루트-우)/후위순회(좌-우-루트)

 

(4) 이진트리의 활용

① 오름차순 정렬 : 이진탐색트리에 삽입 후 중위순회하여 출력 시 오름차순으로 정렬됨.

 

② 수식트리 : 연산자=가지노드, 피연산자=단말노드. 후위순회방식으로 스택을 사용하여 연산.

 

③ 명제논리 : 논리연산자=가지노드, 명제=단말노드.

 

(5) 스레드이진트리 : 재귀호출 없이 순회가능. 링크필드가 nullnull일 경우 방문한(왼쪽)/방문할(오른쪽) 노드의(왼쪽)/방문할(오른쪽) 주소 저장.

최좌 측의 좌측링크와 최우 측의 우측링크는 루트노드를 가리킴.

↳ 구성 : 데이터필드1+링크필드2+태그필드2(데이터필드 1+링크필드 2+태그필드 2(양쪽의 링크필드가 실제자식노드인지 아닌지를 구분할 태그가 필요)

 

 

(6) 히프 : 최대히프(부모≥자식. 내림차순)/최소히프(부모≤자식. 오름차순). 완전이진트리. 우선순위큐에 사용.

* 우선순위큐 : 높은우선순위부터 출력(FIFO아님). 배열/연결리스트/히프로 구현가능. 히프가 가장 효율적.

↳ 삽입 : 가장마지막자리에 삽입 후 부모노드와 비교해 가며 재정렬.

삭제 : 빈 루트자리에 가장마지막자리의 노드를 삽입 후 부모노드와 비교해 가며 재정렬.

 

(7) 이진탐색트리 : 크기기준 정렬된 트리. 같은 수 중복불가. 루트기준 왼쪽은 작고 오른쪽은 큰 수로 연결.

.

↳ 삽입 : 최초 입력데이터를 루트노드, 재귀호출방식으로 새로운 입력데이터를 기존노드와 대소비교해 가며 삽입

삭제 : ① 단말노드일 경우 : 그냥삭제 ② 자식노드가 한 개일 경우 : 부모와 자식노드를 연결

③ 자식노드가 두 개일 경우 : 왼쪽서브트리 중 가장 큰 노드 or 오른쪽서브트리 중 가장 작은 노드를 대치 후 연결

 

(8) 선택트리(승자/패자트리) :

(병합정렬은 n-1) 다수의 런(오름차순정렬)들을 하나로 병합하는 이진트리.

① 승자트리 : 각 런에서 말단노드에 삽입 후 토너먼트방식으로 더 작은(이긴) 수가(이긴) 부모노드값을 결정하는 방식.

제거되는 루트노드값의 말단노드에 해당하는 런에서 다음수를 삽입하는 것을 반복.

 

② 패자트리 : 부모노드에는 더 큰(진) 수가(진) 입력되고, 이긴 수는 올라가는 것을 반복. 루트노드 위에 0번노드(승자) 있음.

 

(9) 이진트리의 개수계산 : n개(노드수)로 표현할 수 있는 상이한 이진트리의 개수.. ex) n=2->2개, n=3->5개

* 스택순열 : 스택을 사용하여 기존 순열을 서로 다른 순열로 만드는 것. = 상이한 이진트리의 개수..

(∵ 모든 이진트리는 유일한 전위-중위 순서쌍을 가짐. 어떤 전위-중위순서쌍에 대해 유일한 이진트리를 가짐)

ex) (a, b, c)는 스택을 통해 (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, b, a)로 만들 수 있음. (c,a,b)(c, a, b)는 불가

↳ 전위-중위순서쌍을 트리로 그리는 방법 

① 스택을 사용하여 기존 순서쌍을 다음 순서쌍을 만드는 과정을 PUSH와 POP으로 정리

② PUSH는 공백노드에 왼쪽화살표, POP은 현재위치(없으면 가장 가까운 오른쪽조상)에 값과 오른쪽화살표.

 

(2) 이중연결성 : 단절점(두 연결성분을 이어주는 점) 이) 없는 그래프를 이중연결그래프라고 함.

 

(3) 강 연결성분 : 해당 연결성분이 방향그래프이고, 연결되어 있는 모든 간선이 양방향성or사이클(재귀적)양방향성 or사이클(재귀적)이면 강연결성분이라고 함. 깊이우선탐색으로 구할 수 있음.

(4) 합-찾기 : 서로소집합에 대한 연산. 연결리스트나 트리로 만들 수 있음.

- Make-Set(x) : x를 단일 원소로 하는 집합을 만듦

- Find-Set(x) : x가 속한 집합의 대표원소(맨 앞원소(리스트),(맨앞원소(리스트), 루트노드(트리)) 반환(각 원소가 포인터로 가리킴)

어떤 두 원소가 같은 집합에 속했는지 비교할 때 사용

- Union(x, y) : x가 속한 집합과 y가 속한 집합을 합침.

 

정점 A와 B가 연결되어 있을 때, 간선(A,B)간선(A, B)은 정점 A와 B에 부속되며, A와 B는 인접함.

↳ 종류 : 무방향그래프(화살표 없음), 방향그래프(화살표(아크)있음), 가중치그래프(=네트워크. 간선에 가중치 있음))

완전그래프(모든 정점 간에 간선이 있음), 부분그래프(원래그래프의 일부정점이나 간선이 없는 그래프)

연결그래프(간선이 없는 정점이 없는 그래프 트리), 평면그래프(간선이 교차하지 않게 그릴 수 있는 그래프)

용어 : 차수(간선수, 방향그래프는 진입+진출차수), 경로길이(경로를 구성하는 간선의 수(정점수아님)(정점수아님)

단순경로(경로를 구성하는 정점이 모두 다른 경로),), 사이클(시작정점과 마지막정점이 같은 단순경로)

트리(사이클을 형성하지 않는 그래프), DAG(사이클을 형성하지 않는 방향그래프)

 

 

2) 그래프 표현방법

 

(1) 인접행렬 : n×n정방행렬(n=정점수). 행에서 열로 간선이 진입하면 1(∴무방향은 대칭행렬). 희소행렬은 메모리낭비

 

(2) 인접리스트 : 포인터배열(헤드노드)로 정점들 구성. 각 정점에 연결된 모든 정점들을 연결리스트로 연결.

 

3) 그래프의 순회(탐색)

 

(1) 깊이우선탐색(DFS) : 스택(LIFO)사용. 저장공간이 상대적으로 적게 필요. 탐색탐색완료 후 깊이우선 신장트리가 됨.

↳ 자식노드 중 하나를 스택에 삽입해 가며,해가며, 자식노드가 없을 경우 자식노드가 있는 노드까지 되돌아감. 중복 시 방문 안 함..

 

(2) 너비우선탐색(BFS) : 큐(FIFO)사용. 저장공간이 상대적으로 많이 필요. 탐색탐색완료 후 너비우선 신장트리가 됨.

↳ 큐에서 나오는 노드의 자식노드를 큐에 삽입하는 방식. 중복 시 방문 안 함..

 

 

4) 신장트리

 

(1) 신장트리 : 모든 정점이 직간접적으로 연결된 트리. 간선수=정점수-1개.

 

(2) 최소비용 신장트리 : 무방향가중치 그래프에서 가중치합이 최소인 신장트리.

- ① 프림알고리즘 : 이미 선택된 정점들로부터 가장 가중치가 작은 간선의 정점을 추가해 나가는 방법

- ② 크루스칼 알고리즘 : 전체중전체 중에서 가장 작은 가중치의 간선을 추가해 나가는 방법.

 

5) 그래프의 응용

 

(1) PERT/CPM : DAG 사용. PERT(시간만고려)/CPM(시간과비용고려). 모든 선행작업이 완료되어야 해당작업이 가능.

방법 : 모든작업(노드)표시 → 화살표(간선)로 선행관계표시 → 작업별 기대시간표시 → 주공정경로/최단완료시간 확인

↳ 주공정경로(critical path) : 전체작업을 최단시간으로 완료하는 데 있어서 결정적으로 작용하는(가장 긴)(가장긴) 경로.

 

* 가상활동(더미활동) : 선행관계만 있고, 필요한 작업시간은 없는 공정. 완료되어야 다음작업 가능.

ex) a, b를 완료해야 c를 작업할 수 있을 때, a는 2시간소요되고 b->c는 필요시간이 없다면 b->c는 더미공정이다.

 

* 표현방법 : AON(마디상 활동) : 활동과 시간을 노드에 표시 / AOA(화살표상 활동) : 활동과 시간을 화살표에 표시.

 

* 전진계산법(ES/EF) : 시작노드부터 구함. ES=해당활동을 시작하기 위한 가장 빠른 시간, EF=ES+활동에 필요한 시간.

* 후진계산법(LS/LF) : 완료노드부터 구함. 전체완료시간에 영향을 안주는 범위 안에서 가장 늦은 시간(LS와 LF) 구함.(LS와LF)구함.

 

(2) 최단경로알고리즘 : 가중치그래프에서 두 정점사이의 최단경로를 구하는 알고리즘

* 다익스트라 알고리즘 : 한 정점으로부터 나머지 점까지의 거리 중최단경로인 노드를 추가해 감.. 양수가중치만 가능.

↳ 구현 : 인접행렬(2차원배열)에 이미 추가된 노드집합(A)의 원소로부터 아직 추가되지 않은 노드집합(B)의 원소까지 최단거리를 지속 변경해 가며, 노드집합B 중 최단거리인 원소를 노드집합 A에A 추가해 나감.해나감.

* 노드집합B노드집합 B의 각 원소까지의 거리는 무한(∞, infinite)이다.

 

* 벨만포드 알고리즘 : 다익스트라와 동일하지만 음의 가중치도 가능(단 음의사이클(사이클의 가중치합이 음수) 불가)

 

 

 

7. 탐색과 정렬

 

1) 탐색(검색)

 

(1) 탐색 : 탐색키(유일성만족)로 원하는 레코드를 찾는 작업.

* 내부탐색 : 메모리(주기억장치)탐색 / * 외부탐색 : 보조기억장치 탐색

 

(2) 내부탐색방법

- 비교탐색

① 순차탐색 : 처음부터 차례로 탐색. 정렬이 되지 않은 경우도 탐색가능. 구현간단. 비효율적.

② 이진탐색 : 재귀적(반복호출)으로 반으로 분할(나눗셈)해 탐색. 이미 정렬되어 있는 경우만 탐색가능.

③ 피보나치탐색 : 재귀적. 가감연산만 사용해 이진탐색보다 빠름(대신 오버헤드발생). 첫번째 0, 두 번째 1로시작.

 

계산탐색 : 해싱(계수탐색)

 

(3) 외부탐색탐색

① ISAM : 인덱스를 사용하는 순차접근방식. 기본구역(킷갑순정렬된 레코드)+인덱스구역(레코드포인터)+오버플로구역

② B-Tree(균형트리) : 루트부터 단말까지 길이가 모두 같은 트리. 자식수 = 노드내데이터수 +1(∵값기준으로 구역 나눔))

 

 

2) 정렬 : 탐색의 용이성을 위해 필요. 비교 횟수와 이동 횟수가 적을수록 우수.

 

(1) 선택정렬 : 가장 왼쪽부터 정렬완료. 위치를 먼저 선택 후 그 오른쪽 전체를 비교/교환해서 정렬.

ex) 오름차순 정렬일 경우 왼쪽의 이정렬부 바로 오른쪽의 데이터를 그 오른쪽 전체와 비교해 최솟값을 찾아 교환.

 

(2) 버블정렬 : 가장 왼쪽부터 옆과 차례로 비교해 가서해가서 가장 오른쪽부터 정렬완료..

 

(3) 삽입정렬 : 최초 두 번째부터 오른쪽으로 왼쪽의 이정렬부 전체와 비교해서 맞는 자리에 삽입하는 방식.

이미 어느 정도 정렬이 진행되었던 리스트일 경우 효과적. 정말정렬된 리스트에 삽입할 경우 최선

 

(4) 셸 정렬 : 일정간격(k)의 데이터들 대상으로 삽입정렬을 수행해 감.. k를 1까지 점점 줄여나가는 방식.

 

(5) 퀵 정렬 : 임의의 피벗(중심)을 정한 후두 포인터로 양끝부터 피벗에 비해 큰 수와 작은 수를 찾아 교환해 가며 정렬.

분할정복알고리즘. *양끝 포인터 만날 시: 해당값과 피벗을 서로교환 후후 피벗중심으로 양쪽을 나눠 반복.

항상 피벗이 중간값일 때가 최선이다.

 

(6) n-way 합병정렬 : 분할정복 알고리즘. 분할단계(n분할단계(n 개씩 원소단위까지 분할) + 합병단계(n개씩 정렬하며 합병)

분할단계 중간에 임시배열이 필요하므로 추가기억공간이 필요해서 정렬 방법 중 가장 많은 메모리를 사용함.

합병단계에서 n개의 부분리스트의 대소를 비교해 1개의 리스트로 합병(=선택트리)하기를 반복.

 

(7) 히프정렬 : 히프(완전이진트리)로 정렬 후 출력. 부모인덱스=자식인덱스÷2.

 

(8) 비교하지 않는 정렬(안정적 정렬)

① 계수정렬(counting-) : 숫자를 순서대로 정렬. 숫자별 개수를 차례로 누적한 값-1을로 사용

 

② 기수정렬(radix-) : 기수(진수)만큼 버킷을 만들고, 가장낮은자리부터 해당자리기준으로 버킷에 넣고 순서대로 출력한 후 다음자리기준으로 버킷에 넣는 것을 반복하여 정렬.

d=총자릿수

↳ 안정적정렬(stable-) : 같은값같은 값의 원소들이 정렬 후에도 정렬전과 같은 순서를 가지는 정렬.