[CS50-2019] C언어 총 정리(8) 알고리즘

[1] 알고리즘

* 알고리즘은 입력(input)에서 받은 자료를 출력(output)형태로 만드는 처리 과정.

입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열

알고리즘의 평가할 때는 정확성도 중요하지만, 효율성도 중요합니다.

* 의사코드 : 생각을 간결하게 정리한 구문 ex. 전화번호부를 집어든다. 책의 중간을 펼친다. 등등..

 

[2] 알고리즘 표기법

(1) Big O : 알고리즘 실행 시간의 상한을 나타낸 것

(2) Big Ω : 알고리즘 실행 시간의 하한

Big O (상한)		Big Ω (하한)
O(n^2) 느림	버블 정렬, 선택정렬	Ω(n^2) 느림	선택 정렬
O(n log n)	병합 정렬	Ω(n log n)	병합 정렬
O(n)	선형 검색	Ω(n)	버블 정렬(*정렬이 된 리스트를 받은 경우)
O(log n)	이진 검색	Ω(log n)
O(1) 빠름		Ω(1) 빠름	선형 검색, 이진 검색
* 알고리즘이 최선인 경우 실행시간(하한) 빠른 순서로 나타낸 것은?(단, 하한이 같은 경우 상한이 빠른 순으로 나열)   이진검색(Ω(1),O(log n)) - 선형검색(Ω(1),O(n))) - 버블정렬(Ω(n),O(n^2))) - 병합정렬 (Ω(n log n),O( n log n ))) - Ω(n^2), 선택정렬(O(n^2)))

* 안쪽 루프에서 교환이 하나도 일어나지 않는다면(이미 정렬되어 있다면) 바깥루프를 교환이 일어나지 않을때까지만 수행하게 코드를 작성해 바깥 루프를 돌지 않으므로 n

 

[3] 검색 알고리즘

(1) 선형검색 : 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색

- n개의 원소가 있을때, 최악의 경우(O(n), 상한) n번 수행, 최선(Ω(1), 하한)의 경우( 1번만에 찾음

- 정확하지만 아주 효율적이지 못한 방법

- 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용함

 

(2) 이진검색 : 배열이 정렬되어있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은 인덱스 또는 큰 인덱스로 이동을 반복

* 정렬은 시간이 오래 걸리고 공간을 더 차지한다.

 

[4] 정렬 알고리즘

(1) 버블 정렬 : 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬

- 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중

- 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수 있음

- n개의 값이 주어졌을때 (n-1)*(n-2) 번 반복되므로 정렬 실행 시간의 상한은 O(n^2)

- 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교해야 하므로 하한도 Ω(n^2)

 

(2) 선택 정렬 : 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬

- 교환 횟수를 최소화 

- 각 자료를 비교하는 횟수는 증가

- 두 번의 루프가 필요(바깥:숫자들을 처음부터 순서대로 방문하고, 안:가장 작은 값을 찾아야 하므로) 상한,하한 n%^2동일

 

[5] 재귀(Recursion)

- 함수가 본인 스스로를 호출해서 사용하는 것

 

[6] 재귀를 활용한 병합 정렬(합병 정렬)

- 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐가며 정렬을 하는 방식

- 숫자들을 반으로 나누는데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는데 각각 O(n)의 시간이 걸리므로 상한은 O(n log n)

- 숫자들이 이미 정렬되었는지 여부에 관계없이 나누고 병합하는 과정이 필요하므로 하한 역시 Ω(n log n)

* 7 4 5 2 6 3 8 1 을 정렬할 경우
(7	4	5	2)	(6	3	8	1)
( (7	4)	(5	2) )	( (6	3)	(8	1) )
(4	7	2	5)	(3	6	1	8)
(2	4	5	7	1	3	6	8)
1	2	3	4	5	6	7	8

 

 

※ 출처 :  CS50 - 2019 [네이버부스트코스] https://www.boostcourse.org/cs112/lecture/119038/?isDesc=false