〔CS50 / C언어〕알고리즘: 선형·이진 검색, 버블·선택·병합 정렬, 재귀 함수

 

1. 알고리즘(Algorithms)

(1) 선형 검색(Linear Search)

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 찾는 방법이다.배열이 정렬되어 있지 않을 경우에 유용하다.

 

(2) 이진 검색(Binary Search)

배열의 중간 인덱스부터 시작하여 찾고자하는 값보다 큰 인덱스 또는 작은 인덱스로 이동하여 중간 인덱스를 검사하는 것을 반복하여 찾는 방법이다.

배열이 정렬되어 있을 경우에 유용하다.

 

(3) 알고리즘 효율성 분석

알고리즘의 효율성을 분석하는 방법으로는 시간 복잡도와 공간 복잡도가 있는데 보통 위와 같은 시간 복잡도를 사용한다.

Big O 와 Big Ω는 g(n)을 상한으로 표시하기 때문에 점근적 상한과 점근적 하한을 나타낸다.

예를 들어, 선택 정렬은 n(n-1)/2 번의 상한을 가지지만 n이 아주 커지는 경우 최고 차항인 n^2 가 점근적 상한이 된다.

 

● Big O : 알고리즘 실행 시간의 점근적 상한(Upper Bound)

 

(BETTER) (WORSE)	O(1)	상수 시간(Constant Time)
	O(log n)	로그 시간(Logartihmic Time)	이진 검색
	O(n)	선형 시간(Linear Time)	선형 검색
	O(n log n)	선형-로그 시간(Log Linear Time)	병합 정렬
	O(n^2)	2차 시간(Quadratic Time)	버블 정렬 선택 정렬

 

● Big Ω : 알고리즘 실행 시간의 점근적 하한(Lower Bound)

(BETTER) (WORSE)	Ω(1)	상수 시간(Constant Time)	이진 검색 선형 검색
	Ω(log n)	로그 시간(Logartihmic Time)
	Ω(n)	선형 시간(Linear Time)	버블 정렬
	Ω(n log n)	선형-로그 시간(Log Linear Time)	병합 정렬
	Ω(n^2)	2차 시간(Quadratic Time)	선택 정렬

 

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 된다.

하지만 운이 좋다면 한 번만에 검색을 끝낼 수도 있으므로 하한은 Ω(1)이 되는 것이다.

 

빅오 표기법에 대하여 이해하기 쉽게 설명 되어있는 네이버 블로그 링크 첨부 (blog.naver.com/dsz08082/222103400094)

 

 

---

 

2. 선형 검색(Linear Search)

 

 

처음부터 마지막 자료까지 차례대로 검색하는 것으로 정확하지만 비효율적인 방법이다.

이를 활용하여 전화번호부에서 특정 이름을 찾아 해당하는 전화번호를 출력하는 프로그램을 작성하는 방법은 다음과 같다.

 

(1) 구조체를 사용하지 않는 방법

가장 간단한 방법이지만 names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 한계가 있다.

만약 전화번호부에 저장할 번호가 추가되거나 새로 정렬해야 하는 경우 실수가 생기기 쉽다. 

그러므로 확장성 있는 전화번호부 검색 프로그램을 만들기 위해서는 다음과 같은 구조체 정의가 필요하다.

 

(2) 구조체를 사용하는 방법

새로운 자료형으로 구조체를 정의해서 이름과 번호를 하나의 구조체에 묶어주는 방법이다.

위의 경우에는 person 이라는 자료형을 정의하고 해당 자료형의 배열 people[] 을 선언하였다.

배열의 원소는 people[0].name   people[3].number   처럼 "." 으로 연결하여 표현한다. 

return 0; 은 정상적인 프로그램 종료(Success)를 return 1; 은 비정상적인 프로그램 종료(Failure)를 의미한다.

typedef (Type Definition) 명령어를 통해 새로운 자료형을 정의할 수 있다.

 

 

---

 

3. 정렬(Sort)

 

 

(1) 버블 정렬(Bubble Sort)

두 개의 인접한 자료값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.

6 3 8 5 2 7 4 1 → 3 6 8 5 2 7 4 1 → 그대로 → 3 6 5 8 2 7 4 1 → 3 6 5 2 8 7 4 1 → 3 6 5 2 7 8 4 1 → 3 6 5 2 7 4 8 1 → 3 6 5 2 7 4 1 8 

이런 식으로 인접한 두 개의 숫자를 비교하여 교환 또는 유지하는 7번의 동작을 총 7 세트 반복하면 되는 것이다.

버블 정렬을 의사 코드로 나타내면 첫 번째 사진과 같으므로 총 (n-1)(n-1)번의 실행을 필요로 한다.

따라서 버블 정렬의 실행 시간의 점근적 상한과 하한은 Ω(n^2) 과 O(n^2)(※아래에서 계속) 로 같다.

정렬이 이미 완성되었는지 여부와 관계 없이 처음에 정해진 루프를 돌며 비교를 반복하므로 하한 역시 n^2 가 되는 것이다.

 

하지만 (n-1)^2 번의 시행을 모두 마치기 전에 정렬이 완료된 경우가 있을 수도 있다.

따라서 의사 코드의 첫번째 줄을 "n-1 세트 반복하기"  가 아닌 "교환이 발생하지 않을 때까지 반복하기"로 수정할 수 있다.

이 경우 운이 좋게 처음부터 순서대로 정렬이 완료된 숫자 리스트를 제공받은 경우 단 n-1 번의 비교만이 필요하다.

그러므로 버블 정렬의 실행 시간의 점근적 하한은 최종적으로 Ω(n) 가 된다.

 

 

(2) 선택 정렬(Selection Sort)

배열 안의 자료 중 가장 작은 수를 찾아 첫번째 위치의 수와 교환하여 정렬하는 방법이다.

의사 코드로 나타내면 두 번째 사진과 같으므로 총 n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 번의 실행을 필요로 한다.따라서 선택 정렬의 실행 시간의 점근적 상한과 하한은 Ω(n^2) 과 O(n^2)로 같다.

 

(3) 병합 정렬(Merge Sort)

 

원소가 한 개가 될 때까지 반으로 나누다가 다시 합쳐나가며 정렬을 하는 재귀적 방식이다.

병합 정렬의 실행 시간의 상한과 하한은 O(n log n)과 Ω(n log n)으로 같다.

숫자들을 반으로 나누는 데에 log n 번의 실행이 필요하고, 

두 개의 원소의 크기를 비교하고 병합하는 과정 중에 n 번의 자료 읽기가 필요하기 때문이다.

위의 예시에서는 8개의 원소를 가졌으므로 log2 8 = 3번 반으로 나누게 된다.

또한 크기를 비교하기 위해 모든 자료를 하나하나 읽어야 하므로 각각의 스텝 당 8번의 실행이 필요하다.

 

※ 병합 정렬에 대하여 쉽게 설명해주신 임경원 님의 블로그: devlimk1.tistory.com/138

 

 

---

 

4. 재귀(Recursion)

 

재귀란 함수가 본인 스스로를 호출해서 사용하는 것을 의미한다.

만약 위의 예시에서 사용자가 height 의 값으로 4 를 입력한다면 출력 결과는 다음과 같다.

#    

##

###

####

첫 번째처럼 중첩 루프를 이용하여 피라미드 모양을 출력할 수도 있지만 재귀를 이용하여 코드를 간결하게 만들 수 있다.

draw 함수 내에서 draw 함수를 호출함으로써 바깥쪽의 루프가 하던 똑같은 작업인 안쪽의 루프 실행 반복을 가능하게 한다.

함수를 따라가다보면 결국 h=0 에 도달하게 되는데 이 때에는 아무것도 출력하지 않도록 조건문을 추가해야 한다.

 

 

※ 네이버 부스트 코스 모두를 위한 컴퓨터 과학(CS50) 강의를 참고하여 작성하였습니다.

컴퓨터 코딩 프로그래밍 교육