프랙티스만이 살길. 프랙티스만이 살길.
4. 알고리즘 본문
- 선형검색(linear search)
- 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사한다.
- 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법이다. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행해야된다. 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용하다.
For i from 0 to n–1
If i'th element is 50
Return true
Return false
- 이진 검색(binary search)
- 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 된다.
If no items
Return false
If middle item is 50
Return true
Else if 50 < middle item
Search left half
Else if 50 > middle item
Search right half
- Big O
- 위와 같은 그림을 공식으로 표기한 것이 Big O 표기법이다.
여기서 O는 **“on the order of”**의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 것이라고 볼 수 있다. O(n) 은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다. 주로 아래 목록과 같은 Big O 표기가 실행 시간을 나타내기 위해 많이 사용됩니다.- O(n^2)
- O(n log n)
- O(n) - 선형 검색
- O(log n) - 이진 검색
- O(1)
- 위와 같은 그림을 공식으로 표기한 것이 Big O 표기법이다.
- Big Ω
- Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다. 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.
- Ω(n^2)
- Ω(n log n)
- Ω(n) - 배열 안에 존재하는 값의 개수 세기
- Ω(log n)
- Ω(1) - 선형 검색, 이진 검색
- Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다. 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 됩니다.
- 버블정렬
- 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다. 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다. 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.
- 중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 $ (n-1)*(n-2) =n2−2n+1$ 번의 비교 및 교환이 필요하다. 여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있다. 정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 된다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
- 선택 정렬
- 정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입이.선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다. 1번째 n개의 탐색 2번째 n-1개의 탐색 을 더하면 $ n+(n-1)+(n-2)+…+1 = \cfrac{n(n+1)}{2} $ 따라서 소요 시간의 상한은 O(n^2)이 된다. 하한도 마찬가지로 Ω(n^2)이다. 버블 정렬과 동일하다.
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item
- 재귀(Recursion)
함수가 본인을 스스로 호출해서 사용하는 것
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int h)
{
// 높이가 0이라면 (그릴 필요가 없다면)
if (h == 0)
{
return;
}
// 높이가 h-1인 피라미드 그리기
draw(h - 1);
// 피라미드에서 폭이 h인 한 층 그리기
for (int i = 0; i < h; i++)
{
printf("#");
}
printf("\\n");
}
h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h 만큼의 #을 출력한다. 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 된다.따라서 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다. 함수가 초기에 주이진 입력보다 더작은 입력을 가지고 자신을 계속 호출한다.
- 병합 정렬(merge sort)
- 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다. 이 과정은 재귀적으로 구현된다
- 전체 과정을 요약해서 도식화해보면 아래와 같다.4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과이다.1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과이다.
- 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과이다.
- 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과이다.
- 병합 정렬 실행 시간의 상한은 O(n log n) 이다. 숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다. 실행 시간의 하한도 역시 Ω(n log n)이다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문이다.