추상 자료형과 알고리즘 정의

▶ 추상 자료형(Abstract Data Type)

 

자료형을 정의하기 전에 자료형에 대한 특징과 연산자를 논리적으로 추상화하여 정의한 자료형입니다.

자료형이란 처리할 자료의 집합이나 자료를 수행할 연산자의 집합입니다.

예) 같은 사물이라도 어떻게 쓰는냐에 따라 용도가 달라질 수 있다.

      추상화 : 지갑

      구체화 : 장지갑, 동전지갑, 카드지갑

 

 

▶ 알고리즘

 

문제 해결을 위한 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서입니다.

예) 음식을 만들 때

     요리의 재료를 컴퓨터에서는 자료,

     그 요리에 들어가는 재료를 다루는 방법을 자료의 연산,

     요리를 만드는 과정을 적은 명세서를 알고리즘이라고 한다.

 

 

▶ 알고리즘이 필요한 이유!

 

주어진 문제를 효과적이고 정확하게 문제를 해결하기 위해 자료를 정의하고 그에 적합한 알고리즘을 작성해야 합니다.

 

 

▶ 알고리즘의 조건

 

1. 입력(Input) : 자료를 토대로 작성될 알고리즘은 외부에서 입력으로 제공될 수 있어야 한다.

 

2. 출력(Output) : 알고리즘이 수행되었을 경우 하나 이상의 결과를 출력해야 한다.

 

3. 명확성(Definiteness) : 수행될 알고리즘의 명령어들은 명확하게 명세되어야 한다.

 

4. 유한성(Finiteness) : 알고리즘을 수행이 완료된 후 반드시 종료되어야 한다.

 

5. 효과성(Effectiveness) : 수행될 알고리즘의 명령어들은 모두 기본적이고 실행이 가능해야 한다.

 

 

▶ 알고리즘의 표현 방법

 

1. 자연어 : 알고리즘을 사람이 사용하는 언어로 표현하는 방법.

                  단점 : 사용하는 사람에 따라 일관성이나 명확성을 유지하기 어려움. => 누구나 이해할 수 있는

                            알고리즘을 표현하는데 한계가 있음.

 

2. 순서도를 이용한 도식화 : 알고리즘을 순서도를 작성하는 규칙에 따라 도식화하는 방법.

                                             단점 : 복잡한 알고리즘을 표현하는데 한계가 있음.

 

3. 프로그래밍 언어를 이용한 구체화 : 알고리즘을 프로그램언어를 사용하여 표현하는 방법.

                                                             단점 : 해당 언어를 모르면 이해하기 어려움. => 알고리즘은 번역하고                                                                         다른 프로그래밍으로 변환해야하므로 비효율적.

 

4. 가상코드를 이용한 추상화 : 알고리즘을 프로그래밍 언어로 표현할 때 생기는 단점을 보완하는 방법.

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

 

 

▶  알고리즘 성능 분석 기준

 

1. 정확성 : 자료를 입력했을 때 일정한 시간 내에 올바른 결과값을 출력하는지에 대한 여부.

 

2. 명확성 : 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는지를 판단.

 

3. 수행량 : 기본적인 연산은 제외하고 알고리즘 특성을 나타내는 중요 연산을 모두 분석.

 

4. 메모리 사용량 : 명령어, 변수, 입출력 자료와 정보를 저장하기 위해 사용하는 메모리.

 

5. 최적성 : 가장 좋은 알고리즘은 최적의 알고리즘이라 할 수 있음.

 

 

▶ 알고리즘 성능 분석 방법

 

1. 공간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료되기까지 소모되는 총 저장 공간의 양.

                          공간 복잡도 = 고정 공간 + 가변 공간

                          - 고정공간 : 프로그램의 크기나 입출력 회수와 상관없이 고정적으로 필요한 저장 공간.

                          - 가변공간 : 프로그램 실행과정에서 사용되는 자료와 변수, 함수를 저장하는 공간.

 

2. 시간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료되기까지 소모되는 총 소요시간.

                          시간 복잡도 = 컴파일 시간 + 실행 시간

                           - 컴파일 시간 : 프로그램마다 거의 고정적인 시간 소요.

                           - 실행 시간 : 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행 시간 보다는 명령문의

                                               실행 빈도수에 따라 계산.

                           - 실행 빈도수 계산 : 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의                                                             없어 하나의 단위시간을 갖는 기본 명령문으로 취급

  2.1) 성능 분석 표기법

    ● 빅 - 오 표기법 : O(f(n))으로 표기. "Big Oh of f(n)"으로 읽음. 함수의 상한을 나타내기 위한 표기법.

                                먼저 실행 빈도수를 구하여 실행 시간 함수 f(n)을 찾고, 이 함수값에 가장 큰 영향을 주는

                                 n에 대한 항을 한 개 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시.

    ● 빅 - 오메가 표기법 : Ω(f(n))으로 표기. "Big Omega of f(n)"으로 읽음. 함수의 하한을 나타내기 위한

                                       표기법.

    ● 빅 - 세타 표기법 : θ(f(n))으로 표기. "Big Theta of f(n)"으로 읽음. 상한과 하한이 같은 정확한 차수를

                                   표현하기 위한 표기법. f(n) = θ(g(n))이 되려면 f(n) = O(g(n))이면서 f(n) = Ω(g(n))

                                   이어야 함

    => 시간 복잡도를 정확히 계산할 수 있다면 빅 - 세타 표기법 사용.

         시간 복잡도를 정확히 분석하기 어렵다면 상한을 구하여 빅 - 오 표기법을 사용하거나 하한을 구하여

         빅 - 오메가 표기법을 사용.

         일반적으로 최악의 경우를 고려한 해결책을 찾기 때문에 빅 - 오 표기법을 주로 사용.

 

    시간 복잡도에 따른 알고리즘 수행 시간 비교표

출처 : https://jundol.me/126