자료구조의 중요성 혹은 필요성을 건물 건축의 비유를 통해 살펴보자.
좌측과 같이 장난감집을 만들때는 머리속의 계획만으로도 건물을 짓는데 큰 상관이 없고 심각한 문제가 발생할 경우라도 걱정할 필요가
없다.(투입된 재료등의 비용이 높지 않아서) 하지만 우측과 같은 크고 고급스러운 집을 만든다면 머리속의 계획만으로는 건축할 수 없을 것이다.
자료구조는 컴퓨터 프로그래밍에 잇어서 가장 기초적인 학문분야로 인식 되고 있다. 높은 건물을 짓기 전에 필요한 기초 공사와 마찬가지로
컴퓨터 프로그램이 효율적이고 안전하게 동작하기 위해서 반드시 필요한 프로그램의 기본 골격에 해당한다고 볼 수 있다.
자료구조는 컴퓨터 프로그램을 구현하기 위해 연구된 것.
하나의 프로그램이 정상적으로 동작하려면, 내부적으로 자료(데이터)를 저장하고 있을 뿐 아니라 이러한 자료를 처리하기 위한 명령어들의 집합을
가지고 있어야 된다.(위 그림) 위 그림은 하나의 프로그램이 자료(data)를 처리하기 위한 명령의 집합으로 구성되어 있을을 보여준다.
여기서 자료구조는 컴퓨터에 자료를 효율적으로 저장하는 방식을 말한다.(정의)
효율적인 자료구조는 컴퓨터의 메모리를 절약할 뿐만 아니라 프로그램 수행 시간을 최소화 하는 기능 수행 – 반대로 비효율적인 자료 구조는
불필요한 저장 공간필요와 느려짐
컴퓨터 명령 자체의 효율성을 증가 시키기 위한 절차(방법)를 보통 알고리즘이라 하고 효율적인 알고리즘이 가능하기 위해서는 먼저 효율적인
자료 구조가 선행 되어야 한다.
프로그램에서 자료를 저장하는 자료를 그 형태에 따라 분류하면 크게 단순구조, 선형구조, 비선형구조, 파일구조 로 나눌수 있다.
단순구조 – 정수, 실수, 문자, 문자열 같이 프로그래밍 언어에서 제공하는 기본적인 데이터 타입 (일반적인 자료구조라 하면 단순구조보다는
단순구조를 활용하여 만든 선형, 비선형 구조를 말한다)
선형 구조는 각각의 자료들 사이의 앞뒤 관계가 1:1인 경우를 말하며 리스트, 스택, 큐, 덱 등이 대표적이다. 선형 구조는 저장된 자료들
사이의 관계가 다음 그림과 같이 선형으로 연결되어 있다.
2. Non - Linear
비선형구조는 각각의 자료들 사이의 앞뒤 관계가 1:1이 아닌 계층 구조 혹은 망 구조를 가지는 경우를 말하며 트리와 그래프 등이
대표적이다. (1:2 OR 2:1관계)
파일 구조는 보조기억장치(하드)에 저장되는 파일에 대한 자료 구조를 말한다. 선형, 비선형 자료구조가 컴퓨터 메모리상에 저장된다는 가정에
의한 것이라면 파일 구조는 메모리가 아닌 디스크에 저장된다는 가정에 기반을 둔 것으로, 주로 메모리에 한 번에 올릴수 없는 대용량 자료들을
대상으로 한다. 파일의 구성 방식에 따라 순차적 파일 구조, 상대적 파일 구조, 색인 파일 구조, 다중 키 파일 구조 등이 있다.
만약 주어진 문제를 해결하기 위해 제시된 함수(절차)가 다음과 같은 5가지 특성을 만족하지 않는다면 그 함수는 알고리즘이 될 수 없다.
-
입력 : 외부에서 제공되는 자료가 0개 이상 있어야 한다.
-
출력 : 적어도 1개 이상의 결과를 만들어야 한다.
-
명백성 : 각 명령어는 의미가 모호하지 않고 명확해야 한다.
-
유한성 : 한정된 수의 단계 뒤에는 반드시 종료 된다. 무한히 동작해서는 안 된다.
-
유효성 : 모든 명령은 실행 가능한 연산이어야 한다. 예를 들어 0으로 나누는 연산이 포함되서는
안된다.
이렇게 알고리즘을 설명한 이유는 자료구조와 밀접한 관련이 있기 때문이다. 같은 자료라 하더라도 어떻게 표현되고 저장되는냐에 따라 사용
가능한 알고리즘이 달라지기 때문에 효율적인 자료구조의 설계는 알고리즘의 설계에 영향을 끼쳐 프로그램의 성능을 결정짓게 하는 가장 중요한 요인 중
하나가 된다.
- 알고리즘을 이루는 연산(산술, 대입, 비교 등)들이 몇 번이나 수행 되는지를 숫자로 표시 하는 것. 즉, 알고리즘의 수행 시간 분석
!!!
- 시간 복잡도 함수란 연산의 수를 입력의 개수 n의 함수로 나타낸 것. T(n)
- 만약 동일한 조건에서, 똑같은 일을 하는데 한 쪽은 20개의 연산을 수행하고, 한쪽은 100개의 연산을 수행한다고 가정하였을 때,
당연히 연산의 수가 적은(20개의 연산) 것이 더 효율적인 알고리즘이라고 할 수 있는데, 이것이 바로 시간 복잡도 방법의 기본 개념이라고 할 수
있다.
연산의 개수를 이용하여 알고리즘을 비교한 결과를 통하여 가장 효율적인 알고리즘을 선택 할 수 있다. 우리가 작성한 표를 보면 n도 있고, n의
제곱도 있는 것을 볼 수 있다.
위의 그림을 보게 되면 알 수 있겠지만 자료의 개수가 많을수록, 차수가 가장 큰 항이 가장 영향을 크게 준다는 것을 볼 수 있다.
그러므로, 차수가 가장 큰 항을 제외한 나머지 다른 항들은 상대적으로 무시해도 무마하다.
다음으로 알아볼 것은 시간복잡도를 표시하는 방법 중 하나인 빅오 표기법이다. 빅오표기법 뿐만아니라 빅오메가와 빅세타 기법도 있긴 하지만
대부분 사용하는 시간 복잡도의 표기법이 빅오표기법이다. 이러한 표기법들은 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간
복잡도를 표시하기 위해 만들어 졌다.
- O(n)이라고 표시하고, 빅오 of n이라고 읽는다.
빅오표기법의 방법은
1. 다항식의 경우 최고차항만을 남기고 다른 항들과 상수항을 버린다.
2. 최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다.
3. 단, log n 의 경우 없애버리면 안된다.
예를 들어, 시간복잡도 함수가 2n^2 + 3n + 1 이라고 할 때, 빅오 표기법의 방법을 이용하면 O(n^2)이라는 결과를 얻을 수
있다.
다음은 많이 쓰이는 빅오 표기법을 순서대로 표시한 것이다.
- O(1) : 상수형
- O(lon n) : 로그형
- O(n) : 선형
- O(nlong n) : 선형로그형
- O(n^2) : 2차형
- O(n^3) : 3차형
- O(2^n) : 지수형
- O(n!) : 팩토리얼형
그렇다면 이러한 성능 분석이 필요한 이유는 무엇일까?
요즘의 컴퓨터는 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 또한 계속하여 발전을 거듭하고 있다. 그러나
아무리 컴퓨터의 성능이 좋아지고 있다고 하나 여전히 프로그램의 효율성은 중요하게 여겨진다. 첫 번째 이유는 최근 상용 프로그램의 규모가 이전에
비해서는 엄청나게 커지고 있기 때문에 즉, 처리해야할 자료의 양이 많아 지므로 알고리즘의 효율성이 더욱 중요하게 된다. 입력 자료의 양이 적은
경우에는 무시해도 상관없겠지만 자료의 양이 많아지면 많아질수록 그 차이도 더욱 커지게 된다. 두 번째 이유는 사용자들 또한 프로그램의 더 빠른
성능을 요구 한다는 것이다. 결과적으로 사전 프로그래밍 계획에 있어서 이러한 성능 분석을 구하는 일은 매우 중요하다.
