1. 자료와 자료구조
# 자료(data)는 현실 세계로부터 단순한 관찰이나 측정을 통해서 수집한 사실(fact)들 또는 값(value)들이다.
# 자료는 가공되지 않은 상태를 의미하고, 정보(infomation)는 어떤 기준에 의해 정리되고 기록된 것을 의미한다.
# 자료구조(data structure)는 자료 개체(data object)의 집합, 자료 값 사이의 관계 그리고 자료에 적용 가능한 함수 또는 연산 등을 의미한다.
# 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다.
# 데이터의 표현은 데이터의 저장을 포함하고, 데어터의 저장을 담당하는 것이 자료구조이다.
2. 자료의 구성 (각각에 대한 설명은 생략)
비트(bit), 바이트(byte), 단어(word), 항목(item or Field), 레코드(record), 파일(file), 데이터베이스(database)
3. 자료구조의 분류
단순구조 : 정수, 실수, 문자, 문자열
파일구조 : 순차파일, 색인파일, 직접파일
선형구조 ; 리스트, 스택, 큐
비선형구조 : 트리, 그래프
자료구조를 공부한다고 하면 대부분 이 중 선형구조와 비선형구조를 공부하는 것을 의미한다.
4. 자료구조와 알고리즘
# 자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면, 알고리즘은 이를 대상으로 하는 '문제의 해결 방법'을 의미한다.
# 자료구조에 따라 효율적인 알고리즘이 바뀌므로 자료구조에 따라 효율적인 알고리즘을 선택할 수 있어야 한다.
# 알고리즘은 '자연언어(일상언어)', 순서도, 특정 프로그램 언어, 의사 코드(pseudo code)를 이용하여 표현할 수 있다.
# 순서도를 사용하여 표현할 경우 단순한 알고리즘은 이해하기 쉬워지나, 특별한 구조나 세밀한 부분, 규모가 큰 알고리즘은 표현하기 어렵다는 단점도 있다.
# 순서도에는 N-S차트(Nassi-Schneidermann chart), HIPO, RERT, 자료흐름도(PFD)등의 기법이 있다.
5. 알고리즘 성능분석 방법
# 알고리즘 분석을 위한 판단 기준
'정확성(correctness)', '간결성(simplicity)', '작업량(amount of work done)', '기억장소 사용량(amount of space used)', 최적성(optimality)'의 다섯가지가 있다.
# 이 중 '작업량'과 '기억장소 사용량'이 중요하며, 작업량은 '시간복잡도(time complexity)', 기억장소 사용량은 '공간복잡도(space complexity)'로 측정한다.
# 하지만 현대에는 하드웨어 성능이 향상되어 대부분의 경우 작업량을 가장 중요하게 생각하는 편이다.
# 시간복잡도는 기본적으로 최악의 경우(가장 많은 연산을 수행해야하는 경우)의 명령문의 수행 빈도수를 데이터수 n과 그에 따른 함수 T(n)으로 만들어서 확인한다.
# 물론 평균적인 경우를 계산할 수 있으면 이것을 고려하는 것이 좋지만 평균적인 경우를 가정하는 것부터가 쉽지 않아서 잘 사용하지 않다.
# 이렇게 만들어진 T(n)을 빅-오 표기법(Big-Ho Natation)으로 따져서 시간 복잡도를 비교할 수 있다.
# 빅오 표기법에서는 T(n)의 가장 큰 차수항만을 가지고 함수 G(n)을 만들어서 시간 복잡도를 비교한다.
6. 계산 차수에 대한 성능 순서
성능 순위 |
계산 함수 |
이름 |
설명 |
1 |
O(1) |
constant(상수) |
데이터 수에 상관없이 연산횟수가 고정된 알고리즘. (가장 좋음) |
2 |
O(logN) |
logarithm(대수) |
데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘. (좋음) |
3 |
O(N) |
linear(1차식: 선형) |
데이터 수의 증가율과 연산횟수의 증가율이 비례하는 알고리즘. (평균적) |
4 |
O(NlogN) |
log linear(선형로그) |
데이터 수가 2배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘. (평균적) |
5 |
O(N^2) |
quadratic(2차식) |
데이터 수가 증가할 때, 연산횟수는 제곱으로 증가하는 알고리즘. 알고리즘에 반복문이 중첩되면 안좋은 이유. (안좋음) |
6 |
O(N^3) |
cubic(3차식) |
데이터 수가 증가할 때, 연산횟수는 세제곱으로 증가하는 알고리즘. 알고리즘에 반복문이 중첩되면 안좋은 이유. (안좋음) |
7 |
O(2^N) |
exponential(지수) |
데이터 수가 증가함에 따라 연산횟수가 지수적 폭발을 일으키는 알고리즘. 현실적으로 사용이 불가능하다. (못씀) |
7. 빅오 표기법의 한계
# 복잡한 알고리즘의 분석이 매우 어렵다.
# 평균 계산 차수를 구하기 어렵다.
# 세밀한 측정이 곤란하여, 작은 차이를 반영하지 못한다.
# 자료가 적은 경우는 알고리즘의 성능을 반영하지 못한다.