추상 자료형 (Abstract Data Type)

1. 자료구조와 알고리즘

---

1.1 자료구조

이번 방학을 알차게 보내기 위해, 방학때 이루고자 하는 목표를 차례대로 기록했다.

우선, 그동안 미뤄놨던 컴퓨터 파일 정리를 했는데, 학기-과목-과제 이런 계층적인 디렉터리를 이용해서 파일을 저장했다.

 

목표를 차례대로 기록하는 것, 컴퓨터에 계층적인 디렉토리로 저장하는 것과 마찬가지로

프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있으며, 이를 자료구조라고 한다.

 

예를 들면 대표적으로 다음과 같은 자료구조가 있다.

스택 : 식당에서 그릇을 쌓는 것처럼 자료들을 쌓아서 정리하는 구조
큐 : 마트 계산대의 줄처럼 먼저 도착한 자료가 먼저 빠져나가는 구조

 

 

 

1.2 알고리즘

알고리즘 기술방법 중 순서도

간단한 구구단 계산기 프로그램을 만들어본다고 하자.

간단하게 궁금한 단 수를 입력받고, 입력받은 단 수를 9단까지 계산하고, 결과를 출력한다고 생각해볼 수 있다.

이처럼 주어진 문제를 처리하는 절차를 알고리즘 이라고 한다.

 

즉,컴퓨터로 어떤 문제를 해결하고자 할 때는 다음과 같은 알고리즘으로 전개될 것이다.

1. 문제를 해결할 수 있는 방법 고안
2. 이들 방법에 따라 컴퓨터가 수행하여야 할 단계적인 절차를 자세히 기술 

 

자료구조와 알고리즘은 밀접한 관계가 있어서 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정된다. 컴퓨터가 복잡한 자료들을 빠르게 저장, 검색, 분석 등을 하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 하고, 각 응용에 적합한 자료구조와 알고리즘을 선택하여야 한다.

 

알고리즘을 기술하는데는 주로 의사 코드(Pseudo-code)를 사용한다.

 

 

 

1.3 추상 자료형

선풍기 사용 설명서를 본다고 생각하자. 사용 설명서에는 정지, 미풍, 약풍, 강풍, 회전 등의 기능 설명과 사용 방법이 나와있을 것이다. 하지만 버튼을 눌렀을 때, 선풍기 내부 회로에서 어떤 일이 발생하는지에 대해서는 전혀 언급되어 있지 않다.

이러한 사용설명서처럼 자료구조에서의 추상 자료형이라고 하는 것은 기능과 사용 방법만 정의한 것이다.

 

사용자 입장에서 내부 구현이 어떻게 되어있는지는 알 필요가 없다. 추상 자료형을 보고 목적에 맞게 가져다 사용하면 되는 것이다. 구현자는 구현을 위한 기능과 데이터 집합을 나열하는 것이다. 즉, 추상자료형은 사용자와 구현자를 분리해주는 역할을 한다.

 

추상 자료형(Abstract Data Type)에 어떻게 구현하는지가 추가되면? ▶ 자료구조(Data Structure)로서 설명

 

 

 

1.4 알고리즘의 성능 분석

위에서 알고리즘을 컴퓨터로 어떠한 문제를 처리하는 절차라고 정의했다. 그렇다면 당연히 적은 시간, 적은 메모리를 사용하는 최선의 효율성을 갖는 알고리즘으로 문제를 해결하는 것이 중요하다.

 

알고리즘 성능 분석은 알고리즘 복잡도 분석(Complexity analysis)을 사용하여 비교가 가능하다. 복잡도 분석은 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉜다. 이 중 시간 복잡도는 알고리즘이 문제를 해결하는 데 소요되는 시간을 수학적으로 표현한 것이다.

 

 

시간 복잡도 함수(Time Complexity Function)

시간 복잡도 함수는 입력 크기 n에 대한 함수로, 알고리즘이 실행되는 데 걸리는 시간을 나타낸다.

일반적으로 시간 복잡도는 아래와 같은 표기법을 사용하여 표현된다:

 

시간 복잡도 함수

• O(1): 상수 시간. 입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우.
• O(log n): 로그 시간. 입력 크기가 커질수록 실행 시간이 느리게 증가하는 경우.
• O(n): 선형 시간. 입력 크기에 비례하여 실행 시간이 증가하는 경우.
• O(n log n): 로그 선형 시간. 병합 정렬과 같은 알고리즘이 여기에 해당한다.
• O(n^2): 이차 시간. 중첩 반복문을 사용하는 알고리즘에서 흔히 볼 수 있다.
• O(2^n): 지수 시간. 피보나치 수열을 재귀적으로 계산하는 알고리즘 등이 여기에 해당한다.
• O(n!): 팩토리얼 시간. 순열을 생성하는 알고리즘 등이 여기에 해당한다.

 

시간 복잡도 분석은 알고리즘이 최악의 경우에 얼마나 오래 걸릴지를 평가하는 데 주로 사용된다.

이러한 분석을 통해 다양한 알고리즘을 비교하고, 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있다.

 

예를 들어, 두 정렬 알고리즘이 있다고 가정하자.

첫 번째 알고리즘은 시간 복잡도가 O(n^2)이고, 두 번째 알고리즘은 O(nlog n)이다.

입력 크기 n이 작을 때는 큰 차이가 없을 수 있지만, n이 커질수록 O(nlog n) 알고리즘이 훨씬 효율적이다.

 

따라서 성능 분석을 통해 알고리즘의 시간 복잡도를 이해하는 것은 매우 중요하며,

이는 최적의 알고리즘을 선택하고 시스템 자원을 효율적으로 사용하는 데 큰 도움이 된다.