알고리즘 - 2016 출석수업 자료 및 예상문제

1. 알고리즘이 무엇인지 •요건에 대해 서술하시오

주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것

입출력

0개 이상의 외부 입력

1개 이상의 출력

모호하지 않고 단순 명확한 명령

한정된 수의 작업 후에는 반드시 종료

모든 명령은 수행 가능해야 함

(실용적 관점) 효율적이어야 함

주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것이 알고리즘이다

 

2. 전이진, 포화이진, 완전이진 트리 개념, 샘플예제를 그리시오

☞전 이진 트리(full binary tree)는 단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리이다.

☞포화이진 트리(perfect binary tree)는 모든 단말 노드의 깊이가 같은 전 이진트리이다.

포화이진 트리의 노드의 개수는 이다.

☞완전이진 트리(complete binary tree)는 포화이진 트리에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다. 포화이진 트리의 각 노드에 부모에서 자식으로, 왼쪽에서 오른쪽으로 번호를 매겼을 때 포화이진 트리는 아니지만 그 번호가 연속되어 있는 경우 완전이진 트리가 된다.

완전이진 트리의 노드의 개수는에서 

사이의 값을 가진다.

아래는 이진트리의 기초이며 알아두면 좋아요 참고 하세요^^

☞포화이진 트리의 노드의 개수는 이다.

☞포화이진 트리의 노드의 개수는 또한로 나타낼 수 있다.

☞포화이진 트리의 단말 노드의 개수는이다.

☞완전이진 트리의 노드의 개수는 에서사이의 값을 가진다.

☞방향 간선(directed edge)은 부모에서 자식으로 가는 경로를 가리킨다.

☞루트 노드(root node)는 부모가 없는 노드이다. 

☞트리는 하나의 루트 노드만을 가진다.(최상위노드)

☞단말 노드(leaf node)는 자식이 없는 노드이다.

☞각 노드의 깊이(depth)는 루트 노드에서 자신까지 가는 경로의 길이이다.

☞트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부르기도 한다. 

☞루트 노드의 깊이는 0이다.

☞트리의 높이(height)는 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이이다. 루트 노드만 있는 트리의 높이는 0이다.

☞형제(sibiling)는 같은 부모를 가지는 노드이다.

☞노드의 크기(size)는 자신을 포함한 모든 자손 노드의 개수이다.

☞노드의 진입차수(In-degree)는 노드에 들어오는 모든 간선의 수이다.

☞노드의 진출차수(Out-degree)는 노드에서 나가는 모든 간선의 수이다.

☞루트를 가진 트리(rooted binary tree)는 모든 노드의 자식이 최대 2개인 루트를 가진 트리(rooted tree)이다.

☞포화이진 트리(perfect binary tree)는 모든 단말 노드의 깊이가 같은 전 이진트리이다.

☞완전이진 트리(complete binary tree)는 포화이진 트리에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다. 포화이진 트리의 각 노드에 부모에서 자식으로, 왼쪽에서 오른쪽으로 번호를 매겼을 때 포화이진 트리는 아니지만 그 번호가 연속되어 있는 경우 완전이진 트리가 된다.

☞균형이진 트리(balanced binary tree)는 모든 단말 노드의 깊이 차이가 많아야 1인 트리이다. 균형 이진 트리는 예측 가능한 깊이(predictable depth)를 가진다.

3. 욕심쟁이 방법 설명, 조건 이익 최대이익 계산

욕심쟁이 방법  해를 구하는 일련의 선택 과정마다 그 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적 해를 구할 수 있을 것이라고 희망적인 전략을 취하는 방법

희망적  각 단계마다 선택한 최적해가 전체 최적 해를 만들어 내지 못할 수 있음을 의미

멋쟁이씨가 세상에서 가장 멋진 넥타이, 가장 멋진 바지, 가장 멋진 재킷을 입는다고 할 때, 그렇다면 그런 옷을 입은 멋쟁이씨는 세상에서 가장 멋쟁이라고 할 수 있는가?

욕심쟁이 방법으로 해를 구할 수 없는 문제도 많다.

 

☞배낭문제

최대 용량 M인 하나의 배낭과 각각 무게 와 이익 가 부여되어 있는 n개의 물체가 있다고 가정

☆배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 집어넣는 방법을 찾아내는 것

☆물체를 쪼갤 수 있다고 가정

[배낭 : M=10 n=4]

[소시지: ] [감: ][빵: ] [생선: ]

M = 10, n = 4

( ) = (15, 20, 9, 14)

( ) = (3, 5, 3, 4)

▷각 물체의 가중치 (단위 무게당 이익)

 (5, 4, 3, 3.5)

 

▷최대 이익

최대이익 = X  =42

 

▷물체를 쪼갤 수 없는 경우  욕심쟁이 방법 적용 불가

M = 10, n = 4

( ) = (15, 20, 9, 14)

( ) = (3, 5, 3, 4)

▷각 물체의 가중치 (단위 무게당 이익)

 (5, 4, 3, 3.5)

 

▷최대 이익

최대이익 =  =35

실제 최대이익 =  =38

4. 어떤 알고리즘이 효율적인지와 그 이유를 설명하시오

효율성 분석

알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정

공간 복잡도 space complexity

•메모리 양 (= 정적 공간 + 동적 공간)

시간 복잡도 time complexity

•수행시간

 

 

수행시간에 영향을 미치는 요인

컴퓨터의 속도

사용하는 프로그래밍 언어

프로그램 작성 방법

컴파일러의 효율성

 

알고리즘의 수행시간 = Σ{각 문장(연산)의 수행 회수}

입력의 크기

입력 데이터의 상태

 

 

입력 크기의 함수로 표현

 입력 크기 : 입력되는 데이터의 크기

• 문제가 해결하고자 하는 대상이 되는 개체의 개수

• 행렬의 크기, 리스트 원소의 수, 그래프의 정점의 수 등

 

입력 데이터의 상태에 종속

 평균 수행 시간 

 최선 수행 시간 

 최악 수행 시간 

Sn : 크기가 n인 입력들의 집합

P(I) : 입력 I가 발생할 확률

t(I) : 입력 I일 때 알고리즘의 수행시간

O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)＜O(2n)＜O(n!)

⇦효율적 비효율적⇨

 

 

 

 

 

알고리즘의 시간 복잡도를 구하려면

알고리즘의 수행시간 f(n)을 구한 후 f(n)=O(g(n))을 만족하는 최소의 g(n)을 찾음

실용적인 접근 방법

•알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함

•g(n)은 최고 차수에 의존

5. 쉘 정렬 인터벌 값이 적혀 있는 것을 보고 정렬 할 것

Donald L. Shell  삽입 정렬의 단점 보완

현재 삽입하고자 하는 키가 정렬 후에 도착핛 자리에서 맋이 벗어나 있어도 핚 번에 핚 자리씩맊 이동하여 접근

멀리 떨어진 원소를 교환하여 속도 향상을 꾀함

•처음에는 멀리 떨어진 두 원소를 비교하여 위치를 교환하고 점차 가까운 위치의 원소를 비교/교환핚 뒤 마지막에는 인접핚 원소를 비교/교환하는 정렬 방식

6. 퀵 정렬

퀵 정렬의 원리

특정 원소를 기준으로 주어진 원소들을 두 부분배열로 나눈 뒤, 각 부분배열에 독립적으로 퀵 정렬을 순환적으로 적용하여 정렬하는 방식

피벗(분할 원소)

두 부분배열로 분할할 때 기준이 되는 원소

보통 주어진 원소 중 가장 왼쪽의 원소로 선택

피벗이 제 위치를 잡도록 하여 정렬하는 방식

 

왼쪽 부분배열의 모든 키값 < 오른쪽 부분배열에서 가장 작은 키값

왼쪽 부분배열의 가장 큰 키값 < 오른쪽 부분배열의 모든 킷값

 

 

 

7. 히프정렬 (최댓값에서 최종 그래프 단계 서술 그리기)

히프정렬

히프(heap) 자료구조의 장점을 이용한 정렬

최대값 삭제, 임의의 값을 삽입하는 연산을 수월하게 하는 히프의 특징을 이용한 정렬

(최대값)히프

완전 이진 나무(Complete binary tree)

각 노드의 값은 자식 노드의 값보다 크거나 같아야 함 (“최댓값 히프”) ⇔ 최솟값 히프

 

 

8. 이진탐색트리 노드 삭제 방법 그리기

 

삭제 연산 _계속(1)

3가지 경우 (삭제되는 노드의 자식의 개수에 따라)

 

1. 자식이 없는 경우 (리프 노드의 경우)

남은 노드의 위치 조절이 불필요

2. 자식이 하나만 있는 경우

자식 노드를 삭제되는 노드의 위치로 올리면서 부분 트리 전체도 따라 올린다.

3. 자식이 두 개 모두 있는 경우

① successor 노드를 삭제되는 노드의 위치로 올린다.

② successor 노드의 자식 노드를 successor 노드의 위치로 올리면서 그 부분 트리 전체도 따라 올린다.

 

삭제 연산의 다른 예

3가지 경우 (삭제할 노드를 x로 가정)

1. x의 오른쪽 자식이 없는 경우

x->r == NULL

2. x의 오른쪽 자식은 있으나, 오른쪽 자식의 왼쪽 자식은 없는 경우

x->r != NULL, x->r->l == NULL

3. x의 오른쪽 자식도 있고, 오른쪽 자식의 왼쪽 자식도 있는 경우

오른쪽 부분 나무에서 가장 작은 값을 찾아서 x 대체

이진 탐색 트리의 성능과 문제점

탐색 시간

키를 비교하는 횟수에 비례

평균 탐색 시간

키 30, 55, 15, 44, 22, 88, 7을 순서대로 삽입하면

최악의 경우

키 7, 15, 22, 35, 44, 55, 88을 순서대로 삽입하면

 

 

 

9. 2-3-4트리 삽입방법

 

2-3-4 트리란?

균형 탐색 트리

2-노드: 1개의 키와 2개의 자식으로 구성

3-노드: 2개의 키와 3개의 자식으로 구성

4-노드: 3개의 키와 4개의 자식으로 구성

각 노드의 한 키의 왼쪽 부분 트리에 있는 모든 노드의 키값은 그 키값보다 작다.

각 노드의 한 키의 오른쪽 부분 트리에 있는 모든 노드의 키값은 그 키값보다 크다.

모든 리프 노드의 높이는 동일

이진 탐색 트리  2-3-4 트리에서 2-노드로만 구성된 트리

삽입 연산

탐색 과정에 4-노드를 만나게 되면 항상 노드 분할이 발생

노드 분할

 

 

2-3-4 트리의 성능

n개의 노드로 구성된 2-3-4 트리

트리의 최대 높이 logn

탐색 시간  O(logn)

2-3-4 트리를 그대로 구현하면 노드 구조가 복잡

이진 탐색 트리보다 더 느려질 가능성이 많음