[cs50] 알고리즘

https://www.boostcourse.org/cs112/lecture/118999/ 

모두를 위한 컴퓨터 과학 (CS50 2019)

알고리즘은 input 으로 받은걸 output 으로 만드는 처리과정이다.

이 처리과정은 output을 만들기위한 규칙을 순서대로 나열한것인데, 같은 Output이더라도 이 규칙이 다를 수 있다.

( 같은 문제더라도 알고리즘이 달라질 수 있다. )

 

예시를 같이보면 이해가 쉬운데,

전화번호부에서 "최하나"를 찾는다고 해보자

1. 앞에서부터 한장씩 넘기면서 찾는다.

2. 앞에서부터 두장씩 넘기면서 찾는다. 

3. 절반을 나누고 펼쳐진 페이지가 "최"보다 작으면 뒷장을, 크면 앞장을 계속 반으로 나누면서 본다. 

만약 성이 고씨라면 1번의 방법이 가장 빠를수있다. 하지만, 1만명이 등록되어 있는 전화번호부이고 "최"씨를 찾는거라면?  1번방법은 매우 비효율적이다.

이렇게 우리가 일상생활에서 머리로 생각할 수 있는 방법을 컴퓨터가 수행할 수 있도록 순서대로 매뉴얼을 알려주는것이 알고리즘이다.

 

그러면 좋은 알고리즘은 어떻게 알 수 있을까?

출처: cs50 부스트코스

 

위 그래프는 가로축이 문제의 크기이고 세로축이 해결하는데 걸리는 시간이다.

우리가 작성했던 이름찾기 알고리즘에서 첫번째 알고리즘은 그래프에서 n , 두번째알고리즘은 절반으로 줄어서 n/2 , 세번째 알고리즘은 logn 으로 크기가 커졌을 때 시간 복잡도가 크게 증가하지 않는 것을 알 수 있다. 이 그래프를 통해서 세번째 알고리즘이 특정 사이즈 이상에서는 좋다고 판단할 수 있다.