CS50 4주차 - 알고리즘
이 포스팅은 부스트코스의 CS50 2019 강의의 내용을 공부한 글 입니다.
알고리즘 기초 (C언어)
검색 알고리즘
배열은 한 자료형의 여러 값들이 메모리상에 모여있는 구조이다.
컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나에 접근한다.
인덱스에서 50이라는 값을 찾기위해 [2, 7, 13, 25, 37, 42, 50] 검색하는 방법은 두가지가있다.
선형 검색
첫번째 인덱스부터 끝까지 증가시키며 50이라는 값이 속해있는지를 검사한다
For i from 0 to n-1 // 0인덱스부터 하나씩 증가시킬때
if i elements is 50 // 50이 있다면
Return true // true를 리턴
Return false //50이 없다면 false
이진 검색
배열의 중간 인덱스에 접근해서 찾고자 하는 값보다 큰지 작은지를 비교하여 검색
if no items
Return false
if middle item is 50
Return true
Else if 50 < middle item
만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?
선형 검색이 효율적이다. 이진 검색은 불가능하다.
알고리즘 표기법
위와 같은 그림을 공식으로 표기한 것이 Big O 표기법이다.
O의 약자는 ‘on the order of’의 약자로, ‘~ 만큼의 정도로 커지는’것이다.
O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다.
O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다.
- O(n^2)
- O(n log n)
- O(n) - 선형 검색
- O(log n) - 이진 검색
- O(1)
Big O가 알고리즘 실행 시간의 상한이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타낸다.
선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로
상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다.
- Ω(n^2)
- Ω(n log n)
- Ω(n) - 배열 안에 존재하는 값의 개수 세기
- Ω(log n)
- Ω(1) - 선형 검색, 이진 검색
실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
최악의 상황에서의 시간 단축이 더 중요하므로 상한이 낮은 알고리즘이 더 좋다.
선형 검색
#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";
for (int i = 0; i < 4; i++)
{
if (strcmp(people[i].name, "EMMA") == 0) // strcmp <- 문자열 비교
{
printf("%s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}
typedef struct에 name과 number이라는 속성을 저장하고
person으로 구조체를 선언해서 .name or .number 으로 연결해서 접근 가능
버블 정렬
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다.
간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
‘교환이 일어나지 않을때’까지만 수행
Repeat until no swaps
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
최종적으로 버블 정렬의 하한은 Ω(n)
실행시간의 하한
- Ω(n^2): 선택 정렬
- Ω(n log n)
- Ω(n): 버블 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
버블 정렬이 효율적인 경우는 어떤 경우인가요? 반대로 어떤 경우에 비효율적이게 될까요?
정렬이 되어있지 않았을 경우 효율 적이고 반대는 정렬되어 있을 경우이다.
선택 정렬
선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아
첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
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): 선택 정렬, 버블 정렬
- O(n log n)
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
실행시간의 하한
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n)
- Ω(n)
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
버블 정렬의 의사코드
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
‘교환이 일어나지 않을때’까지만 수행
Repeat until no swaps
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
최종적으로 버블 정렬의 하한은 Ω(n)
실행시간의 하한
- Ω(n^2): 선택 정렬
- Ω(n log n)
- Ω(n): 버블 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?
모든 수를 비교해야 하므로 단축시키기 어렵다.
재귀 (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)
{
if (h == 0) // 끝없이 반복하는 것을 막아줌
{
return;
}
draw(h-1);
for (int i = 0; i < h; i++) // #을 한줄씩 그려줌
{
printf("#");
}
printf("\n");
}
height의 값을 받았을 떄에 h-1 높이로 draw함수를 호춯하고, h 만큼의 #을 출력한다.
내부적으로 호출된 draw함수를 따라가다보면 h = 0이 된다.
반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 무엇일까요?
코드가 간결성
병합 정렬
병합 정렬은 버블 정렬이나 선택 정렬보다도 뛰어난 알고리즘으로 널리 알려져있다.
원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.
If only one item
Return
Else
Sort left half of items // 왼쪽
sortright half of items // 오른쪽
Merge sorted halves // 두 배열의 합
입력으로 어떤 정보의 배열이 주어졌을 때 받은 입력에 항목이 하나라면 그냥 반환한다.
이런 상황에는 이렇게 하라고 명시적으로 적여야 한다.
병합 정렬 실행 시간의 상한은 O(n log n)이다.
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고,
각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다.
병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요?
정렬 속도가 훨씬 빠르지만 메모리가 더 소비되는 단점이 있다.
Comments