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

프로그램이란 ? 

Data를 저장하고, 저장된 data를 처리하는 것 

(Data Structure)            (Algorithm)

Program = Data Structure + Algorithm

자료구조

Data를 저장하는 방법 

선형 구조 ( List, Stack, Queue )

비선형 구조 ( Tree, Graph )

자료구조와 알고리즘

자료구조적 측면 code 

int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

알고리즘적 측면 code

for (idx = 0; idx < 10; idx++)

sum += arr[idx];

자료구조는 저장 방식, 알고리즘은 저장된 자료를 처리하는 방식이다. 

알고리즘은 자료구조에 의존적이다. 

알고리즘 성능 분석

Time complexity - 실행 속도에 초점을 맞춘 분석방법 (CPU)

Space complexity - 얼마나 많은 메모리를 사용하느냐에 초점을 맞춘 분석방법 (Memory)

성능 판단에 중요한 요소는 Worst case 이다. 

Big-oh 표기법 

O(f(n)) : 점근적 상한 

Binary Search

조건 : 배열이 정렬되어 있어야함 

탐색 후 탐색할 배열의 크기를 반으로 나눔

 

알고리즘

 

구현 코드

 

- 출처 : 윤성우의 열혈 자료구조 (윤성우, 오랜지 미디어)