1 - (3,4) 추상 자료형과 알고리즘의 성능 분석 (작성中)

1 - 3. 추상 자료형

추상화란?

 소프트웨어 개발과 유지보수에 있어서 가장 중요한 문제는 "어떻게 소프트웨어 시스템의 복잡성을 관리할 것인가"이다. 이러한 복잡성에 대처하기 위한 새로운 아이디어들이 등장하였고 이들을 구체화한 프로그래밍 방법론과 언어들이 개발되었다. 이러한 방법론이나 언어의 핵심이 추상화(abstraction)이다.

 추상화 = 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념이나 기능을 간추려 내는 것.

 

 즉, 어떤 시스템의 간략화 된 기술 또는 명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것이다. 좋은 추상화는 사용자에게 중요한 정보는 강조되고 반면 중요하지 않은 구현 세부 사항은 제거되는 것이다. 이를 위하여 정보은닉기법(information hiding)이 개발되었고 추상 자료형의 개념으로 발전되었다.

추상 자료형이란?

 추상 자료형(Abstract Data Type: ADT)은 추상화한 자료형, 즉 추상적으로 정의한 자료형을 의미한다. 구체적으로는 자료의 집합과 자료에 가해지는 연산들의 집합에 대한 수학적인 명세이다. 이러한 추상 자료형은 그 자료형의 구현으로부터 분리된 자료형을 의미하는데, 자료나 연산이 무엇(what)인가는 정의되지만 이들을 컴퓨터에서 어떤 프로그래밍 언어를 이용해 어떻게(how) 구현할 것인지는 정의하지 않는다.

 예를 들어 자연수를 생각해보자. 자연수는 일반적으로 컴퓨터에서 기본적으로 제공하지 않는 자료형이다. 자연수를 추상 자료형으로 정의해보면 다음과 같다.

Natural_Number(자연수에 대한 추상 자료형)

 객체 = 1에서 시작하여 INT_MAX까지의 순서화된 정수의 부분 범위

 연산 ·add(x,y) = x+y가 INT_MAX보다 크면 INT_MAX를 반환하고 아니면 x+y를 반환한다.

  ·distance(x,y) = x가 y보다 크면 x-y를 반환하고 작으면 y-x를 반환한다.

  ·equal(x,y) = x와y가 같은 값이면 TRUE를 반환하고 아니면 FALSE를 반환한다.

  ·successor(x) = x가 INT_MAX보다 작으면 x+1을 반환한다.

 추상 자료형을 표현할 때는 먼저 객체를 정의하고, 다음으로 연산들을 정의한다. 객체는 주로 집합의 개념을 사용하여 표현하고, 연산의 정의에는 연산의 이름, 매개변수, 연산의 결과, 연산이 수행하는 기능 등을 기술한다.

 추상 자료형을 컴퓨터 프로그램으로 구현할 때는 보통 구현에 관한 세부사항들은 외부에서 모르게 하고 외부에는 간단한 인터페이스(Interface)만들 공개한다. 사용자는 공개된 인터페이스만 사용하고 이것이 어떻게 구현되었는지를 알 필요가 없다. 추후에 구현 방법이 변경될 수 있지만, 인터페이스만 정확하게 지켜진다면 사용자는 변경된 내용알 알 수도 없고 사용하는데도 전혀 문제가 없다. 이것이 정보은닉의 기본 개념이다. 즉 "구현으로부터 명세의 분리"가 추상 자료형의 중심 아이디어이다.

추상 자료형과 C++

 추상 자료형은 실제로 사용하는 프로그래밍 언어에 따라 여러 가지 방법으로 구현될 수 있다. C언어에서는 주로 구조체를 사용해서 완벽하지는 않지만 구현할 수 있다. 추상 자료형의 이론은 C++나 Java와 같은 최근의 객체지향 프로그램 언어에 큰 영향을 주었다. 추상 자료형과 C++의 관계를 살펴보자.

·추상 자료형의 개념은 객체지향의 개념과 정확히 일치한다.

·객체지향언어인 C++에서는 클래스를 사용하여 추상 자료형을 구현한다.

·추상 자료형에서의 "객체"는 클래스의 속성(멤버 변수)으로 구현되고 "연산"은 클래스의 메소드(멤버 함수)로 구현된다.

·C++에서는 private나 protected키워드를 이용하여 속성과 연산에 대한 접근을 제한할 수 있다.

·클래스는 계층구조(상속)로 구성될 수 있다.

 앞으로의 포스팅에서는 여러 가지 자료구조를 C++를 이용하여 설명할 것입니다.

1 - 4.알고리즘의 성능 분석

 요즘의 컴퓨터는 예전에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 또한 계속해서 발전하고 있다. 그렇다면 프로그램 작성 시에 계산시간을 줄이고 메모리를 효과적으로 사용하기 위해 더 이상 고민하지 않아도 되는 것일까? 물론 정답은 "아니다"이다.

 그 이유는 무엇일까? 우선 첫 번째 이유는 "컴퓨터가 발전함에 따라 프로그램의 규모도 엄청나게 커지고 있다"는 것이다. 처리해야 할 자료의 양이 많아질수록 알고리즘의 효율성이 더욱 중요해진다. 예를 들어, 동일한 작업을 하는 두 개의 프로그램 A와 B가 있다고 생각할 때, 입력 자료가 n개이며 A와 B의 실행 시간은 각각 n^2과 2^n에 비례하여 커진다고 가정하면, n=6일 때 A와 B의 실행 시간은 36초와 64초로 채 1분이 차이나지 않지만, 입력 자료가 100개로 늘어나면 10000초와 10^22년으로 엄청난 차이가 난다.

 두 번째 이유는 사용자들이 "당연하게도" 빠른 프로그램을 선호하기 때문이다. 예를 들어, 두 개의 실시간 대전 게임이 있다고 했을 때, A게임은 스토리는 별로이지만 게임의 반응이 빠르고, B게임은 스토리는 탄탄하여 영화를 방불케 하지만, 사용자가 펀치 버튼을 누른 뒤 3초 뒤에 펀치가 나간다면 대부분의 사람들은 A게임을 선택할 것이다. 따라서 프로그램 개발자는 하드웨어와 상관 없이 최선의 효율성을 갖는 알고리즘을 개발하도록 노력하여야 할 것이다.

 효율적인 알고리즘이란 전체 실행 시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘이다. 일반적으로 실행 시간이 메모리 공간보다 더 중요하게 생각되기 때문에 알고리즘의 실행 시간을 효율적인 알고리즘의 기준으로 삼는다.

실행 시간 측정 방법

 그렇다면 어떻게 프로그램의 효율성을 측정할 수 있을까? 가장 단순하지만 확실한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제로 컴퓨터에서 실행시킨 다음, 그 실행 시간을 측정하는 것이다. 동일한 작업을 하는 2개의 서로 다른 알고리즘 A와 B가 있다고 가정하자. 동일한 컴퓨터와 동일한 컴파일러를 사용하여 구현하였을 때 알고리즘A는 10초가 걸렸고 알고리즘 B는 50초가 걸렸다고 한다면 알고리즘 A가 더 효율적인 알고리즘이라고 말할 수 있다. 따라서 알고리즘을 구현하여 실행 시간을 측정하는 방법은 대단히 정확하고 확실한 방법이다.

 컴퓨터에서 실행 시간을 측정하는 방법에는 주로 clock() 함수가 이용된다. 이 함수는 호출외었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환하는데, 반환형은 clock_t형이다. 아래 프로그램은 실행 시간을 측정하는 전형적인 프르로그램이다.

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <ctime>

void main()

{

clock_t start, finish;

double duration;

start = clock();

//실행 시간을 측정하고자 하는코드...

//...

finish = clock();

duration = (double)(finish - start) / CLOCKS_PER_SEC;

std::cout<<duration<<"초입니다."<<std::endl;

}

 이 방법으로 두 개의 서로 다른 알고리즘의 성능을 비교하는 데는 몇 가지의 문제가 있다.

 ·당연한 이야기겠지만 이 두 알고리즘을 반드시 "구현"해야 한다. 알고리즘이 비교적 단순한 경우에는 쉽게 구현할 수 있지만 복잡한 알고리즘의 경우에는 구현이 큰 부담이 될 수 있다.

 ·2개의 알고리즘을 반드시 동일한 조건의 하드웨어를 사용하여 실행 시간을 측정하여야 한다. 아주 비효율적인 알고리즘도 슈퍼컴퓨터 상에서 실행하면 가장 효율적인 알고리즘을 스마트폰에서 실행하는 것보다 더 빠른 시간에 치리될 수 있기 때문이다.

 ·사용한 소프트웨어 환경도 동일해야 한다. 예를 들어, 알고리즘의 구현에 사용된 프로그래밍 언어에 따라서도 실행 속도가 크게 달라질 수 있다. 보통 C나 C++와 같은 컴파일 방식 언어를 사용한 경우가 파이썬(python)이나 베이직과 같이 명령어를 직접 실행하는 인터프리트 방식 언어보다 빠르다.

 ·성능 비교에 사용했던 데이터가 아닌 다른 데이터에 대해서는 다른 결과가 나올 수 있어 실험되지 않은 입력에 대해서는 실행 시간을 주장할 수 없다.

 이와 같은 여라 가지 문제점 때문에 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법이 개발되었다.

알고리즘의 복잡도 분석 방법

 알고리즘을 직접 구현하지 않고서도 대략적인 효율성을 분석할 수 있는데, 이것을 알고리즘 복잡도 분석(complexity analysis)이라 한다. 이 방법은 구현하지 않고도 모든 입력을 고려하는 방법을 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

 알고리즘 분석에서는 먼저 "좋다"는 의미를 분명히 해야 한다. 좋은 알고리즘은 실행 시간이 빠르고 처리를 위해 필요한 기억 공간이 적은 알고리즘이다. 알고리즘의 실행 시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도(space complexity)라고 한다. 우리가 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 말한다. 그 이유는 알고리즘이 사용하는 메모리 공간보다는 실행 시간에 관심이 더 많기 때문이다.

시간 복잡도 함수

 시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한다. 연산에는 산술 연산, 대입 연산, 비교 연산, 이동 연산 등이 모두 포함되는데, 복잡도 분석에 이들 연산의 실행횟수를 사용한다.

 만약 동일한 조건에서 동일한 일은 하는데 알고리즘 A는 20번의 연산이 필요하고 알고리즘 B는 100번의 연산이 필요하다면 알고리즘 A가 알고리즘 B에 비해 더 효율적이라고 할 수 있다. 이것이 시간복잡도 분석의 기본 개념이다.

 어떤 알고리즘을 실행하는데 필요한 연산의 수는 보통 주어지는 입력의 개수 n에 영향을 받는다. 이와 같이 연산의 수를  n의 함수로 나타낸 것을 시간 복잡도 함수라 하고 T(n)이라고 표기한다.

 양의 정수 n의 제곱, 즉 n^2을 구한느 문제에 대한 몇 가지 알고리즘을 생각해보자. 시간 복잡도 설명을 위해 좀 다양한 방법을 생각하면 다음과 같이 세 가지 알고리즘이 있다.

·알고리즘 A = 곱셈 연산을 이용해 n과 n을 곱하는 (n*n)방법

·알고리즘 B = 덧셈 연산을 이용해 n을 n번 더하는 방법

·알고리즘 C = 덧셈 연산을 이용해 1을 n*n번 더하는 방법

 이 알고리즘을 유사 코드로 나타내면 다음과 같다.

알고리즘 A	알고리즘 B	알고리즘 C
sum ← n*n;	for i←1 to n do    sum ← sum + n;	for i←1 to n do    for j←1 to n do       sum ← sum+1;

 이제 이들 알고리즘을 구현하지 않고 분석 기법을 사용하여 수행 속도를 예측하여 보자. 여기서 입력의 개수 또는 문제의 크기는 n으로 볼 수 있다. 연산의 횟수를 세어보자. 단, 여기서는 간단한 분석을 위해 루프를 제어하는 연산들은 제외시켰다. 보통 이들은 알고리즘의 복잡도에 크게 영향을 끼치지 않는다.

 사실 덧셈 연산보다는 곱셈 연산에 더 많은 시간이 걸릴 것이다. 그러나 모든 연산에 동일한 시간이 걸린다고 가정하고 알고리즘들을 비교한다. 하나의 연산이 t만큼의 시간이 걸린다고 하면 A는 2t에 비례하는 시간이 필요하고 알고리즘 B는 2nt의 시간이, 알고리즘 C는 2(n^2)t만큼의 시간이 걸린다. 이들 연산들의 개수를 그래프로 그리면 아래와 같다. n이 커질수록 알고리즘간의 연산 양의 차이가 커지는 것을 알 수 있으며, 따라서 우리는 가장 효율적인 알고리즘이 무엇인지 판단할 수 있다.

	알고리즘 A	알고리즘 B	알고리즘 C
대입 연산	1	n	n*n
덧셈 연산		n	n*n
곱셈 연산	1
전체 연산수	2	2n	2n^2

빅오 표기법

 일반적으로 시간 복잡도 함수 T(n)은 입력의 개수 n에 대한 상당히 복잡한 수식으로 나타낳 수 있다. 그러나 자료의 개수가 많아질수록, 즉 n이 커질수록 T(n)에서 차수가 가장 큰 항의 영향이 절대적이 되고 다른 항들은 무시될 수 있을 정도로 작아진다.

 예를 들면, 시간 복잡도 함수 T(n) = n^2 + n + 1을 생각해보자.

·n=1일 때 : T(n) = 1 + 1 + 1 = 3 (n^2항이 33.3%)

·n=10일 때 : T(n) = 100 + 10 + 1 = 111 (n^2항이 90%)

·n=100일 때 : T(n) = 10000 + 100 + 1 = 10101 (n^2항이 99%)

 T(n)의 최고차항의 영향이 n의 증가에 따라 점점 커져서 n=100일 때는 전체의 약 99%가 되는 것을 알 수 있다. 이것은 시간 복잡도 분석에서는 함수의 전체 항이 아니라 최고차항만을 고려하면 될 것임을 짐작하게 한다.

 결국 시간 복잡도 함수에서 중요한 것은 n에 대해 연산이 몇 번 필요한가가 아니라 n이 증가함에 따라 무엇에 비례하는 수의 연산이 필요한가이다. 예를 들어, 위 그래프에서 알고리즘 A는 n에 상관 없이 동일한 수의 연산만 있으면 되고, 알고리즘 B는 n에 비례하는 연산이 필요하며, 알고리즘 C는 n^2에 비례하는 연산이 필요하다는 것이 중요하다.

 이와 같이 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다. 즉, 알고리즘이 n에 비례하는 실행 시간을 가진다고 말하는 대신에 알고리즘 A의 시간 복잡도가 O(n)이라고 한다. O(n)은 "빅오 of n"이라고 읽는다. 빅오 표기법은 n의 값에 따른 함수의 상한값을 나타내는 방법이다. 빅오 표기법은 수학적으로는

 두 개의 함수과이 주어졌을 때 모든 에 대해 을 만족하는 상수 와가 존재하면 이다.

 앞의 그래프에서 값은 n이 매우 커지게 되면 결국은 보다 작거나 같게 된다. 따라서 이 정의는 이 의 상한값이라는 것을 의미한다. 여기서 어떤 수와에 대해서는 아무런 언급이 없음을 주의하라.  나는 아무런 제한 없이 결정될 수 있다. 보통 위의 부등식을 만족하는  나는 무수히 많을 수 있다. 예를 들어, 이이고 이 이라면 일 때 부등식이라 말할 수 있다.

※이 게시물은 생능출판사의 "C++로 쉽게 풀어쓴 자료구조"책을 바탕으로 작성되었습니다. 이 게시글에 자료로 들어간 사진이나 글의 대부분은 생능출판사의 소유이며, 문제가 될 시 삭제하겠습니다.※

※이 게시물은 2018년 7월 26일 18:57까지 작성된 게시글이며, 아직 완성된 포스팅이 아닙니다. 앞으로 내용이 더 추가될 계획입니다.※

태클은 언제나 환영입니다. 잘못된 내용이 있다면 알려주세요!