자료 구조 - Chapter01

자료 구조(Data Structure)에 대한 기본적인 이해

자료구조(Data Structure)

'데이터의 저장'을 담당하는 것. 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해 기술한다.

 

선형 구조

• 리스트
• 큐
• 스택

비 선형 구조

• 트리
• 그래프

파일 구조

• 순차 파일
• 색인 파일
• 직접 파일

단순 구조

• 정수
• 실수
• 문자
• 문자열

선형 구조는 자료를 표현 및 저장하는 방식이 선형(Linear)이다. 즉, 데이터를 선의 형태로 나란히, 일렬로 저장하는 방식이다. 비선형 자료 구조는 데이터를 나란히 저장하지 않는 구조이다. 상재적으로 선형에 비해 수월하지 않다.

 

자료구조와 알고리즘

자료구조가 '데이터의 표현 및 저장방법'을 뜻하면, 알고리즘은 표현 및 저장된 데이터를 대상으로 하는

'문제 해결방법'을 지칭한다.

알고리즘의 성능 분석 방법

자료구조와 알고리즘을 분석하고 평가하는 지표로 '속도'와 '메모리의 사용량'이 있다.

시간 복잡도(time complexity)

속도에 해당하는 알고리즘의 수행시간 분석 결과

공간 복잡도(space complexity)

메모리 사용량에 대한 분석 결과

 

알고리즘의 속도를 판단할 때, 연산의 횟수를 통하여 판단한다.

 

예제 : 순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심요소

 

순차 탐색

ex1_Linear Search.c

0.00MB

값의 동등을 비교하는 ==연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

이러한 탐색 알고리즘의 핵심은 동등비교 연산에 있다.

시간 복잡도를 계산하기 위해 핵심이 되는 연산을 잘 파악해야한다.

 

모든 알고리즘에는 가장 좋은 경우와 가장 나쁜 경우가 존재한다.

최선의 경우(Best case)

알고리즘을 평가하는데 '최선의 경우'는 관심 대상이 아니다.

최악의 경우(worst case)

데이터의 수가 많아지면 '최악의 경우'에 수행하게 되는 연산의 횟수는 알고리즘 별로 큰 차이를 보인다.

따라서 알고리즘을 평가하는 척도로 사용된다.

 

순차 탐색 알고리즘 시간 복잡도

데이터 수가 n개 일때, 최악의 경우에 해당하는 연산횟수는 n이다.

따라서 T(n) = n

 

예제 : 이진탐색(Binary Search) 알고리즘 시간 복잡도 계산하기

 

이진 탐색

ex2_Binary Search.c

0.00MB

이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용 불가하다.

이진 탐색 알고리즘의 시간복잡도 계산은 순차 탐색 알고리즘에 비하면 복잡한 편이다.

==연산을 연산 횟수를 대표하는 연산

 

이진 탐색 알고리즘 시간 복잡도

• n이 1이 되기까지 2로 나눈 횟수 k번, 비교연산 k번 진행
• 데이터가 1개 남았을 때, 마지막으로 비교연산 1회 진행

T(n) = k + 1

따라서 k는 n x (1 / 2)^k = 1 식이 되고, n = 2^k가 된다.

결과 적으로 log를 취하게 되면 T(n) = log2n 이 도출된다. 그런데 마지막 비교연산 1을 표기하지 않는 이유는

log가 상수에 비해 파급효과가 크기 때문에 그 효과가 미비하기 때문이다.

 

빅-오 표기법(Big-Oh notation)

함수 T(n)에서 가장 영향력이 있는 큰 부분을 따지는 것, 이때 사용되는 표기법에 대문자 O가 사용된다.

T(n)이 다항식으로 표현이 된 경우 최고차항의 차수가 빅-오가 된다.

빅오 표기법

예제 : 순차 탐색 알고리즘과 이진 탐색 알고리즘 비교

• 순차 탐색 : T(n) = n -> O(n)
• 이진 탐색 : T(n) = log2(n) + 1 ->O(logn)

이진 탐색 연산 횟수

ex3_Binary Search Count.c

0.00MB

순차 탐색은 n연산이 추가되는 반면, 이진 탐색은 연산량이 훨씬 적은것을 확인할 수 있다.