College‎ > ‎KNOU‎ > ‎3nd‎ > ‎1st Semester‎ > ‎

Algorithm

한국방송통신대학교 컴퓨터과학과 출석수업 수업자료

게시자: K.W. Shim, 2016. 5. 6. 오전 5:37   [ 2016. 5. 6. 오전 5:37에 업데이트됨 ]

알고리즘 과목홈페이지

게시자: K.W. Shim, 2016. 5. 6. 오전 5:37   [ 2016. 5. 6. 오전 5:37에 업데이트됨 ]

알고리즘 과목홈페이지

  • 과목명 : 알고리즘

  • 개요 : 멀티미디어 / 강의 / 출석수업시험 / 대체시험 / 기말시험 / 3 학년 1 학기 , 전공 , 3학점

개요
 
  • 개요 및 목표

    컴퓨터 알고리즘은 전산학의 핵심적인 과목 중의 하나이다. 적절한 자료구조와 적절한 알고리즘이 있어야 좋은 소프트웨어가 작성된다. 따라서 알고리즘에 관한 지식은 컴퓨터의 전 분야에서 기본적이면서도 필수적이다. 따라서 본 과목에서는 지금까지 많이 연구되어 좋은 알고리즘으로 제시된 중요한 정렬, 탐색, 그래프, 문자열 처리, 데이터 압축 등에 관한 알고리즘의 설계 및 분석 방법의 습득한다. 이러한 과정을 통해서 어떤 것이 좋은 알고리즘이고, 또 어떻게 하면 좋은 알고리즘을 만들 수 있는가에 대한 기본적인 능력을 배양한다. 수학적인 깊은 지식은 요구되지 않으나 체계적이고 논리적이며 분석적인 사고가 필요하므로 스스로 왜 그런지 생각하면서 공부할 필요가 있다. 

 
강의계획서
인쇄하기

1. 과목명 : 알고리즘

2. 서비스 일정 - 신규강의 : 학기 중 매주 월요일 추가 업데이트

3. 강의내용

가.강의매체 : 멀티미디어

시청은 학습하기의 학습을 클릭 하시고, 강의 파일을 다운 받고자 하는 경우는 다운로드의 버튼들을 클릭하여 주십시오.
강의
주차
강의주제세부내용학습하기다운로드쪽수담당
교수
동영상음성PDF
1알고리즘 소개      - 알고리즘 개념 및 기본 자료구조 - 알고리즘의 설계 및 분석 - 점근 성능 및 순환 알고리즘의 성능      학습하기
고화질2
저화질
다운
1~33이관용
2정렬 I      - 정렬 개념 - 선택 정렬, 버블 정렬 - 삽입 정렬, 쉘 정렬      학습하기
고화질2
저화질
다운
35~62이관용
3정렬 II      - 합병 정렬 - 퀵 정렬      학습하기
고화질2
저화질
다운
62~79이관용
4정렬 III      - 히프 정렬 - 선형시간 정렬(계수, 기수, 버킷)      학습하기
고화질2
저화질
다운
79~106이관용
5탐색 I      - 순차 탐색 - 이진 탐색 - 이진 탐색 나무      학습하기
고화질2
저화질
다운
107~119이관용
6탐색 II      - 균형 나무(2-3-4 나무, 흑적 나무) - 해싱      학습하기
고화질2
저화질
다운
119~144이관용
7그래프 I      - 개념과 용어 - 그래프 순회 - 위상 정렬, 그래프 연결성      학습하기
고화질2
저화질
다운
145~171이관용
8그래프 II      - 최소 신장 나무 (크루스칼 알고리즘, 프림 알고리즘) - 최단 경로 (데이크스트라, 플로이드)      학습하기
고화질2
저화질
다운
172~192이관용
9스트링 알고리즘 I      - 스트링 매칭 개념 및 기본 알고리즘 - 라빈-카프 알고리즘 - KMP 알고리즘      학습하기
고화질2
저화질
다운
193~206이관용
10스트링 알고리즘 II      - 스트링 매칭(보이어-무어 알고리즘) - 데이터 압축 알고리즘 (RLE, 허프만 코딩)      학습하기
고화질2
저화질
다운
207~223이관용
11스트링 알고리즘 III      - 데이터 압축 알고리즘 (LZ77, 이미지 압축, 동영상 압축)      학습하기
고화질2
저화질
다운
223~238이관용
12동적 프로그래밍      - 개념 - 행렬의 연쇄적 곱셈 - 스트링 편집 거리      학습하기
고화질2
저화질
다운
239~258이관용
13NP-완전 문제      - 개념 - 클래스 P, 클래스 NP - 변환, NP-완전성 - 근사 알고리즘      학습하기
고화질2
저화질
다운
259~275이관용
14병렬 알고리즘      - 개념 - 병렬 계산 모델 - 병렬 알고리즘의 성능 - 병렬 알고리즘의 예      학습하기
고화질2
저화질
다운
277~291이관용
15유전 알고리즘      - 개념 및 전형적인 처리 과정 - 유전 알고리즘의 연산자 - 유전 알고리즘의 매개변수      학습하기
고화질2
저화질
다운
293~314이관용

나. 출석수업

회차강의 주제세부내용교재쪽수담당교수강의실습
1

알고리즘 소개    

* 알고리즘 소개, 정의 및 조건 * 알고리즘 설계 방법과 다양성    

강의
2

알고리즘 분석    

* 알고리즘 분석 (정확성, 효율) * 점근성능과 표기법, 점화식    

강의
3

정렬 알고리즘 I    

* 기본 개념 * 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬    

강의
4

정렬 알고리즘 II  

* 합병 정렬 * 퀵 정렬  

강의
5

정렬 알고리즘 III  

* 히프 정렬 * 선형 시간 정렬 (계수, 기수, 버킷)  

강의
6

출석 수업 정리  

* 출석수업 내용에 대한 보충 설명 및 정리, 질의 응답  

강의

4. 평가방법 및 출제범위

평가유형평가방법출제범위비고
출석수업시험주관식    

각 지역대학(학습관)별로 출석 수업 후 시험일정을 각 지역대학(학습관)별로 출석 수업 후 시험일정을 정하고, 출석수업 담당교수가 직접 출제

     
유의사항
위의 내용은 변경 될 수 있으므로 공지사항 및 학보공고를 반드시 참고하시기 바랍니다.
출제범위가 표기되지 않은 시험유형은 아직 확정되지 않았습니다.

5. 참고문헌

[1] 조유근, 홍영식, 이지수, 김명, 알고리즘, 이한출판사, 2005 
[2] 이석호, 채진석, 알고리즘과 C++, 정익사, 2008
[3] 문병로, 쉽게 배우는 알고리즘: 관계중심의 사고법, 한빛미디어, 2007
[4] 정인정, 알고리즘, 홍릉과학출판사, 1999
[5] Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Ed., The MIT Press (번역서: 문병로, 심규석, 이충세 역, 한빛미디어, 2005)
[6] 박상현, (뇌를 자극하는)알고리즘, 한빛미디어, 2009

2강 - 정렬I_기본적인 방법

게시자: K.W. Shim, 2016. 5. 6. 오전 5:36   [ 2016. 5. 6. 오전 5:36에 업데이트됨 ]

학습개요
이번 강의부터 앞으로 3번의 강의에 걸쳐서 다양한 정렬 알고리즘에 대해서 학습한다.
이번 시간은 정렬의 첫 번째 강의로서 정렬의 기본 개념과 관련 용어를 우선 살펴보고, 정렬할 원소의 개수가 작을 때 간편하게 사용될 수 있는 간단하고 기본적인 비교 기반의 내부 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬에 대해서 살펴본다.

학습목표
1 정렬과 관련된 용어 및 기본 개념을 이해할 수 있다.
2 기본적인 내부 정렬 알고리즘의 수행 과정을
이해할 수 있다.
3 기본적인 정렬 알고리즘의 성능을 분석하고 장단점을
이해할 수 있다.


정렬 (sort)
여러 개의 원소로 구성된 리스트가 주어졌을 때, 이 원소들을 키값의 크기에 따라 오름차순/내림차순으로 재배열하는 것

내부 정렬 (internal sort)
정렬할 모든 데이터를 주기억장치에 저장한 후 정렬을 수행하는 방식
반면 외부 정렬은 모든 데이터를 주기억장치에 저장할 수 없는 경우 일부의 데이터만 주기억장치에 적재하고 나머지 데이터는 외부 기억장치에 저장한 채 정렬하는 방식이다.

비교 기반 정렬
데이터의 키값을 비교하면서 정렬하는 방식으로, 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 히프 정렬이 이에 속한다.
한편 분포 기반 정렬은 데이터의 분포 정보를 이용하는 정렬 방식으로 계수 정렬, 버킷 정렬, 기수 정렬이 있다.

안정적 정렬 (stable sort)
동일한 키값을 갖는 데이터 A와 B에 대하여 정렬 전의 상대적인 위치가 정렬 후에도 그대로 유지되는 정렬 방식

제자리 정렬 (in-place sort)
입력받은 데이터가 저장된 공간 이외의 별도 저장 공간을 상수개만 사용하는 정렬 방식


  • 다음 빈칸에 들어갈 말로 알맞은 것은?
  • 입력 배열 A의 데이터를 정렬하면서 입력 배열 이외의 별도 저장 공간으로 상수 개만을 사용하는
    정렬 알고리즘을 ( ㄱ ) 정렬 알고리즘이라고 하고, 동일한 키값를 갖는 데이터 쌍 A, B에 대하여
    정렬 전에 A가 B의 앞에 있었고 정렬 후에도 이 순서가 그대로 유지되는 것이 보장되는 정렬 알고리즘을 ( ㄴ ) (이)라고 한다.
  1. (ㄱ) 안정적 (ㄴ) 제자리
  2. (ㄱ) 안정적 (ㄴ) 무이동
  3. (ㄱ) 제자리 (ㄴ) 안정적
  4. (ㄱ) 제자리 (ㄴ) 무이동
  • 다음은 어떤 정렬 알고리즘에 의해 처리되는 과정을 나타낸 것이다. 사용한 알고리즘은 무엇인가?
    (단, 오름차순으로 정렬한다.) 

  •  
  1. 선택 정렬
  2. 삽입 정렬
  3. 버블 정렬
  4. 셸 정렬

  • 데이터를 오름차순으로 정렬할 경우 오른쪽부터 모든 인접한 두 키를 비교한 후 왼쪽의 키가 더 크면 오른쪽의 키와의 자리바꿈을 통하여 정렬해 나가는 방법은?
  1. 삽입 정렬
  2. 선택 정렬
  3. 버블 정렬
  4. 셸 정렬
  • 이미 제자리를 잡은 n개 데이터에 대하여 삽입 정렬을 수행할 때 걸리는 시간은?
  1. θ(1)
  2. θ(logn)
  3. θ(n)
  4. θ(nlogn)
  • 셸 정렬은 삽입 정렬의 어떠한 결점을 보완하기 위한 것인가?
  1. 정렬 후에 도착할 자리에 많이 벗어나 있어도 한 번에 한 자리씩만 접근한다.
  2. 두 개의 동일한 값을 가지는 키의 상대적 위치가 정렬 후에도 변한다.
  3. 입력과 동일한 크기의 추가적인 메모리가 필요하다.
  4. 키 값의 범위 내에서 키 값이 확률적으로 균등하게 분포해야 한다.
  • 버블 정렬을 적용하는 과정에서 한 단계의 수행 결과가 다음과 같을 때 다음 단계의 수행 결과는 어떻게 될까요?
    (단, 오름차순으로 정렬하고 밑줄 친 부분은 이미 정렬된 부분이라고 가정한다.)
  • 5 35 20 10 40 25 15 30


정리하기
  1. 정렬의 정의 및 관련 개념
    - 정렬 → 여러 원소로 구성된 리스트에 대해서 이 원소들을 키값의 크기 순서에 따라 재배치하는 것
    - 내부 정렬과 외부 정렬
      ▸내부 정렬 → 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
      ▸외부 정렬 → 모든 데이터를 주기억장치에 저장할 수 없어서 일부 데이터는 주기억장치에 있고 나머지 데이터는 보조기억장치에 저장된 채 정렬을 하는 방식
    - 비교 기반 정렬과 분포 기반 정렬
      ▸비교 기반 정렬 → 데이터의 키값을 비교하여 정렬하는 방식
              (선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 히프 정렬)
      ▸분포 기반 정렬 → 데이터의 분포 정보를 이용하여 정렬하는 방식 (계수 정렬, 버킷 정렬, 기수 정렬)
    - 안정적 정렬 → 동일한 키값을 갖는 데이터 A와 B에 대하여 정렬 전과 정렬 후의 A와 B의 상대적인 위치(앞뒤 관계)가 변하지 않는 정렬
    - 제자리 정렬 → 입력 배열 이외의 필요한 별도 저장 공간의 개수가 상수 개를 넘지 않는 정렬
  2. 선택 정렬
    - 정렬되지 않은 데이터 중에서 가장 작은 키값을 갖는 원소를 선택한 후, 이것을 미정렬 데이터의 첫 번째 원소와 교환하는 과정을 반복하여 정렬을 수행하는 방법
    - O(n2) - 최선/최악/평균의 경우, 불안정, 제자리
  3. 버블 정렬
    - 인접한 두 원소를 차례대로 비교하면서 (오름차순의 경우) 왼쪽 데이터의 키값이 오른쪽 데이터의 키값보다 큰 경우 자리바꿈을 통하여 정렬하는 방법
    - 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 실행 시간 O(n2)을 가짐
    - O(n2), 안정적, 제자리
  4. 삽입 정렬
    - 미정렬 부분의 첫 번째 원소를 하나씩 꺼내어 정렬된 부분에서 바른 위치에 삽입하여 나열하는 방법
    - 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 실행 시간 O(n2)을 가짐
    - O(n2), 안정적, 제자리
  5. 셸 정렬
    - 삽입 정렬의 단점(현재 삽입하고자 하는 키가 정렬 후에 도착할 자리에서 많이 벗어나 있어도 한 번에 한 자리씩만 이동하여 접근하는 문제)을 보완
    - 처음에는 멀리 떨어진 두 원소를 비교하여 위치를 교환하고 점차 가까운 위치의 원소를 비교/교환한 뒤 마지막에는 인접한 원소를 비교/교환하는 정렬 방식으로, 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 여러 번 거치도록 한 것
    - 간격의 크기, 즉 D의 계산 방식에 따라 다양한 성능을 보임
    - O(n2), 불안정적, 제자리
참고자료
  1. 조유근, 홍영식, 이지수, 김명, 알고리즘, 이한출판사, 2005
  2. 양성봉, 알기 쉬운 알고리즘, 생능출판사, 2013
  3. 이석호, 채진석, 알고리즘과 C++, 정익사, 2008
  4. 문병로, 쉽게 배우는 알고리즘: 관계중심의 사고법, 한빛미디어, 2007
  5. 정인정, 알고리즘, 홍릉과학출판사, 1999
  6. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Ed., The MIT Press
    (번역서: 문병로, 심규석, 이충세 역, 한빛미디어, 2005)

1장

게시자: K.W. Shim, 2016. 5. 6. 오전 5:36   [ 2016. 5. 6. 오전 5:36에 업데이트됨 ]


알고리즘이란?
an ordered set of unambiguous, executable steps that produces and terminates in a finite time

튜링기계에 의해 수행 가능한 프로시져 - 계산 이론 (computational theory)

- 0개 이상의 외부 입력과 1개 이상의 출력
- 모호하지 않고 단순 명확한 명령
- 한정된 수의 작업 후에는 반드시 종료
- 모든 명령은 수행 가능해야 한다. 
==> 주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령들을 순서적으로 구성한 것. 

알고리즘의 설계
- 상향식 설계
- 하향식 설계

알고리즘의 표현 / 기술
- 일상 언어, 순서도, 의사 코드, 프로그래밍 코드 등

알고리즘의 정확성 검증
- 수학적 검증
- 실용적 검증

효율성 분석
- 공간 복잡도
- 시간 복잡도

알고리즘 관점에서 자료구조의 특성
  • Array
    • 배열 내의 각 원소 접근시간이 동일하므로 원소들을 임의순서로 처리하는데 유리
    • 배열의 중간에서 삽입/삭제 할 경우 많은 시간이 소요
  • List
    • 상대적으로 삽입/삭제가 용이
    • 리스트 내의 특정 노드를 찾기 위해서 해당 노드의 앞에 위치한 모든 노드를 순차적으로 따라가야 한다.
  • Stack
    • 후입선출 (LIFO : Last In First Out)
  • Queue
    • 선입선출 (FIFO : First In First Out)
  • Tree
    • T의 원소 중에 단 하나의 root node가 존재
    • root 이외 나머지 node는 n개(n >= 0)의 서로 분리된 sub-tree(부분집합 : T1, T2, ..., Tn)로 나누어진다.
    • rooted-tree 
      • 나무의 정점 중 하나가 root로 지정된 것 ?
    • 뿌리가 r인 뿌리나무 T의 어떤 노드 x에 대하여 
      • 조상( ancestor )과 자손( descendant )
        • r로부터 x까지의 경로상에 존재하는 노드 y는 x의 조상이고, x는 y의 자손이다. 
      • 부분 나무 (subtree)
        • 뿌리 x와 x의 자손들로 이루어진 나무
      • 부모 (parent)
        • x의 바로 위쪽에 연결된 노드
      • 자식 (child)
        • x의 아래쪽에 연결된 노드
      • 동기 (sibling)
        • 부모가 같은 노드들
      • 잎 (leaf)
        • 자식이 없는 노드
    • 차수 (degree)
      • 뿌리 나무 T에서 노드 x의 자식의 개수
    • 깊이 (depth)
      • 뿌리 r에서 노드 x까지의 경로의 길이
    • 높이 (height)
      • 뿌리 나무 T에서 가장 큰 깊이
    • 수준 (level)
      • 깊이가 같은 노드들을 동일한 수준에 있는 노드들이라 함
    • 순서 나무 (ordered tree)
      • 노드의 각 자식에 순서가 부여된 뿌리 나무
    • 이진 나무 (binary tree)
      • 각 노드의 자식이 2개 이하인 순서 나무
      • 포화 이진 트리 (perfect)
      • 전 이진 트리 (full)
      • 완전 이진 트리 (complete)
      • 균형 이진 트리 (balanced)
  • Graph
    • G = (V, E)
      • V : 정점의 집합
      • E : 간선의 집합
    • 가중 그래프
    • 무방향 그래프
    • 방향 그래프
    • 주요 용어
      • 인접 (adjacent, incident)
      • 부분 그래프 (subgraph)
      • 경로 (path)
      • 경로의 길이 (length)
      • 차수 (degree)
        • 진입 차수 (in-degree)
        • 진출 차수 (out-degree)
      • 단순 경로 (simple path)
      • 사이클 (cycle)
      • 루프 (loop)
      • 연결 (connected)
      • 강력 연결 (strongly connected)
알고리즘의 설계
- 설계 방법은 다양하며, 일정한 틀을 제시하기 곤란하다
- 대표적인 설계 기법
  • 욕심쟁이 방법
    • greedy method
    • 해를 구하는 일련의 선택 과정마다 그 단계에서 '가장 최선'이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라고 희망적인 전략을 취하는 방법
      • 희망적 : 각 단계마다 선택한 최적해가 전체 최적해를 만들어 내지 못할 수 있음을 의미
    • 욕심쟁이 방법의 한계
      • 세상에서 가장 멋진 상의, 바지, 넥타이를 구입해도 욕심쟁이는 세상에서 으뜸이 안되는 것 => 해를 구할 수 없는 문제도 있다. 
      • 다만, 욕심쟁이 방법을 적용할 수 있다면 아주 간단하게 알고리즘을 만들 수 있다.
    • 거스름돈
      • 고객에게 돌려 줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 문제
        • 단순히 액면가가 큰 돈부터 최대한 뽑아서 제공
    • 배낭 문제
      • 최대 용량 M인 하나의 배낭과 각각 무게 Wi와 이익 Pi가 부여되어 있는 n개의 물체
      • 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되는 해를 찾는 내는 것 
      • M = 10, n = 4, (p1, p2, p3, p4) = (15, 20, 9, 14), (w1, w2, w3, w4) = (3, 5, 3, 4)
      • 각 물체의 가중치 (단위 무게당 이익)
        • (p1/w1, p2/w2, p3/w3, p4/w4) = (5, 4, 3, 3.5)
      • 물체를 쪼갤 수 있을 때 최대 이익 : w1 + w2 + w4 * 1/2 = 42
      • 물체를 쪼갤 수 없을 때 최대 이익 : w1 + w2 = 35 (단, 가중치보다 최대 이익에 치중 할 경우 w1 + w3 + w4 = 38 로 오히려 최대 이익이 더 높을 수 있다.)
    • 거스름돈 문제, 배낭 문제, 프림 알고리즘, 크루스칼 알고리즘, 데이크스트라 알고리즘
  • 분할 정복 방법
    • divide and conquer method
    • 순환적으로 문제를 푸는 방법
      • 분할 : 주어진 문제를 여러 개의 작은 문제로 분할
      • 정복 : 작은 문제들을 순환적으로 처리하여 정복. 만약 작은 문제의 크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해가 구해짐
      • 결합 : 작은 문제에 대해서 정복된 해를 결합하여 원래 문제의 해를 구함
    • 퀵 정렬, 합병 정렬, 이진 탐색
  • 동적 프로그래밍 방법
    • dynamic programming method

알고리즘 분석
  • 정확성 분석
    • 유효한 입력, 유한 시간, 정확한 결과 산출 여부
    • 실용적 vs 이론적
      • 실용적 : 테스트 데이터에 대한 디버깅 결과 -> 프로그램이 정확하다는 것을 증명하지 못함
      • 이론적 : 수학적 증명 -> 논리적으로 정확함을 보임
  • 효율 분석
    • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
    • 시간 복잡도 (time complexity)
      • 알고리즘이 필요로 하는 수행 시간의 크기
      • 알고리즘의 수행시간
        • 실제 실행 시간을 측정 -> 일반성 결여
        • 수행하는 기본 연산의 수행회수로 계산
      • 입력 크기의 함수로 표현
        • 입력 크기 : 입력되는 데이터의 크기
          • 문제가 해결하고자 하는 대상이 되는 개체의 개수
          • 행렬의 크기, 리스트 원소의 수, 그래프 정점의 수 등
      • 입력 상태에 종속적
        • 평균 수행 시간 A(n) =Σ IεSn p( I ) t ( I )
        • 최악 수행 시간 W(n) = max IεSn t ( I )
        • 최선 수행 시간 B(n) = min IεSn t ( I )
    • 순차 탐색의 수행 시간
      • 텍스트 상자

        SeqSearch(A, n, x)
        /* */
        1  {
        2      j = 1 ;                                          // C1                  1
        3      while ( j ≤ n && A( j ) != x )           // C2   k              n + 1
        4         j = j + 1 ;                                  // C3   k - 1         n
        5      return ( j ) ;                                  // C4                   1
        6  }                                                     //                        T(n) = 2n + 3

      • T(n) = 2n + 3 ------------> O(n)
      • c1 + c2 k + c3 (k - 1) + c4 = (c2 + c3) k + (c1 - c3 + c4) = ak + b ( 상수 x n + 상수 )
      • 평균 : k = n / 2
        • A(n) = a (n / 2) + b
      • 최악 : k = n
        • W(n) = a n + b
      • (상수 x n + 상수)
        • 하나의 상수항은 몇 개의 명령문들의 수행시간을 합쳐 놓은 것
        • 컴퓨터의 성능  / 종류에 종속적이므로 각 명령 마다 부여한 상이한 수행시간이 별 의미가 없다. 
        • 간단히 명령마다 동일한 시간 내에 처리된다고 가정해도 무방
      • 상수항보다 n의 차수가 더 중요
        • 상수 값을 무시하고 단지 입력 크기에 대한 차수만 고려 
          • 데이터의 개수가 많을 경우 알고리즘의 수행 시간이 보다 중요한 의미를 가짐
        • 이 경우 상수항이 아닌 n의 최고 차수에 좌우
          • 하위 차수는 무시
    • 공간 복잡도 (space complexity)
      • 알고리즘이 필요로 하는 메모리 공간의 크기 (정적 공간 + 동적 공간)
  • 점근 성능
    • 입력크기 n이 커질 때의 알고리즘의 성능
      • 입력의 크기 n이 커짐에 따라 상수항과 차수가 낮은 항들의 역할이 감소 -> n의 최고 차수에 의존
      • 실제로 알고리즘의 수행시간이 문제가 되는 것은 입력 크기가 커질 때이며 따라서 점근성능을 알고리즘의 시간복잡도로 쓰는 것이다. 
    • 표기법
      • Big-O (점근적 상한)
        •  n0인 모든 n에 대하여 f( n ) ≤ c ' g( n )을 만족하는 양의 상수 c, n0이 존재하면 f( n ) = O( g( n )) 이다.
      • Big-omega (점근적 하한)
        •  n0인 모든 n에 대하여 f( n ) ≥ c ' g( n )을 만족하는 양의 상수 c, n0이 존재하면 f( n ) =Ω ( g( n )) 이다.
      • Big-theta (점근적 상하한)
        •  n0인 모든 n에 대하여 c1 ' g( n ) ≤ f( n ) ≤ c2 ' g( n )을 만족하는 양의 상수 c1, c2, n0이 존재하면, 즉 f( n ) =Ω ( g( n )) = O( g( n )) 이면 f( n ) =Θ( g( n )) 이다.
    • f( n ) = 3n + 3, g( n ) = n
      •  n0인 모든 n에 대하여 f( n ) ≤ c g( n )을 만족하는 양의 상수 c, n0이 존재하면 f( n ) = O(g(n))이다
      • (c = 5, n0 = 2 일때) n  2에 대해서 3n + 3 ≤ 5n -> f( n ) =  O( g( n )) = O( n )
      • (c = 3, n0 = 1 일때) n  1에 대해서 3n + 3  3n -> f( n ) =  Ω ( g( n )) = Ω ( n )
      • f( n ) = O( n ) and f( n ) = Ω ( n ) -> f( n ) = Θ( n )
    • f( n ) = 3 n***3(n의 3승) + 3n - 1, g( n ) = n***3 (n의 3승)
      • (c = 7, n0 = 1 일때)  n  1에 대해서 3 n***3 + 3n - 1  ≤  7n -> f( n ) = O( n***3 )
      • (c = 2, n0 = 2 일때)  n  3에 대해서 n***3 + 3n - 1    2n -> f( n ) = Ωn***3 )
      • f( n ) = O( n***3 ) and f( n ) = Ωn***3 ) -> f( n ) = Θ( n***3 )
    • f( n ) = 2 n***3 + 3 n**2 - n + 10, g( n ) = n***3
      • (c = 5, n0 = 5 일때) n > 5에 대해서 2n***3 + 3n**2 - n + 10 ≤ 5 n***3 -> f( n ) = O( n***3 )
        • (2 x 5***3 + 3 x 5**2 - 5 + 10) ≤ (5 x 5***3)
        • 336 = ((2 x 125) + 75 + 5)           625 = (5 x 125)
      • (c = 2, n0 = 3 일때) n > 3에 대해서 2n***3 + 3n**2 - n + 10 ≥ 2 n***3 -> f( n ) =  Ωn***3 )
        • (2 x 3***3 + 3 x 3**2 - 5+ 10) ≤ (2 x 3***3)
        • 91 = ((2 x 27) + 27 + 5)            54 = (2 x 27)
      • f( n ) = 

1강 - 알고리즘 소개

게시자: K.W. Shim, 2016. 5. 6. 오전 5:35   [ 2016. 5. 6. 오전 5:35에 업데이트됨 ]

학습개요
이번 강의에서는 우선 알고리즘의 정의와 특성을 살펴보고, 앞으로 다룰 다양한 알고리즘을 이해하는 데 필요한 기본적인 자료구조를 소개한다. 그리고 알고리즘의 주요 설계기법과 알고리즘을 분석하는 방법에 대해서 중점적으로 학습한다

학습목표
알고리즘의 중요성과 개념을 이해할 수 있다.
2 알고리즘 학습에 필요한 기본적인 자료구조의 개념,용어 및 특징을 이해할 수 있다.
3 알고리즘의 대표적인 설계 기법의 종류와 특성을 이해할 수 있다.
4 알고리즘의 시간 복잡도 개념과 다양한 점근 성능의표기법을 이해할 수 있다.
5 순환의 중요성 및 기본 점화식의 의미와 폐쇄형을 이해할 수 있다.

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

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

분할정복 방법 (divide and conquer method)
순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 단계를 거친다.

동적 프로그래밍 방법 (dynamic programming method)
주어진 문제를 여러 개의 부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블(표)에 저장해 놓고 이를 이용하여 입력 크기가 더 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법

거스름돈 문제
가게에 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제 (욕심쟁이 방법과 유사)

배낭 문제 (knapsack problem)
배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾아내는 문제 
0/1 배낭 문제: 배낭에 넣는 물체를 쪼갤 수 없다는 가정이 있는 배낭 문제로서, 이 경우에는 욕심쟁이 방법으로 해결할 수 없는 NP-완전문제가 된다.

시간 복잡도 (time complexity)
알고리즘을 실행시켜 완료하는 데 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 횟수를 모두 계산하여 나타낸다.

점근 성능 (asymptotic performance)
입력의 크기 n이 충분히 커질 때의 알고리즘의 성능
표기법:
점근적 상한 f(n) = O(g(n),
점근적 하한 f(n)=Ω(g(n)),
점근적 상하한 f(n)=Θ(g(n))

점화식 (recurrence equation)
함수의 한 값이 자신을 포함한 수식으로 다시 표현된 식을 의미하며, 순환 알고리즘의 수행시간을 나타내기 위한 방법으로 사용된다.

  • 알고리즘에 대한 설명으로 적절하지 못한 것은?
  1. 모든 명령은 컴퓨터에서 수행 가능해야 하며 효율적이어야 한다.
  2. 각 단계는 단순하고 명료해야 한다.
  3. 일정한 단계의 명령을 수행한 후에는 반드시 종료해야 한다.
  4. 외부 입력이 반드시 존재해서 하나 이상의 출력을 생성한다.
  • 이진 트리에 대한 설명으로 잘못된 것은?
  1. n개의 노드를 갖는 어떠한 이진 트리의 높이도 완전 이진 트리의 높이보다는 크거나 같다.
  2. 전 이진 트리는 모든 노드의 차수가 0이거나 2인 이진 트리이다.
  3. 높이가 h인 포화 이진 트리에서는 잎이 아닌 노드가 잎 노드보다 많다.
  4. n개의 노드를 가진 완전 이진 트리의 높이는 정확히 이다. 
  • 다음 빈칸에 들어갈 알맞은 용어는 무엇인가?
  • 그래프에서 정점 v1에서 vn까지의 (        )라는 것은 간선으로 연결된 정점들의 순차열 v1, v2, ⋯, vn이다.
  1. 차수
  2. 길이
  3. 경로
  4. 깊이
  • 욕심쟁이 방법에 대한 설명으로 적절한 것은?
  1. 분할, 정복, 결합 단계로 이루어진다.
  2. 각 단계에서 선택한 최적해들이 전체적인 최적해를 구성한다.
  3. 모든 가능한 해 공간을 만들고 이들에 대한 평가함수의 값으로부터 구한다.
  4. 주어진 문제를 소문제로 분할하고 이 소문제들의 해 중에서 적절한 것을 택하여 원 문제의 해를 구한다.
  • f(n)=2n3+3n2-n+10이라고 하고 g(n)=n3이라고 하자.
    n>3에 대하여 f(n)≥2g(n)이므로 f(n)은 다음 중 어떤 식으로 표현될 수 있는가?
  1. f(n)=O(n3)
  2. f(n)=Ω(n3)
  3. f(n)=Θ(n3)
  4. f(n)=o(n3)
  • 알고리즘의 시간 복잡도를 점화식으로 표현하였을 때 가장 효율적인 알고리즘에 해당하는 것은?
  1. T(n) = 2T(n/2)+Θ(n), T(1)=Θ(1)
  2. T(n) = T(n-1)+Θ(n), T(1)=Θ(1)
  3. T(n) = T(n/2)+Θ(1), T(1)=Θ(1)
  4. T(n) = T(n/2)+Θ(n), T(1)=Θ(1)
  • 다음과 같은 조건의 배낭 문제에 대해 욕심쟁이 방법으로 해를 구하려고 한다.
    배낭에 넣은 물체들의 최대 이익은 얼마인가? (단, 물체를 쪼갤 수 있다고 가정, M: 배낭의 용량, n: 물체의 개수, 각 물체(Xi)의 무게 wi와 그 물체의 이익 pi)
  • M=10, n=4
    (p1, p2, p3, p4)=(18, 15, 12, 25), (w1, w2, w3, w4)=(3, 5, 3, 4)


  • 다음과 같은 알고리즘의 시간 복잡도를 빅오 표기로 나타내시오.
  • void Sort (int A[], int n) {
      int i, j;
      for (i=0; i<n-1; i++)
        for (j=1; j<n; j++)
           if (A[j-1] > A[j] )
             Swap(&A[j-1], &A[j]);
    }
     
정리하기
  1. 컴퓨터 알고리즘이란?
    - 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것
    - 알고리즘의 조건 → 입출력, 명확성, 유한성, 유효성
  2. 기본적인 자료구조
    - 선형 구조 → 배열, 연결리스트, 큐, 스택
    - 비선형 구조 → 트리, 그래프
  3. 알고리즘의 설계 방법
    - 주어진 문제와 조건 등이 매우 다양하므로 알고리즘의 일반적인 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.
  4. 욕심쟁이 방법
    - 해를 구하는 일련의 선택 과정마다 그 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면, 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다. 여기서 ‘희망적’이라는 표현은 욕심쟁이 방법을 적용해도 최적해를 구할 수 없는 경우도 존재한다는 것을 의미한다.
    - 욕심쟁이 방법이 적용 가능한 문제
      ▸거스름돈 문제 → 가게에 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
      ▸배낭 문제 → 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 배낭에 넣은 방법을 찾는 문제로서 물체를 쪼갤 수 있다고 가정한다. 물체를 쪼갤 수 없는 0/1 배낭 문제는 욕심쟁이 방법으로 해결할 수 없다.
      ▸교재 4장(그래프) → 프림 알고리즘, 크루스칼 알고리즘, 데이크스트라 알고리즘
  5. 분할정복 방법
    - 순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 세 단계를 거친다.
    - 적용 가능한 문제 → 퀵 정렬(교재 2장), 합병 정렬(교재 2장), 이진 탐색(교재 3장) 등
  6. 동적 프로그래밍 방법
    - 주어진 문제를 여러 개의 부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고 이를 이용하여 입력 크기가 더 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법이다.
    - 적용 가능한 문제 → 플로이드 알고리즘(교재 4장), 교재 6장
  7. 알고리즘 분석은 두 가지 측면에서 수행
    - 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 산출하는지를 판단한다.
    - 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 즉 소요되는 메모리 공간의 크기(“공간 복잡도”)와
            수행에 걸리는 시간(“시간 복잡도”)을 추정한다.
  8. 알고리즘의 수행 시간
    - 수행 시간 = 각 연산의 수행 횟수의 합
    - 수행 시간은 일반적으로 입력 크기(입력되는 데이터의 크기) n의 함수로 표현
    - 데이터의 입력 상태에 따라 수행 시간은 달라진다.
    - 알고리즘의 우열을 따질 경우에는 알고리즘의 수행 시간을 나타내는 식의 성장률 또는 차수만을 따지는 것이 일반적이며, 따라서 입력 크기 n의 최고 차수만을 따지며 하위 차수와 상수는 모두 무시한다.
  9. 점근 성능
    - 입력의 크기 n이 충분히 커질 때 알고리즘의 수행 시간이 무엇에 의해 좌우되는가를 나타내는 것
     → 수행 시간이 다항식으로 표현되는 경우에는 입력의 크기가 커짐에 따라 상수항과 차수가 낮은 항들의 역할이 감소하게 되고, 결국 n의 최고차항에 좌우된다.
    - 표기법 → ① “Big-oh” 점근적 상한 f(n) = O(g(n),
           ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)),
           ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))
    - 시간 복잡도 함수 간의 크기 관계
      → O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!)
  10. 기본 점화식의 종류와 폐쇄형
    ► T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
    ► T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2)
    ► T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn)
    ► T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)
    ► T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)
    ► T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn)  

참고자료
  1. 조유근, 홍영식, 이지수, 김명, 알고리즘, 이한출판사, 2005
  2. 양성봉, 알기 쉬운 알고리즘, 생능출판사, 2013
  3. 이석호, 채진석, 알고리즘과 C++, 정익사, 2008
  4. 문병로, 쉽게 배우는 알고리즘: 관계중심의 사고법, 한빛미디어, 2007
  5. 정인정, 알고리즘, 홍릉과학출판사, 1999
  6. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Ed., The MIT Press
    (번역서: 문병로, 심규석, 이충세 역, 한빛미디어, 2005)

1-5 of 5