자료구조와 알고리즘에 대한 기본적인 이해
자료구조와 알고리즘에 대한 기본적인 이해
자료구조, 알고리즘이란 무엇인가?
우선 자료구조를 정말 간단하게 말하자면 데이터를 표현하고 저장하는 방법이다.
그리고 크게 이 방법을 두 가지로 나눈다.
1. 선형 구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식(리스트, 스택, 큐)
2.비선형 구조 : 데이터를 나란히 저장하지 않는 구조 (트리, 그래프)
자료구조가 '데이터의 표현 및 저장 방법'을 뜻한다면,
알고리즘은 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻한다.
숫자 데이터를 가지고 있는 배열을 예로 들자면,
- 자료구조적 측면 : int arr[10] = {1,2,3,4,5,6,7,8,9,10};
- 알고리즘적 측면 :
for(idx = 0; idx = 10; idx++){
sum += arr[idx];
}
알고리즘의 성능 분석 방법
우리는 잘 동작하는 것은 물론이거니와 좋은 성능까지 보장받기를 원한다. 때문에 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.
- 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)
- "어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느리냐?" -> 시간복잡도(속도에 관한)
- "어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰냐?" -> 공간 복잡도(메모리 사용량에 관한)
==> 하지만 대부분 속도에 초점을 맞춘다.
그럼 어떻게 속도를 평가할 수 있나요?
- "연산의 횟수를 셉니다."
- "그리고 처리해야 할 데이터의 수 n에 대한 연산 횟수의 함수 T(n)을 구성합니다."
==> 연산의 횟수를 통해 알고리즘의 빠르기를 판단한다.
- 순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심 요소
- 순차 탐색 알고리즘
#include <stdio.h>
int LSearch(int ar[], int len, int target)
{
int i;
for(i=0; i<len; i++)
{
if(ar[i]==target)
return i; // 찾은 대상의 인덱스 값 반환
}
return -1; // 찾지 못했음을 의미하는 값 반환
}
int main(void)
{
int arr[]={3, 5, 2, 4, 9};
int idx;
idx=LSearch(arr, sizeof(arr)/sizeof(int), 4);
if(idx==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
idx=LSearch(arr, sizeof(arr)/sizeof(int), 7);
if(idx==-1)
printf("탐색 실패 \n");
else
printf("타겟 저장 인덱스: %d \n", idx);
return 0;
}
for(i=0; i<len; i++)
{
if(ar[i]==target)
return i; // 찾은 대상의 인덱스 값 반환
}
그러면 "어떠한 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘일까?"
==> 값의 동등을 비교하는 ==연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.
비교 연산의 수행횟수에 따라 < 연산과 ++ 연산의 수행 횟수가 줄어들기도 늘어나기도 한다.
따라서 우리는 ==연산의 횟수를 대상으로 시간 복잡도를 분석하면 된다.
- 순차 탐색 알고리즘의 시간 복잡도 계산하기 1: 최악의 경우(worst case)
찾고자 하는 값이 배열의 맨 마지막에 저장되어 있거나 찾고자 하는 값이 아예 저장되어 있지 않으면 비교 연산의 수행 횟수는 n이 된다.
알고리즘을 평가하는데 '최선의 경우'는 관심대상이 아니다. 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다.
데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산 횟수는 (비교연산횟수는 ) n이다.
T(n) = n 최악의 경우를 대상으로 정의한 함수 T(n)
- 순차 탐색 알고리즘의 시간 복잡도 계산하기 2 : 평균적인 경우(average case)
평균적인 경우의 연산횟수 계산을 위해서 다음과 같이 두 가지 가정을 하겠다.
- 가정 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정한다.
- 가정 2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일하다.
그럼 배열에 탐색 대상이 존재하는 경우와 존재하지 않는 경우를 나눠서 연산 횟수를 계산해보자.
- 탐색 대상이 존재하지 않는 경우의 연산횟수 = n
- 탐색 대상이 존재하는 경우의 연산횟수 = n/2
탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이니
n* 1/2 + n/2 * 1/2 = 3n/4 (1/2씩 곱해서 더한 이유는 탐색 대상이 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문이다.)
==> 최악의 경우에 비해서 상대적으로 시간 복잡도를 구하는 것이 쉽지 않다. 또한 프로그램의 성격에 따라서 배열에 탐색 대상이 존재할 확률은 50%보다 높을 수도 있고 낮을 수도 있다. 그렇기에 이 계산은 '최악의 경우'의 시간 복잡도 보다 신뢰도가 낮다.