자료구조의 개념
자료구조를 간단하게 표현한다면, '컴퓨터 프로그래밍 언어에서 효율적인 자료(데이터)의 형태'를 의미한다.
- 우리는 효율적으로 자료를 사용하기 위해 자료구조를 배운다.
- 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조
선형 자료구조
- 항목들을 순서적으로 나열하여 저장하는 창고
- 항목 접근 방법에 따라 다시 세분화
-> 리스트: 가장 자유로운 선형 자료구조
-> 스택, 큐, 덱 : 항목의 접근이 맨 앞(전단)이나 맨 뒤(후단)로 제한
비선형 자료구조
-
항목들이 보다 복잡한 연결 관계
-
트리: 회사의 조직도나 컴퓨터의 폴더와 같은 계층 구조
-> 힙 트리는 우선순위 큐
-> 이진 탐색트리나 AVL트리: 탐색을 위한 트리 구조 -
그래프: 가장 복잡한 연결 관계를 표현
-> 다양한 문제를 해결하기 위한 기본 구조로 사용
알고리즘 개념과 자료구조의 관계
알고리즘이란 '어떤 문제를 해결해 가는 논리적인 과정'으로 정의할 수 있다. 다음 예로 알고리즘 개념을 익혀보자
_
( 동전 문제 )
지불해야 하는 값이 x 원 일 때 1원, 50원, 100원, 500원 동전을 이용해 값을 지불하시오.(사용되는 동전의 수가 최소가 되어야 함)
해당 문제는 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현이 가능하다.
그리디 알고리즘으로 문제를 해결할 때 500원의 개수, 100원의 개수, 50원의 개수, 1원의 개수 총 4번의 선택을 하게 되는데 각 선택에서 지불해야 하는 남은 금액을 최대로 채울 수 있는 개수를 선택하면 된다.
각 선택이 이전 선택에 관계없이 나머지 금액을 최대로 채울 수 있는 동전의 갯수를 선택하기 때문에 현재 선택이 이후의 선택에 영향을 주지 않는다는 greedy choice property 조건을 만족하며, 500원 ->100원->50원->10원, 큰 동전에 먼저 선택권을 부여하기 때문에 매 순간 나머지 금액을 최대로 채우는 선택이 결국 가장 최소의 동전 개수를 도출한다는 점에서 optimal substructure 조건을 만족한다고 할 수 있다._
알고리즘의 성능 분석
- 알고리즘의 성능 분석 기법
-
실행 시간을 측정하는 방법
-> 두 개의 알고리즘의 실제 실행 시간을 측정하는 것
-> 실제로 구현하는 것이 필요
-> 동일한 하드웨어를 사용하여야 함 -
알고리즘의 복잡도를 분석하는 방법
-> 직접 구현하지 않고서도 수행 시간을 분석하는 것
-> 알고리즘이 수행하는 연산의 횟수를 측정하여 비교
-> 일반적으로 연산의 횟수는 n의 함수
[시간 복잡도 분석] -> 수행 시간 분석
[공간 복잡도 분석]
<파이썬의 실행시간 측정 코드 예시>
다른 예시로 시간 복잡도를 비교해보자.
1번 예시
import time
start = time.time()
sum = 0
for i in range(1,10000001):
sum += i
end = time.time()
print(sum)
print('실행시간:', end- start)2번 예시
import time
start = time.time()
n = 1000000
sum = (n + 1) * n / 2
end = time.time()
print(sum)
print('실행시간:', end-start)
예시 1번은 데이터 개수에 비례해서 실행 시간이 늘어난다. 그러나 예시 2번은 데이터 개수 상관 없이 시간이 동일하다.
이를 시간 복잡도로 표현이 가능하다.
예시 1번은 O(n) 예시 2번은 O(1) 표기가 가능하다.
Big - O 표기법에 대해 알아보자!
- 대략적인 시간 측정을 위한 것으로 생각
- 차수가 가장 큰 항이 절대적인 영향
- 다른 항들은 상대적으로 무시
최선, 평균, 최악의 경우
보통은 최악의 경우(worst case)를 가장 널리 사용된다. 계산하기 쉽고 응용에 따라서 중요한 의미를 가지기 때문이다.
다음 내용
다음 내용에서 순환 알고리즘을 통해 시간 복잡도 분석을 더 알아보도록 하겠습니다.
자료구조는 심오하다...
