알고리즘

개념
어떠한 문제를 해결하기 위한 일련의 생각의 흐름 Algorithm is an effective method expressed as a finite list of well defined instructions for calculating a function

I. 자료구조와 알고리즘의 개요

   가.  알고리즘의 정의

    - 어떠한 문제를 해결하기 위한 일련의 생각의 흐름

- Algorithm is an effective method expressed as a finite list of well defined instructions for calculating a function.

 

나.  알고리즘의 조건

조건

설명

입출력

 0개 이상의 외부 입력 / 1개 이상의 출력

명확성

 각 명령어는 모호하지 않고 의미가 명확해야 함

유한성

 알고리즘은 수행 뒤에 반드시 종료

유효성

 모든 명령들은 오류가 없이 실행 가능해야 함

효율성

 충분히 큰 입력에 대하여 알고리즘의 수행 시간은 크게 차이가 발생하기 때문에 효율적으로 수행되어야 함

- 프로그램은 유한성이 만족되지 않아도 된다는 측면에서 알고리즘과 프로그램이 구별됨

 

다.  알고리즘의 선택 기준

기준

설명

정확성

 알고리즘에서의 입력데이터와 수행 후 기대되는 출력에 대해 정확히 이해/일반적으로 수학적 귀납법 이용 증명

효율성

 알고리즘의 수행에 소요되는 컴퓨터 자원의 양 (기억장치 의 소요량과 수행시간)을 의미

 프로그램의 효율성을 높이기 위한 튜닝 작업은 시스템을 구현한 후에 이루어져야 함

 수행시간의 80% 이상을 코드의 20% 이하 부분에서 소비 한다는 현상

적합성

 목표 시스템의 하드웨어와 소프트웨어에 적합을 의미

 

라.  알고리즘의 생성 절차

    알고리즘 설계 -> 표현 -> 정확성 검증 -> 효율성 분석

 

 

 

II. 자료구조와 알고리즘의 유형

가.  알고리즘의 유형

  • 정렬 알고리즘

  • 탐색 알고리즘

 

 

III. 알고리즘 설계기법

  가. 알고리즘 설계 목표

- 알고리즘은 궁극적으로 컴퓨터에서 수행하는 것을 목표로 하므로 실용성이 있어야 하고 효율성도 필요

- 입출력, 명확성, 유한성, 효과성을 만족하는 알고리즘이 존재하면 그 문제가 해결 가능함

   

   나. 대표적인 설계 기법

기법

설명

예제

욕심쟁이 방법

(greedy method)

 해를 구하는 일련의 선택 과정마다 그 단계에서 최선이라고 볼 수 있는 선택을 행해나가면 결과적으로 전체적인 최적해를 구할 수 있을거 라는 희망적인 전략을 취하는 방법

 최적의 해를 구한다는 보장을 못함

 크루스칼, 다익스트라 알고리즘 / 허프만 트리

분할과 정복 방법

(divide and conquer method)

 문제를 더 이상 나눌 수 없을 때까지 나누고, 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 방법

 문제를 쪼개는 요령이나 규칙은 없음

 병합정렬 / 거듭제곱

동적 프로그래밍 방법

(dynamic programming method)

 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어질 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법

 소문제에 대한 여러 최적해로부터 다음 크기의 소문제에 대한 최적해가 결정

 피보나치 수 / LCS알고리즘

백트래킹

(back tracking)

 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘

 목적 : "진짜 해"를 효율적으로 찾는 것

 N-Queen 알고리즘

 

 

IV. 알고리즘 표현방법

구분

내용

흐름도

 장점 : 명령의 흐름을 쉽게 파악

 단점 : 복잡한 알고리즘을 나타내기에는 역부족

 EMB0000019c0030

프로그램 설계언어

 프로그래밍 언어를 사용하여 알고리즘을 표현하는 방법

 장점 : 알고리즘 자체가 실제로 구체화된 구현이므로 추가적인 구체화 작업이 필요 없음

 단점 : 알고리즘을 번역하고 필요한 다른 프로그래밍 언어로 변환해야 하는 작업이 필요

의사코드

(pseudo-code)

 프로그래밍 언어의 형태를 갖춘 의사코드(pseudo-code)를 사용하여 알고리즘을 표현하는 방법

 장점 : 원하는 특정 프로그래밍 언어로 변환 (구체화 작업) 하기가 쉬움

 단점 : 특정 프로그래밍 언어가 아니기 때문에 직접 실행할 수는 없음

 

V. 알고리즘 평가 방법

   가. 알고리즘의 성능을 가리는 5가지 측정기준

  • 정확성 : 알고리즘이 정확하게 동작하는가
  • 작업량 : 얼마나 적은 연산을 수행하는가
  • 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
  • 단순성 : 얼마나 단순한가
  • 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가

 

   나. 정확성 평가

  • 수학적 : 알고리즘이 예상대로 수행되는지 수학적 증명 수행
  • 실용적 : 테스트 데이터에 의한 디버깅을 통해 정확성 평가

 

다. 효율성 평가

구분

설명

시간 복잡도

(Time Complexity)

 입력크기의 값에 대하여, 단위연산을 몇 번 수행 하는지를 계산함으로써, 알고리즘의 수행시간 평가

 프로그램의 컴파일 시간과 실행 시간의 합

 3가지 점근적 표현법

O - 빅오      Ω - 오메가  Θ - 세타

공간 복잡도

(Space Complexity)

 알고리즘 수행에 필요한 메모리의 양을 평가

 필요한 고정 공간과 가변 공간의 합

 

 

 

VI. 알고리즘의 점근 표기법과 복잡도

가.  점근 표기법

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

(1) Big O : 어떤 최악의 상황에서도 성능을 보장

(2) Big Omega : 아무리 좋은 케이스라도 그 성능 이상을 낼 수 없음

(3) Big Theta : 알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 표현

  • Big O 표기법으로 표현한 알고리즘의 성능 간 그래프

 

나.  복잡도

구분

내용

시간 복잡도

문제를 해결하는 시간과 입력의 함수 관계

공간 복잡도

문제를 해결하기 위해 필요한 저장 공간과 함수 관계

 

댓글