CS50 - 4. 알고리즘
June 15, 2023
1. 검색 알고리즘
배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조입니다.
컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근합니다.
선형 검색
배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사합니다.
다음은 의사코드입니다.
For i from 0 to n–1
If i'th element is 50
Return true
Return false이진 검색
만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 됩니다.
다음은 의사코드입니다.
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 half2. 알고리즘 표기법
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 Ω
Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것입니다.
→ 보통 실행시간의 상한선을 고려하여 알고리즘을 작성합니다.(Big O 표기법을 선호)
3. 선형 검색
선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색합니다.
선형검색의 효율성
선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다.
리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행됩니다.
선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다.
이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다.
- 숫자 찾기
*#*include <cs50.h>
#include <stdio.h>
int main(void)
{
// numbers 배열 정의 및 값 입력
int numbers[] = {4, 8, 15, 16, 23, 42};
// 값 50 검색
for (int i = 0; i < 6; i++)
{
if (numbers[i] == 50)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;
}- 전화번호부
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};
for (int i = 0; i < 4; i++)
{
// 문자열을 비교하려면 strcmp를 사용. 문자열이 같다면 0을 반환. string.h에 있는 라이브러리
if (strcmp(names[i], "EMMA") == 0)
{
printf("Found %s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
}이 경우에는 names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 한계가 있습니다.
- 전화번호부(with struct)
#include <cs50.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
string name;
string number;
}
person;
int main(void)
{
person people[4];
people[0].name = "EMMA";
people[0].number = "617–555–0100";
people[1].name = "RODRIGO";
people[1].number = "617–555–0101";
people[2].name = "BRIAN";
people[2].number = "617–555–0102";
people[3].name = "DAVID";
people[3].number = "617–555–0103";
// EMMA 검색
for (int i = 0; i < 4; i++)
{
if (strcmp(people[i].name, "EMMA") == 0)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}4. 버블 정렬
정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다.
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.
버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.
이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.
8개의 숫자가 임의의 순서로 나열되어 있습니다.
6 3 8 5 2 7 4 1
3 6 8 5 2 7 4 1 (교환)
3 6 5 2 7 4 1 8
3 6 5 2 7 4 1 8 (교환)
3 5 6 2 7 4 1 8 (교환)
3 5 2 6 7 4 1 8
3 5 2 6 7 4 1 8 (교환)
3 5 2 6 4 7 1 8 (교환)
3 5 2 6 4 1 7 8
1 2 4 3 5 6 7 8 (정렬 완료)다음은 버블 정렬의 의사코드 입니다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로 (n-1)(n-2) = n^2-3n+2(n−1)∗(n−2)=n2−3n*+2 번의 비교 및 교환이 필요합니다.
여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다. 버블 정렬 실행 시간의 하한도 Ω(n^2) 입니다.
→ 버블 정렬(O(n^2))은 선형선택(O(n)), 이진 탐색(O(logn))보다 비효율적입니다.
5. 선택 정렬
보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.
정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
6 3 8 5 2 7 4 1
1 3 8 5 2 7 4 6 (가장 작은 값인 1과 6이 있던 자리 Swap)
1 2 8 5 3 7 4 6 (다음 작은 값인 2를 3이 있던 자리 Swap)
...
...
...
1 2 3 4 5 6 7 8 (계속해서 바꾼다면 오름차순 정렬 완성)이러한 정렬 방법을 선택 정렬 이라고 합니다. 다음은 선택 정렬의 의사코드 입니다.
For i from 0 to n–1
Find smallest item between i'th item and last item
Swap smallest item with i'th item여기서도 두 번의 루프를 돌아야 합니다.
바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 합니다.
따라서 소요 시간의 상한은 O(n^2)이 됩니다. 하한도 마찬가지로 Ω(n^2) 입니다. 버블 정렬과 동일합니다.
6. 정렬 알고리즘의 실행시간
실행시간의 상한
- O(n^2): 선택 정렬, 버블 정렬
- O(n log n)
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
실행시간의 하한
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n)
- Ω(n): 상황에 따라서는 버블 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
7. 재귀
함수가 본인 스스로를 호출해서 사용 → 재귀(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)
{
// 높이가 h인 피라미드 그리기
for (int i = 1; i <= h; i++)
{
for (int j = 1; j <= i; j++)
{
printf("#");
}
printf("\n");
}
}- 재귀 함수를 활용한 피라미드 그리기
#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");
}8. 병합 정렬
병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.
재귀적으로 구현이 가능한 정렬 알고리즘입니다.
다음은 병합 정렬 의사코드입니다.
if only one item
Return
else
Sort left half of items
Sort right half of items
Merge sorted halves다음 숫자들을 오름차순으로 병합 정렬해 보겠습니다.
7 4 5 2 6 3 8 1
7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과입니다.
4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한 결과입니다.
2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한 결과입니다.
1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과입니다.병합 정렬 실행 시간의 상한은 O(n log n) 입니다.
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.
실행 시간의 하한도 역시 Ω(n log n) 입니다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문입니다.
출처
- 모두를 위한 컴퓨터 과학(CS50 2019) https://www.boostcourse.org/cs112
