[자료구조] 자료구조 및 알고리즘 기초

자료구조를 정리하게 된 계기

코딩테스트에서 쉬운 자료구조 문제가 출제되었는데 정확하게 기억나지 않았다.

그 문제에만 많은 시간을 들였지만 결국 풀지 못했던 적이 있다.

그래서 학부시절 배웠던 자료구조 일부를 다시 정리하고 까먹지 않도록 복습하기 위해서 글을 남긴다.

 

자료구조 

: 주어진 문제를 해결하기 위해 필요한 데이터의 조직화

 

알고리즘

: 특정한 일을 수행하는 명령어들의 유한 집합

 

알고리즘 문제

유한한 입력 데이터 → 자료구조 + 알고리즘 → 입력 데이터에 대응되는 결과

 

알고리즘 조건

- 입력 : 0개 이상 입력

- 출력 : 1개 이상 출력

- 명확성 : 각 명령은 모호하지 않아야 함

  ex) x = 1/n (X)

        if (n != 0): x = 1/n (O)

- 유한성 : 한정된 단계 후에 반드시 종료

- 유효성 : 각 명령어는 실행 가능한 연산

 

좋은 알고리즘

: 사용된 메모리 공간이 적고, 수행시간이 적은 알고리즘

* 알고리즘의 평가 기준

  - 공간복잡도(Space Complexity) : 알고리즘 수행에 필요한 메모리 공간

  - 시간복잡도(Time Complexity) : 알고리즘 수행 시간

 

공간복잡도 분석

공간복잡도 = 고정공간 + 가변공간

- 고정공간 : 문제의 입출력 크기에 무관한 일정한 양의 메모리 공간

- 가변공간 : 문제의 입출력 크기에 따라 가변적인 메모리 공간

ex) n개의 실수 값들의 합 계산하는 함수

float sum(float list[], int n) {
	float tempsum = 0;
	int i;
	for(i = 0; i < n; i++)
		 tempsum += list[i];
	return tempsum;
}

- 고정공간 : i, n, tempsum → 2*sizeof(int) + sizeof(float)
- 가변공간 : list[] (call by value or call by reference)
- 총 공간의 양 : 2*sizeof(int) + sizeof(float) + 가변공간

 

시간복잡도 분석

프로그램 구현 없이 알고리즘에서 문장이 수행되는 스텝 수를 계산하여 측정

* 스텝 수의 계산 방법

  - s/e (steps/execution) : 각 문장에 대한 스텝 수 계산

  - frequency : 각 문장이 실행되는 빈도 계산

  - 각 문장에 대한 총 스텝 수 = (s/e) x (frequency)

ex) n개의 실수 값들의 합 계산하는 함수

Statement	s/e	frequency	total steps
float sum(float list[], int n) {	0	0	0
float tempsum = 0;	1	1	1
int i;	0	0	0
for(i = 0; i < n; i++)	1	n+1	n+1
tempsum += list[i];	1	n	n
return tempsum;	1	1	1
}	0	0	0
total			2n+3

cf) 시간복잡도를 계산하는 다른 방법

실험적 수행시간 측정 : clock()과 같은 시간을 재는 함수로 프로그램을 구현하여 수행시간 측정 → 잘 사용되지 않음

 

점근적 표기법(Asymptotic Notation)

: 알고리즘의 입력 크기 변화에 따른 수행 시간을 예측하기 위해 정확한 단계 수를 대신하여 수학적 기호를 사용하여 표현

* 표기 방법

1) Big-Oh (Big-O) : 상한 표현, 알고리즘의 최악의 실행시간 표기

O(g(n)) = f(n) : 모든 n≥\(n_0\) 에 대해 0 ≤ f(n) ≤ cg(n) 인 양의 상수 c 와 \(n_0\)이 존재한다.

 

2) Big-Omega (Big-Ω) : 하한 표현, 알고리즘의 최상의 실행시간 표기

Ω(g(n)) = f(n) : 모든 n≥\(n_0\) 에 대해 0 ≤ cg(n) ≤ f(n) 인 양의 상수 c 와 \(n_0\)이 존재한다.

 

3) Big-Theta (Big-θ) : 상한-하한 표현, 알고리즘의 평균 실행시간 표기

θ(g(n)) = f(n) : 모든 n≥\(n_0\) 에 대해 0 ≤ \(c_1g(n)\) ≤ f(n) ≤ \(c_2g(n)\) 인 양의 상수 \(c_1\), \(c_2\) 와 \(n_0\)이 존재한다.

 

입력 크기에 따른 시간복잡도