1. Algorithm thinking, peak finding
우리가 알고리즘을 배우는 이유는 무엇일까?
이에 대한 대답은 시간이 지나면 지날 수록 증가하는 트래픽, 데이터들을 처리하기 위해서이다. 과거에 우리가 인터넷이나 프로그램을 사용할 때 평균적으로 사용되는 데이터들이 기하급수적으로 늘어나고 있고 이러한 데이터들을 효율적으로 처리하여 프로그램이 원활하게 기능을 수행할 수 있게끔 만들기 위해서 알고리즘이 필요한 것이다.
그렇다면 알고리즘에서 중요한 것은 무엇일까? 우리가 해결하고자하는 문제에서 원하는 조건과 원하는 조건을 방해하는 조건에 대해서 명확히 해야 한다는 것이다. 이 두 조건을 명확히 할 수 있어야 원하는 답을 얻기 위한 조건에 대해서 생각해볼 수 있기 때문이다. 이러한 것들은 아래의 예제들을 통해서 자세히 알아보자
Peak Finding
const 1d = [1,2,3,4,5,4,3,2]위의 예제 처럼 1차원의 배열이 주어졌을 때 이 배열에서 최고 고점, 정상을 찾기 위한 조건을 어떻게 찾을 것인지에 대한 문제를 예시로 제시 되었다. 1차원 배열에서 정상을 찾기 위해서는 어떻게 해야 할까? 우선 현실에서의 정상의 특징을 생각해보자. 현실에서 정상은 산에서 가장 높은 부분이다. 산에는 여러개의 봉우리가 존재하지만 그 봉우리 중에서 가장 높은 봉우리를 산의 정상이라고 한다. 이러한 특징을 문제에 갖고 와서 생각해보자
n === 찾고자 하는 정답의 인덱스
f(n) === 인덱스 n의 값
f(n - 1) < f(n) && f(n) < fn(n + 1)현실에서의 정상의 조건을 문제에 갖고와 조건으로 표현하자면 위와 같이 될 것이다. 이러한 조건을 찾는 방법은 무엇이 있을지 생각해봐야 한다.
- brute force search
- Divide and Conquer 이 중에서 고려해봐야 하는 사항은 2번 Divide and Conquer를 살펴보아야 한다.
n / 2 => 구하고자 하는 길이를 절반으로 나누어 정상이 존재할 수 있는 조건을 나눈다.
1. if (n/2) - 1 < (n/2):
정상은 절반의 값보다 더 큰 경우에 존재한다.
2. if (n/2) + 1 > (n/2):
정상은 절반의 값보다 더 작은 경우에 존재한다.
1.의 경우 0 ~ n/2 까지 탐색을 하면 된다.
2.의 경우 n/2 ~ n.length까지 탐색을 하면 된다.위와 같이 나누어 조건을 통해 세분화하여 탐색을 진행할 경우 아래와 같이 시간복잡도를 더 효율적으로 만들 수 있다.
$$T(n) = T(n/2) + \theta(1) = \theta(1) + \dots + \theta(1)(\log_2(n))times = \theta(\log_2(n))$$
log2(n)의 시간 복잡도는 기능을 수행하는데 대략 0.01초 정도의 시간이 걸리기 때문에 보다 효율적이라고 할 수 있다.
2. Models of Computation
컴퓨터에서 사용되는 비용에 대해서 고려해야한다. 컴퓨터에서 우리가 어떠한 기능을 사용될 때 소비되는 비용들은 무엇이 있을까? 우리가 웹을 실행할 경우 그 실행에 따른 메모리를 차지할 것이고 또한 그 웹을 실행을 완료하는데 시간이 들것이다. 이렇듯 크게 구분할 수 있는 비용은 시간(time), 공간(space, memory) 이 소비가 된다.
RAM & Random Access Machine
Web에서 특정 단어에 대한 검색 결과를 찾으려고 한다고 생각을 해보자. RAM은 Array와 비슷한 방식으로 데이터를 저장한다고 생각해볼 수 있다.