[cs50] 4강 Algorithms
scr: edwith
1) 검색 알고리즘
주어진 배열 속에서 특정 값을 찾는 방법
선형 검색
-
배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 검사
배열이 정렬되어 있지 않고 랜덤으로 있다면, 선형검색이 가장 적절한 방법일 수 밖에 없음.
For i from 0 to n–1
If i'th element is 50
Return true
Return false이진 검색
-
배열 중간 인덱스부터 시작해 값 비교하면서 이동을 반복
만약 배열이 정렬되어 있다면 선형검색보다 더 효율적임
2) 알고리즘 표기법
알고리즘의 실행 시간의 상한과 하한을 표기.
Big O 표기법
- 알고리즘 실행 시간의 상한
- “on the order of”의 약자
- ~ 만큼의 정도로 커지는.
알고리즘 실행 시간 그래프 예시 : -> O(n) , O(log n) 
주요 표기
O(n^2)
O(n log n)
O(n) - 선형 검색
O(log n) - 이진 검색
O(1)
Big Ω
- 알고리즘 실행 시간의 하한
ex) 선형검색에서 운 좋으면 한번에 찾기 가능 -> 하한은 Ω(1)
주요 표기
Ω(n^2)
Ω(n log n)
Ω(n) - 배열 안에 존재하는 값의 개수 세기
Ω(log n)
Ω(1) - 선형 검색, 이진 검색
3) 선형 검색
선형 검색으로 값을 찾는 방법
선형 검색
- 자료 검색 시 사용되는 다양한 알고리즘 중 하나
- 원하는 원소 발견까지 처음부터 마지막까지 차례대로 탐색
- 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 함
효율성 문제
- 정확하지만 비효율적임.
- 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우 무작위 탐색 보다 유용.
구조체
- 구조체 자료형을 정의하고 배열을 선언하면 속성값을 이용해 쉽게 접근가능.
예) person 구조체 정의. person a의 변수의 속성: a.name, a.number
4) 버블 정렬
- 정렬 알고리즘 중 하나
- 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬
- 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중 -> 너무 많이 교환하는 낭비 발생 가능.
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-1번, n-2번 반복 -> (n−1)∗(n−2)번 교환 필요
- 상한 : O(n^2)
- 하한 : Ω(n^2) -> 정렬 여부 관계 없이 중첩루프 돌며 확인해야하니까 하한도 상한과 같음.
5) 선택 정렬
- 정렬 알고리즘
- 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
- 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가
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): 선형 검색, 이진 검색
버블정렬을 효율적으로
만약 정렬된 배열이 주어진다면 안쪽 루프에서 교환이 하나도 일어나지 않음.
이럴경우 바깥루프를 교환이 일어나지 않으면 멈추라고 하면,
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) 이 될 수 있음
7) 재귀
재귀적 호출 : 함수를 함수 내에서 재사용하는 방법
- 재귀를 사용하면 중첩 루프를 사용하지 않고도 하나의 함수로 동일한 작업을 수행 가능
- 중첩 대신 재귀 사용하면 코드 효율이 높아짐.
#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");
}
}를
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) 병합 정렬
-
원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
-
재귀적으로 구현되는 정렬
-
상한 : O(n log n)
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문 -
하한 : Ω(n log n)
숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문
시간복잡도 로그 시간
만약 T(n) = O(log n) 이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다. 컴퓨터가 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. (즉, log2n, 때때로는 lg n 이라고 쓰임.) 그러나, 로그의 밑이 변할 때, logan와 logbn는 오로지 상수 승수에 따라서만 달라지며 이것은 빅-오 표기법에서는 버림한다; 그러므로 O(log n)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다.
scr : wikipedia
- 타 정렬과 비교했을 때
장점 : 상한이 낮음. 실행속도 빠름
단점: 하한이 높음. 저장공간/메모리 더 필요
시간 복잡도 정리
실행시간의 상한
- O(n^2): 선택 정렬, 버블 정렬
- O(n log n) 병합 정렬
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
.
실행시간의 하한- Ω(n^2): 선택 정렬,
버블 정렬- Ω(n log n) 병합 정렬
- Ω(n) : 버블 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
