CS50 2: 알고리즘

알고리즘이란 무엇인가?

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

알고리즘은 정확성과 효율성을 필요로 한다

 

 

 

 

의사 코드(Pseudocode)

그 동안 여기저기서 들어보았던 수도 코드가 이것이었다!

문법 걱정 없이 알고리즘을 단계별로 표현할 수 있는 유용한 방법이며 프로그램의 논리를 이해하는데 더 효과적인 방법

프로그램을 짜기 전 의사코드를 작성해보면 문제가 무엇인지, 어떻게 해결해야 좋을지 보다 더 직관적으로 보고 판단할 수 있다는 것이 큰 장점이다

 

 

 

선형 탐색

원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색하는 방법

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

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

 

버블 정렬

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

n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게 된다

최악의 경우 n-1번의 과정을 거쳐야 하기 때문에 효율적이지 못하다

 

선택 정렬

가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬

교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다

n-1번의 교환, n²번의 비교, 최악의 경우와 최선의 경우에서 수행하게 되는 교환, 비교 횟수가 동일하다

 

삽입 정렬

정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법

자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적

 

합병 정렬

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

n개의 원소가 있을 때 완전히 다 나누어지기까지 호출되는 함수의 개수는 log n개

합쳐지는 과정에서 각 원소들의 크기를 비교하기 때문에 n번의 비교 과정

즉 한번 나누어질 때마다 n번의 비교 횟수가 추가되기 때문에 시간 복잡도는 Ο(n log n)

 

이진 탐색

자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색의 범위를 반으로 줄여나가는 탐색 알고리즘

 

 

 

Big-O 표기법

최악의 경우에 대한 시간 복잡도를 나타내는 표현

 

 

Big Ω (omega) 표기법

최선의 경우에 대한 시간 복잡도를 나타내는 표현

 

 

 

 

 

 

 

고등학교 수학을 이용해서 계산한 거라는데 나는 하나도 모르겠다...^^

제곱 계산하는것도 힘든 나는 그냥 그렇구나.. 하고 넘어가는걸로....ㅎㅎㅎ