[CS50] 「2」 의사 코드, 정렬, 탐색, 시간 복잡도

[CS50] 「2」 의사 코드, 정렬, 탐색, 시간 복잡도

「1」 컴퓨터와 컴퓨팅

> 「2」 알고리즘 기초

「3」 프로그래밍 기초

 

> 1. 알고리즘

> 2. 의사 코드

> 3. 선형 탐색

> 4. 버블 정렬

> 5. 선택 정렬

> 6. 삽입 정렬

> 7. 시간 복잡도

> 8. 합병 정렬

> 9. 이진 탐색

1. 알고리즘

○ 입력을 출력으로 바꾸기 위해 수행되는 명령의 절차

○ 정확성과 효율성 중요

○ 자연어, 의사 코드, 순서도 등으로 표현

2. 의사 코드

○ 프로그래밍 언어보다 문법적 제약을 적게 받으므로 알고리즘 표현에 많이 사용

 

의사 코드 요소

○ 반복문, 조건문 포함

○ 정의된 문법 없음

3. 선형 탐색

○ 원하는 원소가 발견될 때까지 차례대로 탐색

○ 정확성 높고, 효율성 낮음

○ 자료가 정렬되지 않거나, 하나씩 찾아야 하는 경우 사용

○ 평균, 최악 O(n), 최선 Ω(1)

4. 버블 정렬

○ 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교, 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

○ 계속 정렬 여부를 플래그 비트(f)로 결정

○

평균, 최악 

O(n²), 최선 Ω(n)

초기상태			8	5	6	2	4
1회전			5	8	6	2	4	→	5	6	8	2	4
								→	5	6	2	8	4	→	5	6	2	4	8
2회전			5	6	2	4	8	→	5	2	6	4	8	→	5	2	4	6	8
3회전			2	5	4	6	8	→	2	4	5	6	8
4회전			2	4	5	6	8
최종			2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

5. 선택 정렬

○ n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 두고, 나머지 n - 1개 중 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하는 정렬 방식

○ 평균, 최악 O(n²), 최선 Ω(n²)

초기상태			8	5	6	2	4
1회전			5	8	6	2	4	→	5	8	6	2	4
								→	2	8	6	5	4	→	2	8	6	5	4
2회전			2	6	8	5	4	→	2	5	8	6	4	→	2	4	8	6	5
3회전			2	4	6	8	5	→	2	4	5	8	6
4회전			2	4	5	6	8
최종			2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

6. 삽입 정렬

○ 가장 간단한 정렬 방식, 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬

○ 두 번째 키, 첫 번째 키 비교, 순서대로 나열(1회전), 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전), n번째 키를 n - 1개의 키와 비교하여 알맞은 순서에 삽입

○ 평균, 최악 O(n²), 최선 Ω(n)

초기 상태		8	5	6	2	4
1회전		8	5	6	2	4	→	5	8	6	2	4
2회전		5	8	6	2	4	→	5	6	8	2	4
3회전		5	6	8	2	4	→	2	5	6	8	4
4회전		2	5	6	8	4	→	2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

7. 시간 복잡도

○ 알고리즘 수행 시간을 기준으로 효율성 분석

 

Big-O 표기법

○ 최악의 경우에 대한 시간 복잡도

 

Big Ω 표기법

○ 최선의 경우에 대한 시간 복잡도

8. 합병 정렬

○ 이미 정렬 돼 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

○ 두 개의 키들을 한 쌍으로, 각 쌍에 순서를 정함

○ 순서대로 정렬된 각 쌍의 키들을 합병하여, 하나의 정렬된 서브리스트 만듦

○ 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복

○ 평균, 최악 O(nlog₂n)

초기상태	71	2	38	5	7	61	11	26	53	42
1회전	(  2	71  )	(  5	38  )	(  7	61  )	(  11	26  )	(  42	53  )
2회전	(  2	5	38	71  )	(  7	11	26	61  )	(  42	53  )
3회전	(  2	5	7	11	26	38	61	71  )	(  42	53  )
4회전	(  2	5	7	11	26	38	42	53	61	71  )
최종	2	5	7	11	26	38	42	53	61	71

 

     : 비교 중       : 교환 발생       : 고정

9. 이진 탐색

○ 이분 검색(이진 검색)은 전체 파일을 두 개의 서브파일로 분리, Key 레코드 검색하는 방식

○ 반드시 순서화된 파일이어야 검색 가능

○ 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교해 가며 검색

○ 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율 좋고, 탐색 시간 적게 소요

○ 중간 레코드 번호 M = (F + L) / 2 (F : 첫 번째 레코드 번호, L : 마지막 레코드 번호)

○ 첫 번째 값(F), 마지막 값(L)을 이용하여 중간값 M을 구하여 찾으려는 값을 비교

 

ex) 1 ~ 100 중 15를 찾는데 걸리는 횟수?

 

M = (1 + 100) / 2  = 50 (정수만 취함) : 1회 비교

> 50은 찾으려는 값보다 큼, 1 ~ 49 사이

M = (1 + 49) / 2 = 25 : 2회 비교

> 25는 찾으려는 값보다 큼, 1 ~ 24 사이

M = (1 + 24) / 2 = 12 (정수만 취함) : 3회 비교

> 12는 찾으려는 값보다 작음, 13 ~ 24 사이

M = (13 + 24) / 2 = 18 (정수만 취함) : 4회 비교

> 18은 찾으려는 값보다 큼, 13 ~ 17 사이

M = (13 + 17) / 2 = 15 : 5회 비교

> 15는 찾으려는 값과 같음, 총 5회 비교

 

 

 

 

 

 

CS50 강의