1. 자료구조와 알고리즘의 이해

1-1. 자료구조에 대한 기본적인 이해

 

* 자료구조란 무엇인가?

자료구조: 데이터를 표현하고 저장하는 방법

 

* 자료구조의 분류

자료구조의 분류

* 자료구조와 알고리즘

자료구조: 데이터의 표현 및 저장방법

알고리즘: 표현 및 저장된 데이터를 대상으로 하는 문제의 해결 방법

자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있다. -> 알고리즘은 자료구조에 의존적이다.

 

1-2. 알고리즘의 성능분석 방법

 

* 시간 복잡도와 공간 복잡도

시간 복잡도: 알고리즘의 수행 시간

공간 복잡도: 메모리 사용량

알고리즘의 성능을 분석할 때 시간 복잡도에 초점을 맞춰서 분석한다. -> 데이터의 수에 따른 연산 횟수를 분석한다. (특히 최악의 경우를 따진다.)

 

* Big-O Notation

수학적 정의: 두 함수 f(n)과 g(n)이 주어졌을 때, 모든 n ≥ k에 대하여 f(n) ≤ cg(n)을 만족하는 두 개의 상수 c와 k가 존재하면 f(n) = O(g(n))이다.

시간 복잡도에서의 의미: 데이터 수의 증가에 따른 연산 횟수 증가율의 상한선을 표현한다.

 

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

int LinearSearch(int arr[], int len, int target) { // 순차 탐색 알고리즘이 적용된 함수
	for (int i = 0; i < len; i++) {
		if (arr[i] == target)
			return i; // 찾은 대상의 인덱스 값 반환
	}
	return -1; // 찾지 못했음을 의미하는 값 반환
}

 시간 복잡도: O(n)

 

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

// 배열에 저장된 데이터는 정렬이 되어 있다고 가정한다.
int BinarySearch(int arr[], int len, int target) {
	int first = 0; // 탐색 대상의 시작 인덱스 값
	int last = len - 1; // 탐색 대상의 마지막 인덱스 값
	int mid;

	while (first <= last) {
		mid = (first + last) / 2; // 탐색 대상의 중앙을 찾는다.
		if (target == arr[mid]) // 중앙에 저장된 것이 타겟이면
			return mid; // 탐색 완료
		else { // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
			if (target < arr[mid])
				last = mid - 1;
			else
				first = mid + 1;
		}
	}
	return -1; // 찾지 못했음을 나타내는 반환값
}

시간 복잡도: O(logn)