기억은 필기를 이기지 못한다

<<Queue>>

특징 : 선입선출(FIFO)리스트, 가장 먼저 들어온 데이터가 가장 먼저 나감

한쪽 끝(rear)에서 삽입이 일어나고, 반대쪽 끝(front)에서 삭제가 일어나는 순서리스트

용도 : 입력된 순서대로 출력이 필요한 경우 ex) 운영체제 : 프로세스나 쓰레드 관리

<enqueue>

rear에서 데이터 삽입이 일어남

<dequeue>

front에서 데이터 삭제가 일어남

<<ArrayQueue>>

1차원 배열 queue[MAX_SIZE]사용

변수 front : 저장된 첫 번째 원소의 앞자리 인덱스 저장, 평상시 공백을 가리키고 있음

변수 rear : 저장된 마지막 원소의 인덱스 저장, 평상 시 마지막 원소를 가리키고 있음

상태 표현 : 초기상태 - front = rear = -1

공백상태 - front = rear

포화상태 - rear = MAX_SIZE -1

<enqueue>

마지막 원소 뒤에 삽입해야 하므로 마지막 원소의 인덱스를 저장한 rear 값을 하나 증가 시켜 삽입할 자리 준비 -> 수정한 rear 값에 해당하는 배열 공간 Q[rear]에 요소를 저장

<dequeue>

가장 앞에 있는 원소를 삭제해야 하므로 front의 위치를 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비 -> front 자리의 원소를 삭제하여 반환

<peek>

가장 앞에 있는 원소를 검색하여 반환 = front + 1

<문제점&해결>

삽입, 삭제가 여러 번 일어나면 rear와 front는 점점 뒤로 이동, 시간이 지나면 앞 자리가 공백이지만 rear가 MAX_SIZE -1 상태이므로 포화상태로 인식 할 수 있음

저장된 원소들을 배열의 앞부분으로 이동시켜야 함 -> Circular을 사용하여 개선

<<Circular Queue>>

논리적으로 배열의 처음과 끝이 연결되어 있다고 가정

Front와 rear의 위치가 배열의 마지막 인덱스에서 논리적인 다음 자리인 인덱스 0으로 이동하기 위해서 나머지 연산자(mod, %)를 이용 - +1하게 되는 상황에서 %MAX_SIZE사용

<<Linked Queue>>

단순 연결 리스트 사용

변수 front : 첫 번째 노드를 가리키는 포인터 변수

변수 rear : 마지막 노드를 가리키는 포인터 변수

상태 표현 : 초기상태와 공백상태 - fornt = rear = NULL;

<enqueue>

Empty면 첫 노드이자 마지막 노드가 됨, else rear->link(마지막노드의 링크) = newnode, rear(마지막 가리키는 포인터) = new node

<dequeue>

Empty면 Error, temp = Q->front, e = temp->data;, Q->front = temp->link, free(temp);return e;

<peek>

Return Q->front->data;

<<Deque>>

Double-ended Queue, 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐

스택과 큐의 특성을 모두 지니고 있으므로 덱을 스택으로도 큐로도 활용할 수 있음

양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서 변화가 많으므로 배열은 비효율적, 양방향으로 연산이 가능한 이중 연결 리스트를 사용!

<<Stack>>

개념 : 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

특징 : 후입선출(LIFO)리스트, 가장 최근에 들어온 데이터가 가장 먼저 나감

Top 이라고 하는 한 쪽 끝에서 모든 삽입, 삭제연산이 일어나는 순서 리스트

용도 : 입력과 역순의 출력이 필요한 경우

            Ex) editor에서 undo기능, 함수호출에서 복귀주소 기억

구현방법 :

1. Linear Lists(Array) : 구현 간단, 크기 변경 어려움

2. Linked Lists: 크기 제한 없음, 구현 복잡

<<Array Stack>>

Stack[Max_SIZE]사용

변수 top : 가장 최근의 삽입된 요소를 가리키는 변수, -1이면 공백스택

가장 먼저 삽입된 요소는 stack[0]에 가장 최근에 삽입된 요소는 stack[top]에 저장

<push>

full이면 overflow, top += 1, S->stack[S->top] = element

<pop>

Empty면 underflow, e = S->stack[S->top], S->top -= 1, return e;

<peek>

Empty면 underflow, return S->stack[S->top]

<<Linked Stack>>

단순 연결 리스트 사용

변수 top : 가장 최근에 삽입된 요소를 가리키는 변수, NULL이면 공백스택

가장 먼저 삽입된 요소는 마지막 노드(link가 NULL), 가장 최근에 삽입된 요소는 첫 번째 노드

<push>

맨 처음 노드로 삽입

<pop>

맨 처음 노드를 삭제

<peek>

Return S->top->data;

<Stack Example 1. 수식 괄호 검사>

왼쪽 괄호를 만나면 스택에 push -> 오른쪽 괄호와 만나면 스택을 pop하여 오른쪽 괄호와 짝이 맞는지 검사 -> 마지막 괄호까지 조사한 후 스택에 괄호가 남아 있으면 거짓

<Stack Example 2. 수식 후위 표시법>

괄호가 없는 경우 : 피연산자를 만나면 그대로 출력 -> 연산자를 만나면 스택에 push할 지 여부 결정( 스택에 아무것도 없으면 push, 스택의 top에 있는 것보다 연산자의 우선순위가 더 높으면 push, 같거나 더 낮으면 pop하여 출력하고 결정 단계로 되돌아감 -> 수식의 끝에 도달하면 스택의 모든 연산자 pop하면서 출력

괄호가 있는 경우 : 조건 추가 - "("는 연산자로 수식에 있을 경우 다른 연산자보다 높은 우선 순위를 가짐 스택에 들어 있을 경우 모든 다른 연산자보다 낮은 우선순위를 가짐

")"는 연산자로 간주하지 않고 만나면 스택에서 연산자를 하나씩 pop하여 이것이 "("이면 버리고 다음 토큰으로 진행 "("아니면 꺼낸 연산자를 출력하고 되돌아감

중위표기법으로 변환 : 피연산자를 만나면 스택에 push -> 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산 후, 다시 스택에 push -> 수식이 끝나면 마지막으로 스택을 pop하여 출력

*List 구현 방법

Linear lists : 구현이 간단하지만 삽입, 삭제 시 오버헤드발생, 항목의 개수 제한이 있음

Linked lists : 삽입, 삭제 효율적이며 크기가 제한없지만 구현이 복잡하다.

<<Linear lists>>

<삽입>

중간에 원소가 삽입되면 그 이후 원소들은 한 자리씩 자리를 뒤로 이동해야함.

방법 : 삽입할 빈 자리 만들기 -> 원소 삽입

이동횟수 : (n + 1)개의 원소로 이루어진 Linear lists에서 k번 자리에 원소 삽입 시, n번째 원소부터 k번째 원소까지 (n - k + 1)개의 원소를 이동

<삭제>

중간에 원소가 삭제되면 그 이후의 원소들은 한 자리씩 자리를 앞으로 이동

방법 : 원소 삭제 -> 빈 자리 채움

이동횟수 : (n + 1) 개의 원소로 이루어진 Linear lists에서 k번 자리에 원소 삭제 시, k+1부터 n번 째 원소까지 (n - k)개의 원소를 이동

<Linear lists 응용 및 구현>

1.     Polynomial(다항식)

2.     Matrix(행렬 연산)

<<Linked Lists>>

특징 : 자료의 논리적인 순서와 물리적인 순서가 불일치

1.     각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식으로 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음

2.     여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현하므로 크기 변경이 유연하고 더 효율적으로 메모리를 사용

분류 : 리스트의 연결방식에 따라 단순 연결리스트, 원형 연결 리스트, 이중 연결 리스트로 나눔

구성 :

1.     Node = Data Field + Link Field

2.     Head = 리스트의 첫 번째 노드를 가리키는 변수

<삽입>

* List가 비어있을 때

0.     첫 번째 노드로 삽입

1.     마지막 노드로 삽입

2.     중간 노드로 삽입

<삭제>

1.     삭제

삭제할 노드의 앞 노드를 찾음 -> 앞 노드의 링크 필드에 삭제할 노드의 링크 필드 값을 저장 -> 삭제할 노드를 삭제 (free)

<탐색>

<<Circular Linked Lists>>

정의 : 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트

특징 : 링크를 따라 계속 순회하면 이전 노드에 접근 가능

<<Doubly Linked Lists>>

정의 : 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

노드구조 : llink + data + rlink

응용 : Polynomial

<<재귀함수>>

Ex0) Factorial

           if(n == 0)

                      return 1;

           else

                      return n * Factorial(n-1);

Ex1) Fibonacci Number

Ex2) Binary Search Algorithm

Ex3) Tower of Hanoi

           목적 : 원반 n개를 A에서 C로 이동

 1.     작은 원반 n-1개를 A에서 B로(HanoiTower(n-1, from, to, tmp)

 2.     큰 원반 1개를 A에서 C로(printf)

 3.     작은 원반 n-1개를 B에서 C로(HanoiTower(n-1, tmp, from, to)

<<데이터구조>>

<좋은자료구조>

Easy to process(Algorithm)

It depends on what you want to do with the data structures

<데이터구조 분류>

1.     단순구조

      정수, 실수, 문자, 문자열

2.     선형구조 (자료들 사이의 관계가 1:1 관계)

리스트, 스택, 큐

3.     비선형구조 (자료들 사이의 관계가 1:n 또는 n:n 관계)

트리, 그래프

4.     파일구조 (서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조)

           순차파일, 색인파일, 직접파일

<추상자료형>

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열하는 것

<시간복잡도>

Ex) T(n) = n^2 + 2n + 1 -> O(n) = n^2

Big-Oh : T(n)에서 실제로 영향력을 끼치는 부분(T(n)이 다항식일 때 최고차항의 차수)

<<Sort>>

정렬 : 순서 없이 배열된 자료를 오름차순이나 내림차순으로 재배열 하는 것

Key : 자료를 정렬하는데 사용하는 기준이 되는 특정 값

<분류>

실행방법 :

1. 비교식 정렬 - 비교할 키 값을 한번에 두 개씩 비교하여 교환함으로써 정렬을 수행

2. 분배식 정렬 - 키값을 기준으로 자료를 여러 개의 부분집합으로 분해하고 각 부분집합을 정렬

정렬장소 :

1. 내부 정렬 - 컴퓨터 메모리 내부에서 정렬

2. 외부 정렬 - 메모리의 외부인 보조 기억 장치에서 정렬

<내부 정렬>

정렬할 자료를 메인 메모리에 올려서 정렬하는 방식

정렬 속도가 빠르지만 정렬할 수 있는 자료양이 메모리의 용량에 따라 제한

*내부 정렬의 분류

비교식: 1. 교환방식: 키를 비교하고 교환하여 정렬(선택, 버블, 퀵)

2. 삽입방식: 키를 비교하고 삽입하여 정렬(삽입, 셸)

3. 병합방식: 키를 비교하고 병합하여 정렬(merge)

4. 선택방식: 이진트리를 사용하여 정렬(heap, tree)

분배식: 1. 키를 구성하는 값을 여러 개의 부분 집합에 분배하여 정렬 - 라딕스정렬(기수정렬)

<선택 정렬>

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

시간복잡도 : O(n^2)

<버블 정렬>

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식, 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬

시간복잡도 : O(n^2)

<퀵 정렬>

정렬할 전체 원소에 대해서 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법 (divide & conqure)

왼쪽 부분 집합은 pivot보다 작은 원소, 오른쪽 부분 집합은 pivot보다 큰 원소

시간복잡도 : O(nlogn)

<삽입 정렬>

정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법

시간복잡도 : O(n^2)

<Shell 정렬>

일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법

시간복잡도 : O(n^1.25)

<merge 정렬>

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법

부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 정렬된 부분집합들을 다시 결합하는 divide & conqure 기법 사용

시간복잡도: O(nlogn)

<Radix 정렬>

원소의 키값을 나타내는 기수를 이용한 정렬방법

정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하면서 정렬

키 값의 자리수 만큼 기수 정렬을 반복

시간복잡도 : O(d(n+r))

<Heap 정렬>

Heap 자료구조를 이용한 정렬방법

Heap의 삽입을 모두 한 후 root node 하나씩 heap 삭제 반복

시간복잡도 : O(nlogn)

<Tree 정렬>

이진 트리 탐색을 이용해 정렬하는 방법

정렬할 원소들을 이진 탐색 트리로 구성 -> 중위 순회하며 원소 저장

시간복잡도 : O(nlogn)

<<Graph>>

연결되어 있는 원소들 사이의 다:다 관계를 표현하는 비선형 자료구조

Graph G - 2개의 집합 v(vertax)와 e(edge)로 구성

           V: 공집합이 아닌 정점의 유한집합

           E: 간선이라고 하는 정점 쌍들의 집합

           표기: G = (V, E)

* Graph 종류

무(방)향 그래프(undirected graph)

           두 정점을 연결하는 간선에 방향이 없는 그래프

           간선을 나타내는 쌍에 순서 없음

           간선을 통해서 양방향으로 갈 수 있음

방향 그래프(directed graph)

           모든 간선은 방향을 가짐

           방향은 정점의 쌍 <u, v>정점의 순서로 표시. (u -> v)

부분 그래프(sub graph)

           원래의 그래프에서 정점이나 간선을 일부만 제외하여 만든 그래프

가중 그래프(weighted graph) or network

           정점을 연결하는 간선에 가중치를 할당한 그래프

* Graph 용어

인접정점(adjacent vertax) : 하나의 정점에서 간선에 의해 직접 연결된 정점 B->D (o), B<-C (x)

방향 그래프의 차수: 진입 차수, 진출 차수

무방향 그래프의 차수 : 모든 간선 수 * 2

정점 u로부터 정점 v까지의 경로(path): u에서 v까지 간선을 따라 갈 수 있는 정점을 순서대로 나열한 것

경로의 길이: 경로 상에 있는 간선의 수

단순 경로: 경로중에 반복되는 간선이 없는 경로

사이클: 시작정점과 종료 정점이 동일한 단순 경로

DAG(direvted acyclic graph): 방향그래프이면서 사이클이 없는 그래프

*그래프 연결정도

연결그래프(connected graph): 모든 정점 쌍에 대하여 항상 경로 존재하는 무방향 그래프

*tree : 사이클을 가지지 않는 연결 그래프

단절그래프: 연결되지 않은 정점이 있는 그래프

연결요소: 최대 연결 부분 그래프

완전그래프: 모든 정점이 연결되어 있는 그래프

강력 연결 : 방향그래프에서 서로다른 두 정점 u, v의 모든 쌍에 대해 u에서 v로 v에서 u로의 방향 경로 존재

강력 연결 요소: 강력 연결된 최대 부분 그래프

약한 연결 : u에서 v로 또는 v에서 u로의 어느 하나의 경로만 존재

<graph의 표현>

1.     인접 행렬(adjacent matrix)

행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법

그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장

인접행렬의 대각선 성분은 모두 0

2.     인접 리스트(adjacent list)

연결 자료구조를 이용하며 각 정점에 대한 인정 정점들을 연결하여 만든 단순 연결리스트

<graph traversal>

하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산

Ex) 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부

그래프 탐색방법: 깊이 우선 탐색, 넓이 우선 탐색

1.     깊이 우선 탐색 원리 (스택 사용)

하나의 정점 방문 -> 이웃한 정점으로 갈 수 잇으면 무조건 이웃 중 하나로 방문(push) (과거에 방문하지 않은 정점이어야 함) -> 반복 -> 만약 방문 가능한 이웃 정점이 없다면 (pop) 왔던 경로 상의 가장 최근에 방문했던 정점으로 돌아가서 그 정점 이웃 노드 방문을 시도

2.     너비 우선 탐색 원리 (큐 사용)

시작정점 v를 방문 -> v에 인접한 모든 정점들을 방문(enqueue) ->모두 찾았으면 앞에부터 dequeue하며 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문 -> 반복 -> 큐가 공백이면 탐색 종료

<<Spanning Tree>>

그래프 G의 신장 트리

           조건: G는 연결 그래프

           정의: G의 spanning tree는 G의 모든 정점들이 포함되어야 하며 연결 그래프이고 acyclic

*n개 정점의 그래프의 신장트리는 n-1개의 간선을 가짐

신장트리 구하는 방법: 깊이 우선 신장트리. 너비 우선 신장트리

<최소 비용 신장 트리>

무방향 가중치 그래프에서 최저의 비용을 갖는 신장트리(간선들의 가중치 합이 최소)

최소 비용 신장 트리를 만드는 알고리즘: Kruskal, Prim algorithm

신장트리를 만드는 제한 조건:

           그래프 내에 있는 간선들만을 사용

           정확하게 n-1개의 간선만을 사용

           사이클을 생성하는 간선 사용금지

<Kruskal Algorithm 1>

정의: 가중치가 높은 간선을 제거하면서 최소 비용 신장 트리를 만드는 방법

그래프 G의 모든 간선을 가중치에 따라 내림차순으로 정렬 -> 그래프 G에서 가중치가 가장 높은 간선 제거, disconnceted로 만드는 간선은 생략 -> 그래프에 간선이 n-1개만 남을 때까지 반복

<Kruskal Algorithm 2>

정의: 가중치가 낮은 간선을 삽입하면서 최소 비용 신장 트리를 만드는 방법

그래프 G의 모든 간선을 가중치에 따라 오름차순으로 정렬 -> 그래프 G에서 가중치가 가장 낮은 간선 삽입, 사이클을 형성하는 간선은 생략 -> 그래프에 간선이 n-1개가 삽입 될 때까지 반복

<Prim Algorighm>

정의: 간선을 정렬하지 않고 하나의 정점에서 시작하여 트리를 확장해나감

그래프 G의 시작 정점 선택 -> 선택한 정점에 부속된 모든 간선 중에서 가중치가 가장 낮은 간선을 연결하여 트리 확장 -> 이전에 선택한 정점과 새로 확장된 정점에 부속된 간선 중 가장 가중치가 낮은 간선 삽입, 단 사이클을 형성하는 간선은 생략 -> G에 n-1개 간선 삽입 될 때까지 반복

<<최단 경로 알고리즘>>

신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치 합이 최소인 경로

*Weight Adjacent Matrix

최단 경로를 구하려는 가중치 그래프의 가중치를 저장

간선 (i, j)가 그래프에 존재하면 M[i][j] = 가중치 값, 그래프에 존재하지 않으면 M[i][j] = 무한대

<Dijkstra Algorithm>

무방향, 방향 모두 적용 가능

가정 : 모든 간선은 음이 아닌 수

기능 : 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구한다

컨셉 : 시작 정점 v에서부터 정점 u까지 최단 경로 dist[u]를 구해 정점 u가 집합 S에 추가되면 새로 추가된 정점 u에 의해 단추고디는 경로가 있는지를 확인함, 현재 알고 있는 dist[w]와 새로 추가한 정점 u를 거쳐서 가는 dist[u] + cost[u][w]를 계산한 경로를 비교해 경로가 단축되면 dist[w]를 단축된 경로값으로 수정함으로써 최단경로를 찾음

<Bellman-Ford Algorithm>

그래프에서 정점 S에서 정점 G로 가는 최단경로?

특징 : 음수 비용을 허용하는 최단 경로 알고리즘

모든 vertax는 모든 간선에 대해서 relaxation 수행

<Floyd-Warshall Algorithm>

모든 정점의 쌍 u와 v간의 최단 경로를 구하는 알고리즘

모든 vertax에 대해 해당 vertax를 거쳐서 가는 최단경로를 구함

Tree Definition : 하나 이상의 노드로 이루어진 유한집합

           하나의 root node

           나머지 노드들은 n개의 분리 집합 T1, T2, … Tn으로 분할

특징 :

           원소들 간에 1:n 관계를 가지는 비선형 자료구조

           원소들 간에 계층 관계를 가지는 계층형 자료구조

           구성요소 : node, edge

<이진 트리>

모든 노드가 최대 2개의 서브트리를 갖는 트리

재귀적 구성

<완전 이진 트리>

레벨 1부터 k-1까지 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

* n개의 노드를 가진 완전 이진트리의 높이 = log(n+1)

이진트리의 표현

1.     배열

2.     연결리스트

이진트리의 순회

1.     중위순회(inorder traversal) -> 중위표기식 구할 수 있음

왼쪽 서브트리 방문, 루트 노드 방문, 오른쪽 서브트리 방문

2.     전위순회(preorder traversal) -> 전위표기식 구할 수 있음

루트 노드 방문, 왼쪽 서브트리 방문, 오른쪽 서브트리 방문

3.     후위순회(postorder traversal)-> 후위표기식 구할 수 있음

왼쪽 서브트리 방문, 오른쪽 서브트리 방문, 루트노드 방문

*일반트리를 이진트리로 변환

첫 번째 자식 노드 간선만 남기고 나머지 간선 제거 -> 형제 노드를 간선으로 연결

<ex: 수식트리 구현>

<<Priority Queue>>

우선수위를 근거로 dequeue 연산이 진행

구현방법 1. 배열 2. 연결리스트 3. 힙(Heap)

Heap을 이용할 시 O(logN)으로 삽입삭제 시간이 줄어듬

<Heap>

완전이진트리로 우선순위 개념을 큐에 도입한 자료구조

우선 순위가 높은 데이터가 먼저 나간다.

1.     Max Heap

2.     Min Heap

부모와 자식의 데이터 값 같은 경우 허용

<이진 탐색 트리>

탐색을 효율적으로 하기 위한 자료구조

특징 : 이진트리이며 모든 원소는 다른 유일한 key를 가짐

           왼쪽 서브트리의 key < 루트의 key < 오른쪽 서브트리의 key

삽입 : 탐색실패한 위치의 왼쪽 or 오른쪽에 삽입

삭제 : 삭제 노드 차수 0, 1, 2에 따라 case나눔

<일반 트리>

자식의 개수에 제한이 없는 트리