[이론] 데이터구조와 알고리즘 개요

데이터 구조

데이터구조는
1) 데이터를 구성하고 저장하는 방법을 설명하며
2) 데이터를 식별하는 방법을 제공하고
3) 데이터의 관계를 보여주는 개념이다.

알고리즘

알고리즘은 문제를 해결하기 위해 사용하는 일련의 단계다.
문제를 해결하려면 알고리즘이 단순하고 명확하며 모호하지 않아야 한다.

데이터구조와 알고리즘의 관계

• 데이터 구조와 알고리즘은 서로 다른 개념이면서 상호 보완적이다.
• 데이터 구조는 알고리즘이 다루는 데이터를 구성하며,
• 알고리즘이 데이터를 처리하고 사용자가 원하는 완전한 정보를 산출하는 과정에서 필요한 부분을 제공한다.

기본 자료형

• 불
  • 논리 자료형으로 참과 거짓, 0과 1, 켜기와 끄기 등 두 개지 상태를 표현할 수 있다.
  • 컴퓨팅 분야의 핵심
  • 양자 컴퓨팅 분야에는 큐비트라고 하는 양자비트가 있다. : 0과 1 어느 쪽도 확정할 수 없는 상태까지 표현한다.

• 문자
  • 자연어 : 사람이 데이터를 더 쉽게 이해하고 기억할 수 있게한다.
  • 문자는 문자열을 구성하는 데 사용되며 컴퓨터마다 인코딩 방식이 다를 수 있다.

• 정수
  • 수학에서 정수는 무한하지만, 컴퓨터 과학에서의 정수는 CPU 아키텍처와 메모리 용량의 한계, 프로그래밍 언어에 정해져 있는 정부 범위의 제한 때문에 무한하지 않다.

• 부동 소수점 수
  • 부동점 (floating point) : 소수점이 숫자를 정밀하게 표현하기 위해 어딘가 떠다니는 것처럼 움직이기 때문에 붙여진 이름
  • 단정도 (single precision) : 32비트로 1위드를 표현 (float)
  • 배정도 (double precision) : 64비트로 1위드를 표현 (double)
    • 위드 : CPU가 한 번의 버스 사이클을 통해 메모리나 입출력 장치에 접근할 때 데이터의 크기다. 예를 들어, 32비트 OS에서 1위드는 32비트이고, 64비트 OS에서 1위드는 64비트이다. CPU 아키텍처에 따라 처리하는 데이터양은 다르다.
  • 이 밖에 128비트를 1위드로 표현하는 decimal이라는 자료형도 있다.

재귀

사전에서 찾은 정의가 다음과 같다면?

'뚱띵' : '뚱띵'을 참조하세요.

자기 자신을 참조하므로 사전에서는 사용하면 안 되는 표현이다. 하지만 프로그래밍 영역에서는 실행 도중 자기 자신을 호출하는 함수인 재귀 함수를 기본으로 제공하거나 직접 정의할 수 있다. 이 재귀 함수는 보통 특정 조건을 충족할 때까지 끊임없이 동작한다.

컴퓨터 메모리에는 한계가 있으므로 재귀 함수가 자기 자신을 호출하는 횟수가 늘어날수록 컴퓨터의 가용 메모리 공간은 점점 줄어든다.
결국 자기 자신을 호출하는 횟수의 한계인 최대 재귀 깊이 (maximum recursion depth)를 초과해 스택 오버플로 에러 (stack overflow error)가 발생할 수 있다.

재귀는 프로그래밍 언어에서 자주 쓰이는 개념이며, 실제로 많은 알고리즘이 재귀적으로 동작한다.

반복

반복이란 특정 조건이 충족될 때까지 코드 덩어리의 실행이 되풀이되는 것을 뜻한다.

반복은 알고리즘 실행뿐만 아니라 일반적인 프로그래밍에서도 광범위하게 사용된다. 반복에서 유의할 점은 재귀와 마찬가지로 컴퓨터 가용 메모리의 한계 때문에 반복의 종료 조건을 지정하지 않으면 프로그램에 에러가 발생한다는 것이다.

알고리즘의 세 가지 유형

• 분할 정복 알고리즘 (divide and conquer algorithm)
  • 큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결 방법을 얻는 알고리즘이다.
  • 개미가 혼자 나뭇잎 더미를 다 옮기기엔 힘들지만, 여러마리가 하나씩 옮기면 가능하다.

• 탐욕 알고리즘 (greedy algorithm)
  • 실행되는 순간마다 최상의 결정 (가장 적합한 동작)을 내리는 알고리즘이다.
  • 단, 매번 최선의 결정을 내리며 살더라도 그 결정이 인생 전체에 대해 언제나 최선일 수는 없다. 이처럼 탐욕 알고리즘이 내리는 결정도 문제 전체를 해결하는 최적의 결정인지는 장담할 수 없다.
  • ex) 방문 판매원 문제 : 방문 판매원이 n개의 도시를 방문하려고 한다. 가능한 한 최소 거리를 이동하며 n개의 도시를 모두 방문하는 최단 경로는 무엇인가?
  • 탐욕 알고리즘이 문제를 해결하는 방식은 한 도시에서 시작해 방문한 도시마다 그 다음으로 가장 가까운 도시를 방문하는 것이다. 이것이 최단 경로인지는 장담할 수 없지만, 최적 경로의 근사치는 구할 수 있다.

• 동적 프로그래밍 알고리즘 (dynamic programming)
  • 탐욕 알고리즘과 대조를 이룬다.
  • 동적 프로그래밍 알고리즘은 과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘이다.
  • 탐욕 알고리즘과 동적 프로그래밍 알고리즘 모두 문제를 더 작은 단위로 나누는 데 중점을 둔다는 공통점이 있지만, 탐욕 알고리즘은 특정 순간에 최적인 해결 방법을 찾고 동적 프로그래밍 알고리즘은 문제를 해결하는 다양한 해결 방법을 찾아 저장한 후 나중에 재사용한다는 점에 차이가 있다.
  • 동적 프로그래밍 알고리즘은 음석 인식, 유전자 염기서열 분석, 연쇄 행렬 곱셈에 주로 사용된다.
  • 간단히 정리하면, 탐욕 알고리즘은 근사치를 구하고 동적 프로그래밍 알고리즘은 최적화를 한다.

알고리즘 분석

알고리즘을 설계한 뒤에는 알고리즘의 성능을 분석할 필요가 있다. 알고리즘은 문제를 해결하기 위해 사용하는 일련의 단계이다. 문제를 해결하기 위해 사용하는 단계가 적을수록 더 효율적인 알고리즘이라고 할 수 있다.

그래서 알고리즘을 분석할 때는 시간 복잡도 (time complexity)와 공간 복잡도 (space complexity)의 두 가지 방법을 이용한다.

• 시간 복잡도 : 주어진 입력에 따라 알고리즘이 문제를 해결할 때 걸리는 시간을 뜻한다. 시간 복잡도를 이용하는 알고리즘 분석은 알고리즘의 성능이 얼마나 효율적인지 알 수 있는 가장 일반적인 방법이다.
  • 실제적인 방법 : 입출력 데이터의 양이 알고리즘 동작에 미치는 영향을 관찰하고 기록하는 것이다. 이러한 관찰과 기록을 바탕으로 알고리즘이 얼마나 효율적인지 판단할 수 있다. 하지만 실제적인 방법은 정확성이 떨어지고 사용 범위가 제한적이다. 이를 피하기 위해 수학적인 방법을 사용한다.
  • 수학적인 방법 : 점근적 분석 (asymptotic analysis)라고 한다. 이 분석 방법의 본질은 수학적으로 알고리즘 성능의 한계를 증명하는 것이므로 실제적인 방법보다 많은 시간을 절약할 수 있기도 하다.
• 공간 복잡도 : 알고리즘이 문제를 해결할 때 점유하는 컴퓨터의 메모리 공간을 뜻한다. 공간 복잡도를 이용하는 알고리즘 분석은 그리 널리 사용되는 편이 아니다. 자원이 제한된 시스템에서 동작하는 프로그램을 구현하는 것과 같이 특별한 경우에 사용하는 분석 방법이다.

빅 오 표기법

알고리즘의 성능이 최악이 되는 경계를 판단하거나 알고리즘의 평균 성능을 찾으며, 이때 알고리즘 사이의 점근적 증가율* (asymptotic growth rate)을 비교하기 위해 빅 오 표기법을 사용한다.

*알고리즘에 입력하는 데이터양의 증가에 따른 처리 시간 변화율을 뜻한다.

알고리즘의 효율성을 수학적으로 판단하는 방법은 몇 가지 범주로 나눌 수 있다. 1) 알고리즘을 실행하는 데 걸리는 시간이 가장 긴 최악의 경우를 측정하는 것, 2) 알고리즘을 실행하는 데 걸리는 시간이 가장 짧은 최상의 경우를 측정하는 것, 3) 최악의 경우와 최상의 경우를 모두 측정하는 것이다. 때로는 4) 알고리즘을 실행하는 데 걸리는 시간의 평균을 측정할 수도 있다.

알고리즘의 효율성을 설명할 때는 빅 오메가 (Ω), 리틀 오메가 (ω), 빅 오 (O), 리틀 오 (o), 세타 (θ)등 다양한 표기법이 존재하며 각 표기법은 용도가 정해져 있다.

점근적 분석에 가장 많이 사용되는 것은 빅 오 표기법이다. 빅오라는 이름에서 대문자 O는 시간 복잡도의 정도를 나타내는 표기법인 차수-order (복잡도의 차수- order of complexity라고도 한다)를 뜻한다. 그런데 알고리즘의 복잡도를 주로 대문자 O 또는 빅 오를 사용해서 표기하는 관례가 생기면서 자연스레 빅 오 표기법이라고 부르게 된 것이다.

오메가 (Ω, ω) : 알고리즘을 실행하는 데 걸리는 최소 시간을 측정
세타 (θ) : 알고리즘을 실행하는 데 걸리는 최소 및 최대 시간을 모두 측정
빅 오 (O) : 알고리즘을 실행하는 데 걸리는 최대 시간을 측정.

빅 오 표기법의 본질은 알고리즘의 실행 시간이 최악인 경우를 나타내는 것이다.

○ 빅 오 표기법으로 실행 시간을 나타내는 방법

○ 성능이 좋은 순서 :

O(1) > O(logn) > O(n) > O(nlogn) > O(n2) > O(2n) > O(n!)

수형 알고리즘 O(1)의 성능이 가장 좋고 계승 (팩토리얼)형 알고리즘인 O(n!)의 성능이 가장 나쁘다.
O(n!)은 실제로 컴퓨터 과학이 해결해야 하는 복잡한 문제의 시간 복잡도 이며, 대표적으로 앞의 방문 판매원 문제가 있다.

참고 : 코드 없는 알고리즘과 데이터 구조