자료 구조와 알고리즘

자료 구조, 알고리즘

자료 구조(data structure)란 대부분의 프로그램에서 사용되는 자료(data)를 효율적으로 표현하고 저장하기 위해 정의한 구조이다.

또한 주어진 문제를 처리하는 절차가 필요한데 이를 알고리즘(Algorithm)이라고 한다. 알고리즘은 다음의 특성을 가진다

• 0개 이상의 입력을 가진다
• 1개 이상의 출력을 가진다
• 각 명령어는 모호하지 않고 명확해야 한다
• 각 명령어는 실행 가능한 연산으로 구성되어야 한다
• 알고리즘은 유한한 시간동안 실행 후 반드시 종료되어야 한다

알고리즘은 어떤 프로그래밍 언어를 사용하던 문제를 해결하는데 사용하는 방법은 동일하기 때문에 알고리즘을 기술할 때에는 프로그래밍 언어로 꼭 작성하지 않고 유사 코드(pseudo-code) 또는 플로우 차트와 같은 흐름도로 나타내기도 한다. 하지만 플로우 차트의 경우 알고리즘이 복잡해지면 기술하기 힘들다는 단점이 있다.

유사 코드(pseudo-code)란 일반적인 언어보다는 체계적이고 프로그래밍 언어보다는 덜 엄격한 언어로 알고리즘의 표현에 적합한 언어이다.

배열을 통해 점수를 저장하고 어떤 정렬 방법을 이용하여 값을 정렬했다면 배열은 점수를 저장하는 자료 구조에 해당하고 정렬 방법은 알고리즘이 된다. 이렇게 자료 구조와 알고리즘이 더해져 프로그램이 완성된다.

추상 데이터 타입

데이터 타입(data type)이란 데이터의 집합과 그에 적용이 가능한 연산의 집합이다. 따라서 정수형 자료형의 경우는 정수 데이터의 집합 뿐만 아니라 덧셈, 뺄셈, 곱셈 등의 정수간 연산의 집합을 모두 포함한다.

자료 구조는 추상 데이터 타입을 프로그래밍 언어로 구현한 것이다.

추상 데이터 타입을 보기 전 추상화(abstraction)에 대한 개념을 알아야 한다. 소프트웨어 시스템의 복잡성에 대처하기 위한 방법론으로 나온 것으로 어떤 시스템의 간략한 기술 또는 명세로 시스템의 핵심 구조나 동작에만 집중하는 것이다.

추상화가 잘 된 경우는 사용자에게 중요한 정보는 강조되고 중요하지 않은 세부 사항은 제거하는 것이다. 이를 토대로 정보 은닉(information hiding)이 개발되었고 더 나아가 추상 데이터 타입의 개념이 나왔다.

추상 데이터 타입(abstract data type : ADT)는 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입을 말한다. 따라서 데이터의 집합과 데이터에 가능한 연산들에 대한 명세가 된다. 구현으로부터 분리되어 있다는 말은 데이터나 그 연산이 무엇인지는 알지만 이것이 어떻게 컴퓨터에서 구현되는지는 정의하지 않는다는 것이다.

이러한 추상 데이터 타입은 객체 지향 프로그램 언어에 큰 영향을 주었다.

알고리즘의 성능 분석

알고리즘의 성능은 공간적, 시간적인 관점에서 측정할 수 있다.

공간적의 경우 얼마나 큰 메모리를 필요로 하는가를 통해 측정할 수 있다. 시간적 관점에서 보면 계산 시간을 보는 것이다.

시간의 경우는 알고리즘 입력의 양이 많아지는 경우 그 차이가 상당해지기 때문에 일반적으로 실행 시간이 메모리 공간보다 중요하게 여겨지는 경우가 많다.

따라서 실행 시간에 초점을 맞추어 성능을 분석할 것이다.

알고리즘의 실행 시간 측정 방법으로 가장 직관적인 방법은 직접 실행시켜 측정하는 것일 것이다.

파이썬으로 실행 시간을 측정하는 경우 코드는 다음과 같다

import time
start = time.time() # 시작 시간을 저장하는 변수 start

# 실행 시간을 측정할 작업 코드

finish = time.time() # 종료 시간을 저장하는 변수 finish
print("time :", finish - start) 
# 종료 시간에서 시작 시간을 마이너스 하여 실행 시간 계산, 단위는 초

코틀린으로 실행 시간을 측정하는 경우 코드는 다음과 같다

fun main() {
	val start = System.currentTimeMillis() // 시작 시간을 저장하는 변수 start
	
	// 실행 시간을 측정할 작업 코드

	val finish = System.currentTimeMillis() // 종료 시간을 저장하는 변수 finish
	print((finish-start)/1000)
	//종료 시간에서 시작 시간을 마이너스하여 실행 시간 계산
	//밀리초 단위이기 때문에 1000으로 나누어 초 단위로 변환
}

하지만 이렇게 시간을 측정하는 경우 몇 가지 문제점이 있다.

• 알고리즘을 구현하고 테스트 해야한다.
• 두 개의 알고리즘을 비교하는 경우 똑같은 하드웨어와 똑같은 언어와 샅은 소프트웨어 환경에서 실행 시간을 측정해야 한다.

그래서 직접 구현하지 않고 대략적인 알고리즘의 효율성을 비교할 수 있는 복잡도 분석이란 것을 활용한다.

실행 시간 분석을 시간 복잡도라 하고, 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도라 한다. 일반적으로 알고리즘의 복잡도를 이야기할 때는 시간 복잡도를 말한다.

시간 복잡도(Time Complexity)

연산들의 실행 횟수는 보통 그 값이 변하지 않는 상수가 아닌 입력의 개수 n에 따라서 변한다. 그래서 연산의 개수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수 라 하고 T(n)으로 표기한다.

빅오 표기법

예를 들어 $T(n)=n^2+n+1$ 이라는 시간 복잡도 함수가 있다고 할 때, n의 크기가 급격하게 커질 수록 $T(n)$의 값을 결정하는 항은 $n^2$이 될 것이다.

따라서 입력의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도함을 알 수 있다.

그리고 $4n+3$의 시간 복잡도 함수와 $2n+1$의 시간 복잡도 함수가 있는 경우 n이 커지게 되면 두 값의 차이는 미미한 수준으로 볼 수 있다.

시간 복잡도 함수에서 불필요한 정보를 제거해 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법(big-oh notation) 이라고 하고 $O(n)$과 같이 쓴다. 빅오 표기법은 수학적으로는 다음과 같이 정의한다.

• 두 개의 함수 $f(n)$과 $g(n)$이 있을 때 모든 $n \ge n_0$에 대해서 $\mid f(n) \mid \le c \mid g(n) \mid$을 만족하는 2개의 상수 $c와 n_0$가 존재하면 $f(n)=O(g(n))$이다.

즉 빅오 표기법으로 표현된 전체의 값을 주도하는 가장 큰 항이 어느 시점 ($n_0$)부터 상수 c배 했을 때 항상 기존 $f(n)$의 시간복잡도보다 항상 크다는것이다. 이러한 부등식을 만족하는 $c$와 $n_0$는 무수히 많을 수 있다.

다음은 빅오 표기법을 실행 시간이 빠른 순서대로 표시한 것이다.

• $O(1)$ : 상수형
• $O(\log n)$ : 로그형
• $O(n)$ : 선형
• $O(n \log n)$ : 선형 로그형
• $O(n^2)$ : 2차형
• $O(n^3)$ : 3차형
• $O(2^n)$ : 지수형
• $O(n!)$ : 팩토리얼형

나머지 표기법

이 외에도 빅오메가 표기법이나 빅세타 표기법 등이 있다.

빅오 표기법은 상한을 표기하기 때문에 상한이 여러개 존재할 수 있기 때문에 최소 차수 함수로 표기했을 때만 의미가 있다.

하한을 표기하는 표기법은 빅오메가 표기법(big omega), 동일한 함수로 상한과 하한을 만들 수 있는 경우 표기법은 빅세타(big theta) 표기법이 된다.

3개의 표기법 중에서 가장 정밀한 것은 빅세타 표긱법이지만 통상적으로 빅오 표기법을 많이 사용한다. 하지만 빅오 표기법은 최소 차수로 상한을 표시해야 한다.

입력에 따라 실행 시간이 달라지는 경우

같은 알고리즘을 쓰고 있다 하더라도(예를 들어 정렬 알고리즘) 정렬된 입력 집합을 받거나 어질러진 입력 집합을 받는 경우와 같이 다른 실행 시간을 보일 수 있다.

알고리즘의 효율성은 3가지로 나누어질 수 있다.

• 최악의 경우(worst case)
• 최선의 경우(best case)
• 평균적인 경우(average case)

이 중에서 어떤 것을 기준으로 삼아야 할지 고민해봤을 때, 얼핏 보기에는 평균적인 경우 실행 시간이 가장 좋아 보이지만 평균 실행 시간을 구하는 것이 매우 힘든 상황이 많다.

따라서 최악의 경우 실행 시간을 알고리즘의 시간 복잡도 척도로 많이 사용한다. 예를 들면 어떠한 입력에 대해서도 일정 시간안에 반드시 계산이 완료되어야 하는 경우가 그렇다.

반대로 실행시간이 가장 적은 최선의 경우는 알고리즘에 따라 별 의미가 없는 경우가 많다.