[CDS] chapter 1 : 자료구조와 알고리즘

1. 자료구조와 알고리즘의 개념

컴퓨터 프로그램 = 자료구조 + 알고리즘 이라고 할 수 있다. 여기서 자료구조란 데이터를 효율적으로 저장하고 관리하기 위한 체계적인 방법을 말하고, 알고리즘은 데이터를 활용해 문제를 처리하는 절차를 말한다.

 

자료구조와 알고리즘은 서로 보완적인 관계에 있다. 적절한 자료구조 없이는 효율적인 알고리즘을 설계하기 어렵고, 효율적인 알고리즘 없이는 자료구조를 제대로 활용할 수 없다. 따라서 효율적인 프로그램을 작성하려면 반드시 자료구조와 알고리즘을 함께 고려해야 한다.

 

프로그래밍은 결국 알고리즘을 작성하고 그에 적합한 자료구조를 선택하는 것이다. 적절한 자료구조와 알고리즘을 적용하면 문제를 훨씬 효율적으로 해결할 수 있게 된다.

2. ADT : 추상 자료형

자료형(data type)이란 데이터의 종류를 말한다. C언어의 경우 정수(int), 실수(float), 문자(char)등을 기초 자료형으로 제공하고 있다. 자료형에서는 그 객체인 데이터와 함께 데이터 간의 연산이 중요한 고려요소가 되는데, 자료형마다 적용될 수 있는 연산이 달라지기 때문이다. 예를들어 나머지 연산의 경우 정수형에서만 적용될 수 있을 것이다.

 

이제 추상 자료형(Abstract Data Type)에 대해 살펴보자. ADT는 자료형을 추상적으로 정의한 것으로, 실제적인 구현으로부터 분리되어 정의된 자료형을 말한다. ADT는 사용자로 하여금 데이터 구조의 내부 구현에 신경 쓰지 않고 제공된 인터페이스를 통해 데이터를 조작할 수 있게 한다. ADT는 자료구조를 설계할 때 기능 중심으로 접근하여 그 동작을 명확히 정의할 수 있도록 도와주고, 구현 세부사항을 유연하게 변경할 수 있게 한다.

 

ADT의 예시는 chapter 4부터 공부할 여러 자료구조들의 학습내용에서 각각 확인할 수 있다.

3. 알고리즘 성능 분석

프로그램의 효율성이 중요한 것은 누구나 아는 사실이다. 그렇다면 프로그램의 효율성은 어떻게 측정해야 할까? 일단 가장 단순하고 강력한 방법으로 프로그램의 수행시간을 측정하는 방법을 생각할 수 있다. 동일한 작업을 수행하는 여러 프로그램들이 있다면 가장 빠르게 작업을 수행하는 프로그램이 가장 효율적이라고 판단할 수 있을 것이다. 그러나 이 방법은 1) 실험되지 않은 입력값에서는 같은 결론을 보장할 수 없고 2) 직접 구현해야 하며, 3) 실험환경을 완벽하게 동일하게 세팅해야 한다는 단점이 있다.

 

알고리즘 복잡도 분석은 알고리즘이 실행되는 동안 얼마나 많은 자원을 사용하는지 측정하는 것으로, 위와 같은 단점에서 자유로운 분석방법이다. 여기에는 알고리즘의 수행시간에 관한 시간 복잡도 분석과 알고리즘이 실행되는 동안 사용하는 기억공간의 크기에 관한 공간 복잡도 분석이 있다. 이하에서 시간 복잡도 분석을 중심으로 구체적으로 살펴보자.

(1) 시간 복잡도 함수

시간 복잡도는 알고리즘이 문제를 해결하는 과정에서 수행되는 연산의 횟수를 나타낸 것이다. 시간 복잡도 분석의 기본 개념은 동일한 문제를 해결하는 데에 있어 적은 연산 횟수만으로 해결가능한 알고리즘이 효율적인 알고리즘이라는 것이다. 여기서 연산의 횟수는 고정된 것이 아니고, 프로그램에 주어지는 입력의 개수 n에 따라 변하게 된다. 따라서 연산의 횟수는 n에 관한 함수로 나타낼 수 있는데, 이를 시간복잡도 함수라 하고 T(n)으로 표기한다.

(2) 빅오 표기법

프로그램이 조금만 커져도 T(n)은 매우 복잡한 함수가 될 것이다. 여기서, 1) 입력의 크기가 작을 경우 시간복잡도의 차이가 미미하고 분석이 크게 의미가 없는 점, 2) 입력의 크기가 큰 경우 n에 관한 최고차항이 전체 함수의 성능을 지배하게 되는 점, 3) 입력 크기가 커질때의 증가추세가 알고리즘 평가의 핵심 기준이라는 점에서 T(n)을 단순화 시킬 실마리를 찾을 수 있다.

 

빅오 표기법은 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 수 있도록 하는 표기법이다. 수학적 정의는 다음과 같다.

https://www.programiz.com/dsa/asymptotic-notations

빅오 표기법은 n의 값에 따른 함수의 상한값을 나타내는 방법으로, 입력 크기 n이 충분히 커질 때 T(n)이 빅오 표기법의 기준 함수의 상한선 이내에서 동작함을 보장한다.

 

빅오 표기법은 결국 상한을 표시하는 방법이기 때문에, 상한이 여러개일 수 있다는 문제점이 있다. 이를 보완하기 위한 표기법으로 1) 하한을 표시하는 방법인 빅오메가 표기법, 2) 동일한 함수로 상한과 하한을 만들 수 있는 경우 해당 함수로 표기하는 빅세타 표기법이 있으나, 통상적으로 빅오 표기법을 가장 많이 사용한다. 이 경우 최소차수로 상한을 표시하는 것이 관습인 것 같다.

(3) 기준 자료집합 : 최선 vs 평균 vs 최악

알고리즘 분석의 기준을 정립하는 데 있어 마지막으로 남은 과제는 어떤 자료집합을 기준으로 성능을 평가할 것인가이다. 예를 들어, 정렬 알고리즘의 경우 이미 정렬된 자료를 입력으로 하면 순식간에 수행이 완료될 수 있다. 이는 최선의 경우에 해당하며, 알고리즘의 성능을 평가하는 데 큰 의미를 가지지 않는다. 반면, 평균적인 경우는 현실적으로 가장 바람직한 기준이 될 수 있다. 그러나 평균적인 경우를 평가하려면 광범위하고 다양한 자료집합을 기반으로 평균값을 계산해야 하며, 이는 데이터 수집과 계산이 복잡하여 현실적으로 적용하기 어렵다.

 

따라서, 통상적으로 최악의 경우를 시간 복잡도의 기준으로 사용한다. 최악의 경우를 기준으로 하면, 알고리즘이 모든 상황에서 안정적으로 동작할 수 있음을 보장할 수 있기 때문이다. 특히, 최악의 경우 성능이 보장되는 알고리즘은 예측 불가능한 입력 상황에서도 신뢰성을 유지할 수 있어 실질적으로 더 중요한 척도로 여겨진다.