알고리즘 (1)

알고리즘 개요

컴퓨터 알고리즘이란?

주어진 문제를 해결하기 위해 잘 정의된 동작들의 유한집합

 

문제 해결 능력과 알고리즘 설계 능력을 향상 시키고 프로그래밍에서의  효율성을 높이는 방법을 공부

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

알고리즘이 좋고 나쁘고는 성능이 결정 짓는데 이 성능은 시간인 경우가 많다

 

알고리즘 표현 방법

순서도(flow chart)

- 알고리즘을 그림으로 표현한 것 (알고리즘을 약속된 기호로 표현하는 것)

플로우 차트의 구성

sequence (순차진행) decision(if문 결정문) repetition (반복문, 여기서 대부분의 시간을 소비)

장점: 알고리즘을 이해하기 쉽다

단점: 알고리즘을 표현하는 시간과 비용이 많이 든다

 

의사코드(pseudo-code)

알고리즘을 영어 또는 한글과 같은 사람이 사용하는 자연어로 표현하는 것

C-like (pseudo code (alog.)) C언어로 작성되는 수도코드

장점: 알고리즘을 표현하는데 시간이 적게 걸린다

단점: 가독성이 떨어진다 (알고리즘을 이해하기 어려운 경우가 발생)

 

알고리즘 분석 방법: 경험적 분석과 수학적 분석

경험적 분석

- 알고리즘을 프로그래밍 언어로 구현을 한 뒤에 이를 실행시켜 보아 실행 시간을 비교해 보는 것

장점: 직접 돌려보기 때문에 신빙성 있는 자료를 제공하며 수학적인 지식이 필요없다

단점: 실제 프로그램으로 구현해야 성능 평가를 할 수 있기 때문에 시간이 많이 소요된다

 

수학적 분석

- 알고리즘 자체만을 가지고 수학적 모델링 기법을 이용하여 분석을 하는 것

장점: 프로그래밍 과정에서 같은 알고리즘이더라도 프로그래머의 능력에 따라 나타날 수 있는 성능의 펀차를 없앨 수 있다

단점: 수학적 모델링을 잘 할 수 있는 숙련된 전문가가 필요함

 

일반적인 알고리즘 설계 방법

<무작위(randomized) 알고리즘>

- 난수의 (random number) 통계적 특성을 이용

 

< 분할 정복(divide-and-conquer) 알고리즘>

- 분할(divide), 정복(conquer), 결합(combine)의 과정을 거침

- 큰 문제를 하위 문제로 나누어 나중에 재결합 (일반적으로 1/2로 계속 나누면서 진행, 가장 성능이 좋음)

예: 합병정렬, 퀵정렬

 

알고리즘의 우수함을 가리는 기준

1. 정확성 : 정확하게 동작하는가?

2. 작업량: 얼마나 작은 연산을 수행하는가?

3. 메모리 사용량: 얼마나 적은 메모리를 사용하는가?

4. 단순성: 얼마나 단순한가?

5. 최적성: 개선의 여지가 없을 정도로 최적한가?

 

최악의 경우 성능 분석: O(n)

평균의 경우 성능 분석: Theta(n)

최상의 경우 성능 분석: Omega(n)

 

점근 표기법(asymptotic notation)

알고리즘의 수행시간을 대략적으로 나타내는 방법

최고차항으로만 알고리즘의 성능을 대략적으로 표시하여(즉 단순화하여) 알고리즘 간의 성능 비교에 용이함

 

<동적 프로그래밍>

 

<욕심쟁이 알고리즘>

 

<근사 알고리즘>

 

<완전 탐색>

Brute Force

 

리스트(list)

링크드리스트(linked list)

- 순서화된 데이터를 표현하는 가장 간단한 자료 구조

- 데이터를 노드로 구성된 연결 리스트로 표현

- 알고리즘을 표현하는데 있어서 가장 많이 사용하는 자료구조

장점: 데이터 삽입, 삭제하는데 유연성이 있다/ 동적인 메모리 할당으로 크기를 자유롭게 조절 가능하다

단점: n값이 클 경우 데이터를 찾을 때 배열 보다 속도가 느리다

array: 기억장치 이웃하는 공간에 할당, 성능이 빠르다 (n값이 아주 작을 때)

linked list: 기억장치 빈 공간에 할당, array에 비하면 성능이 느림

double linked list: 기억장치 빈 공간에 할당, 양방향 링크를 통해서 데이터 검색이 빠름 (공간낭비 발생?)

링크드 리스트의 마지막 노드는 NULL 이나 -1을 가리킨다

 

tail 포인터가 있을 때

1. 추가 할 노드를 newnode로 둔다

2. tail포인터를 찾는다

3. tail -> nextnode(link) = * newnode;

4. newnode -> nexnode(link) = -1;

5. tail = newnode;

O(1)

malloc() 동적 메모리 할당

mfree() 메모리 공간 비워내기

 

링크드리스트 추가

ptr node -> link = newnode;

newnode -> link = -1;

 

링크드리스트 삭제

삭제하고자 하는 노드가 발견될 때까지 루프

삭제할 노드가 발견되면 (ptr) ptr - 1을 해서 전 노드로 감

pre node -> link = ptr node -> link;

ptr -> link = -1; ptr -> data = 0;

 

링크드리스트 삽입

삽입하고자 하는 노드가 발견될 때까지 루프

발견

ptr -> link = newnode;

newnode -> link = ptr -> link;

O(n)

 

노드 개수 세기

count = 0 (항상 clear 되있다고 가정은 하지만 하는게 좋음)

current = head;

current = current -> nextnode;

count ++;

링크드 리스트의 마지막이 될 때까지 루프를 수행

 

double linked list

기본개념: 한 방향이 아닌 양방향으로 연결이 된 선형 자료 구조

장점: 알고리즘의 가용성(신뢰성)을 높일 수 있다 (한쪽이 끊어져도 한쪽이 남아 있어서 비교적 튼튼?)

단점: 메모리 공간낭비가 발생

 

스택(Stack)

스택은 알고리즘 구현에 있어서 자주 사용되는 자료구조

처음에 들어간 것이 가장 마지막에 나오도록 설계되어 있는 구조

- FILO(First In Last Out) 또는 LIFO(Last In First Out)

한쪽이 막혀있는 자료구조, 막혀 있지 않은 다른 쪽에서 삽입과 제거가 이루어짐

 

스택의 주요 기능: 삽입과 제거 (push and pop)

스택의 꼭대기: top (SP)

스택의 bottom: 보통 NULL(-1)로 표현

삽입 연산(Push)

- 스택의 최상위(top)에 데이터를 추가하는 연산

현재 top 위치에 데이터를 insert하고

top(sp) = top(sp) + 1

삭제 연산(pop)

현재 top 위치에 데이터를 delete하고

top(sp) = top(sp) - 1

 

스택의 응용분야

- 함수가 호출될 때마다 스택에 해당 함수의 정보를 추가하고 함수가 종료되면 해당 정보를 제거

- 트리 등을 구현할 때도 사용 가능

- 간단하면서도 유용한 자료 구조이며 알고리즘 문제 해결의 핵심 자료 구조

 

inorder 표기법을 postorder로 변환하는 과정

inorder 수식 입력이 없을 때 까지 아래 과정을 수행 (O(n))

(1) ( 만나면 스택에 삽입 (push)

(2) 숫자를 만나면 출력

(3) 연산자를 만나면 스택에서 현재 연산자보다 우선순위가 같거나 높은 연산자를 모두 출력하고 현재 연산자를 스택에 삽입 (즉 +, - 를 만나면 *, / 를 출력 우선순위가 같은 +, -도 출력해야 함)

(4) ) 만나면 스택 내에 있는 것을 모두 pop 후 출력 ( ()는 출력 안함)

(5) 이러한 과정을 더 이상 데이터가 없을 때까지 반복

 

스택의 성능 평가

- 스택은 일반적으로 빠른 성능을 보장

- 스택에서 데이터를 추가하거나 삭제하는 경우, 이 작업은 상수 시간 O(1) 내에 수행

 

스택의 구현 방법에 따라 성능이 달라지는데

- 배열을 사용하여 스택을 구현할 수 있고 (데이터가 적을 경우)

- 연결리스트를 사용하여 스택을 구현할 수도 있음 (일반적이며 데이터가 비교적 많을 경우)

 

큐(Queue)

먼저 들어간 데이터가 먼저 나오는 구조

FIFO(First In First Out) 선입선출

enqueue: 큐의 rear에서 데이터 삽입 (rear = rear + 1)

dequeue: 큐의 front에서 데이터 삭제 (front = front - 1)

 

순환 큐

- 실제로 데이터를 옮기는 대신 (너무 많은 이동이 필요) 전단과 후단의 위치만 관리

(문제점1) 데이터 삽입/제거가 몇번 수행되고 나면 전단과 후단이 모두 뒤로 후퇴하여 큐를 더 이상 사용할 수 없게 됨

(해결책1) 배열의 끝과 시작이 이어진 것처럼 전단과 후단을 관리

(문제점2) 전단과 후단이 같은 위치에 있을 때 가득찬 경우(full)와 비어 있는 경우(empty)를 구분하지 못함

(해결책2) 실제 용량 보다 1만큼 더 크게 여유공간을 생성

그러면 empty인 경우엔 front = rear, full인 경우엔 front = rear + 1

 

트리(tree)

나무를 닮은 자료구조

트리의 예: 회사의 조직 체계, 가계도, 폴더 구조

알고리즘에서 트리를 주로 사용하는 경우

- 운영체제에서 파일 시스템

- HTML이나 XML 문서를 다룰 때 사용하는 DOM

(일반적으로 데이터의 개수가 많을 때 주로 사용)

 

구성 요소: root node, branch node, leaf node

parent > 현재 노드의 부모 노드

children > 현재 노드의 자식 노드들

sibling > 현재 노드의 형제 노드

 

path: B, D, F를 B에서 F까지의 경로라 함

- 경로의 길이를 가짐 : B, D, F는 2

경로 길이는 가능한 짧게 해야 함

depth: root 노드에서 해당 노드 까지의 경로 길이

- 자주 사용하는 데이터는 가능하면 depth가 0에 가까운 쪽으로 배치

A깊이 0, B,G, I 깊이 1

level: 깊이가 같은 노드의 집합

tree depth: 루트 - 가장 밑의 leaf node 까지

degree: 어떤 노드의 자식의 개수 (가능한 작게 해야함)

 

트리 표현 방법: 중첩된 괄호, 중첩된 집합

단점: 이해하기 어렵다

 

linked list로 표현 (N-Link 표현법)

문제점: link field 공간 낭비가 심해짐 (특히 leaf node에서, 그리고 고정 N개라서 유연성이 없음)

(해결책) 왼쪽 자식-오른쪽 형제 표현방법 (binary tree로 변환)

sibling node 끼리 전부 연결 후 parent node와의 연결은 삭제

(단 맨 왼쪽 chid node의 parent link는 유지)

(문제점) binary tree의 노드가 한쪽으로 치우치는(skewed) 현상