https://www.boostcourse.org/cs112/joinLectures/41307
David J. Malan (데이비드 J. 말란)의 <모두를 위한 컴퓨터 과학(CS50 2019)> 수강 내용
1) 검색 알고리즘
학습목표
주어진 배열 속에서 특정 값을 찾는 방법을 설명할 수 있다.
선형 검색
순차 검색 알고리즘(sequential search algorithm)/ 선형 검색 알고리즘(linear search algorithm): 리스트에서 특정한 값을 찾는 알고리즘 중 하나. 맨 앞에서부터 끝까지 차례대로 찾아나감.
// 의사코드(강의 중..)
for i from 0 to n-1
if i'th element is 50
return true
return false이진 검색
binary search algorithm: 정렬되어 있는 리스트에서 특정한 값을 찾아내는 알고리즘. 속도가 빠르다는 장점(정렬 전제 하에)
// 의사코드(강의 중..)
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
- on the order of: ~만큼의 정도로 커지는
- 실행 시간의 상한
- O(n^2) bubble sort, selection sort
- O(n log n) merge sort
- O(n) linear search
- O(log n) binary search
- O(1)
- 시간 복잡도 비교:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)
Big Ω
- 실행 시간의 하한
- Ω(n^2) selection sort
- Ω(n log n) merge sort
- Ω(n) - bubble sort 배열 안에 존재하는 값의 개수 세기.
- Ω(log n)
- Ω(1) - linear search, binary search
3) 선형 검색
학습목표
주어진 배열 또는 구조체에서 선형 검색을 할 수 있다.
효율성
- 아주 효율적이지 못한 방법
- 자료가 정렬되어 있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에 유용
구조체
- 여러 자료형을 가진 변수들을 하나로 묶어 자료형으로 사용할 수 있도록 정의하는 것
#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)
{
printf("Found %s\n", people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;
}4) 버블 정렬
학습목표
버블 정렬의 원리와 실행 시간을 설명하고 구현
버블 정렬
두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법. 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 them5) 선택 정렬
학습목표
선택 정렬의 원리와 실행 시간을 설명하고 구현
선택 정렬
배열 안의 자료 중 가장 작은 수를 찾아 첫번째 위치의 수와 교환해주는 방식의 정렬. O(n^2),Ω(n^2)
//의사코드
for i from 0 to n-1
find smallest item between i'th item and last time
swap smallest item with i'th item 6) 정렬 알고리즘의 실행시간
학습목표
여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다.
키워드
- Big O
- Big Ω
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
-
선택 정렬, 버블 정렬, 선형 검색, 이진 검색 4가지 알고리즘이 최선인 경우일 때의 실행시간이(하한) 빠른 순서대로 나열한 것은 무엇인가요?
(단, 하한이 같은 경우 상한이 빠른 순으로 나열한다)
이진 검색 - 선형 검색 - 버블 정렬 - 선택 정렬 -
오답체크
병합 정렬, 선택 정렬, 버블 정렬의 실행시간의 하한을 빠른 순서대로 정렬한 것은 무엇인가요?
버블 정렬 - 병합 정렬 - 선택 정렬
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");
}스택
- 재귀 함수에서 동일한 함수를 계속해서 호출할 때마다 함수를 위한 메모리가 계속 할당된다. 이 메모리를 스택이라 한다.
- stack overflow: 재귀 함수를 무한 호출 했을 때 발생.
8) 병합 정렬
학습목표
재귀를 활용한 병합 정렬을 구현.
병합 정렬(합병 정렬)
- 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
- O(n log n), Ω(n log n)
//의사코드
on input of n elements
if n<2
return
else
sort left half of elements
soret right half or elements
merge sorted halves