[CS50] 제 4강 알고리즘

강의에서는 알고리즘을 배우면서 중요한 것은 알고리즘의 흐름, 개념을 잘 얻어가는 것이라고 한다.

강의는 경험인 것이고 익힘은 계속 적용해 나가면서 익히는 것이다.

 

 

검색 알고리즘

 

메모리를 바이트의 격자 배열로 취급하면 우리가 원하는 대로 사용할 수 있다.

서랍을 열어서 원하는 물건을 찾는다고 한다면 우리는 서랍을 한 번에 하나씩 열어가면서 찾을 것이다.

정렬되어있는 것을 알지 못하기 때문에 서랍을 한 개씩 여는 방법을 사용한다. - 선형 검색

혹은 정렬되어있는 것을 알고 있다면 반 씩 쪼개서 찾아가는 방법을 사용할 수 있다. - 이진 검색

 

이진 검색은 처음에 강의에서 알려준 전화번호부에서 이름 찾는 방식과 동일한 방법이다.

검색해야 하는 조건을 반씩 줄일 수 있기 때문에 선형 검색보다 높은 효율을 낼 수 있다.

 

 

알고리즘 표기법

 

Big-O : 알고리즘을 수행하는 데 필요한 시간의 상한선을 의미한다.

Big-Ω : Big-O와 반대로 최상의 경우 알고리즘에 필요한 시간의 하한선을 의미한다.

 

O는 정렬해야 하는 배열이 실행해야 하는 알고리즘에 의해 최대로 걸리는 시간을 나타낸다.

Ω의 경우는 그 반대로 최소한의 시간을 나타낸다.

예를 들어 선형 검색의 경우 맨 처음부터 하나씩 검색을 하게 될 텐데 내가 찾고자 하는 자료가 배열의 맨 처음에 있다면 

Big-Ω는 1이 될것이다. 그것은 Big-Ω(1) 이렇게 나타낼 수 있다.

그렇다면 선형 검색의 경우 Big-O는 어떻게 될까? 내가 찾고자 하는 것이 배열의 가장 마지막에 있다면 서랍을 가장 마지막까지 열어봐야 하기 때문에 배열의 개수가 n 개라면 n번 시도해야 찾을 수 있다. 그러므로 Big-O(n)라고 표현할 수 있다.

 

그렇다면 오메가(Ω)와 O의 값 중 어떤 것이 좋아야 좋은 알고리즘 인가?

컴퓨터 과학자가 가장 걱정하는 부분은 최악의 경우 컴퓨터가 어떻게 동작할지 또는 평균적으로 어떻게 동작하는지 이다. 그러므로 우리는 오메가보다는 O에 조금 더 집중해야 한다.

 

 

 

 

선형 검색

 

선형 검색 알고리즘은 정확한 방법일 수는 있지만 굉장히 비효율적인 알고리즘이다.

만약 검색해야 할 배열 목록이 수백만인데 찾아야 하는 자료가 맨 마지막에 있다면? 음..

 

선형 검색은 분명히 유용한 경우가 있다. 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다. 반대로 자료가 잘 정렬되어 있다면 선형 검색을 사용할 필요가 없다.

몇 개 안 되는 검색이라면 알고리즘의 영향이 크게 느껴지지 않지만 수백만 개의 목록을 검색한다고 생각하면 정렬의 중요성을 알게 될 것이다.

 

그러므로 정리가 안된 정보에서 데이터를 검색할 때 선형 검색을 사용할 것인지, 혹은 정렬 후 다른 검색 알고리즘을 사용할지를 기타 비용 등을 계산해서 사용하는 것이 중요하다.

 

 

 

버블 정렬

 

여타 다른 블로그 글들을 보면 알고리즘들에 대해 gif 이미지를 보여주고 잘 이해시켜준다. 내 게시글은 내가 이해하고 누군가에게 설명할 수 있을 정도로 정리할 수 있는지, 오늘 공부한 것을 잘 이해했는지 스스로 묻는 것이기 때문에 글 위주로 작성하고 있어 이미지가 따로 없다.

 

정렬 알고리즘 중 하나인 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 버블 정렬 알고리즘은 수행 한 번만에 모든 원소가 정렬되는 것을 보장하지 않는다.

버블 알고리즘은 Big-O(n^2)로 표현된다. 인접한 자료형들 모두를 비교해야 하기 때문에 n-1, n-2, … , 2, 1 이 횟수에 대한 sum공식은 {(n-1)*(n-2)}/2 가 된다. 사실 이런 수식은 중요하지 않다.

big-O에 들어가는 식은 그래프로 표현했을 때 유의미한 지표를 나타낼 수 있는 수를 적는다. 

 

버블 정렬은 O(n^2)이 된다. 하한선도 마찬가지로 배열이 정렬되어있는 채로 입력받아도 여전히 같은 횟수를 반복하며 정렬 수행을 하기 때문이다. 그래서 하한선 또한 Ω(n^2)로 정의한다.

 

하지만 버블 정렬이 효율적인 경우가 있다면 언제일까?

배열이 정렬되어 있는 경우이다. 정확히 n번만 비교하고 배열의 자리를 교체하는 과정이 없어진다. 원래대로라면 버블 정렬 알고리즘은 멈춤이 없이 계속해서 반복 수행하지만 교체 과정이 필요 없을 때 강제로 종료를 시켜준다면 최선의 성능( Ω(n) )을 보여 줄 수 있다. 내가 여기서 궁금증이 든 것은 "정렬하려고 알고리즘을 사용하는데 정렬된 배열을 또 알고리즘에 넣는 건 뭐지?" 라고 생각이 들었다. 하지만 시스템에 입력되어있는 정렬 알고리즘은 자료가 정렬되어 있는지 알지 못하기 때문에 그저 알고리즘 수행을 끝없이 반복한다. 그렇기 때문에 원래대로라면 버블 정렬은 하한선 또한 Ω(n^2)로서 효율이 매우 좋지 않지만, 배열의 교체가 없는 상황인 경우 반복 수행에 break를 줄 수 있다면 가장 최선의 효율을 낼 수 있다.

 

결론적으로는 버블 정렬은 O(n^2)으로서 효율이 좋지 않아 자주 쓰이지 않지만 braek를 줄 수 있는 경우를 만들어 줄 수만 있다면 최선의 효율을 가진 알고리즘이 될 수도 있다.

 

 

 

선택 정렬

 

오름차순을 기준으로 배열을 처음부터 끝까지 검색하면서 최솟값을 저장해뒀다가 맨 마지막까지 확인한 다음 맨 첫 번째 위치랑 교체하면서 정렬하는 방법이다. 처음부터 끝까지 계속해서 반복하는 알고리즘이기 때문에 말할 것도 없이 O(n^2)가 된다. 하한선의 경우도 마찬가지로 계속해서 처음부터 끝까지 검색해야 하기 때문에 Ω(n^2)가 된다.

 

조금 더 효율을 낼 수 있는 방법을 생각하면 최솟값만이 아니라 최댓값도 동시에 검색하면 약 2배의 효율을 낼 수 있겠다.

 

 

 

재귀 함수

 

재귀 함수는 함수 안에서 동일한 함수를 다시 호출하는 것을 말한다. 재귀 함수에서 동일한 함수를 계속해서 호출할 때마다 함수를 호출하기 위한 메모리또한 계속해서 할당되는데 이때 사용되는 메모리를 스택이라고 부른다.

함수가 종료되지 않고 계속 호출되는 경우 스택 공간이 초과되고 프로그램 충돌이 발생할 수 있기 때문에 재귀를 사용할 때는 과도한 스택 메모리가 사용되지 않도록 주의해야 한다. 

 

메모리 사용 문제 때문에 재귀는 매우 유의하면서 사용해야 하지만 아래에서 설명할 자료구조를 다룰 때 유용하게 사용될 수 있다.

 

 

 

병합 정렬 알고리즘

 

병합 정렬은 이진 검색 O(logN)과 비슷하다.

 

정렬할 자료가 한 개라면 종료되고

한 개가 아닌 경우 

왼쪽 절반을 정렬하고,

오른쪽 절반을 정렬하고,

이 두배 열을 병합한다.

 

이 과정을 재귀로서 이해하고 사용할 수 있다.

병합 정렬 알고리즘은 정렬 알고리즘으로서 비교와 정렬의 두 과정이기 때문에 O(n* log n) 이 된다.

 

배열을 반씩 나누고 한 개가 아닌 경우 절반을 나누고 정렬한다. 반을 나눈 것에서 반을 나누고 나눠 원소가 하나가 될때까지 계속 반복 수행해야 하는데, 이때 메모리 공간의 여유가 있다면 병합 정렬 알고리즘을 사용함으로써 높은 효율을 낼 수 있다.

메모리가 필요한 이유는 재귀에서 설명한 것처럼 반을 나누고 함수 안에서 같은 함수를 호출하는 과정에서 메모리를 사용하는 스택이 쌓이기 때문이다. 

 

재귀를 이해할 때 도움이 된 영상을 첨부했다.

 

https://www.youtube.com/watch?v=QAyl79dCO_k