lecture 1: Algorithmic Thinking, Peak Finding
0. Intro
알고리즘은 input size에 따라 성능 차이가 존재한다.
가령, 친구들에게 전화를 걸어 파티에 초대하는 상황을 생각해보자.
한 명씩 직접 전화를 거는 방법은 시간이 오래 걸릴 수밖에 없다. 만약 친구가 10명이라면 10번의 통화를 해야 하고, 100명이라면 100번의 통화를 해야한다.
반면에 한 명에게 전화해서 그 친구가 다른 한 명에게 전달하도록 하는 방법을 생각해보자. 친구가 10명일 때는 4번의 전화로 충분하고, 100명일 때도 최소 7번의 전화로 연락을 끝낼 수 있다.
이렇게 input size가 커짐에 따라 알고리즘의 복잡도가 어떻게 변하는지 관찰하는걸 점근적 복잡도라고 한다.
따라서 알고리즘이란 Large size의 input이 들어왔을 때, 문제 해결을 위한 효율적인 방법을 찾는 학문이라고 할 수 있다.
1. Algorithmic Thinking : Peak Finding
A. One-dimension Case
1차원 배열에서 극댓값이라는 개념은 다음과 같이 정의할 수 있다.
\[\text{Position } \alpha \text{ is a peak if \& only if } (\alpha \geq \alpha_{\text{right}} \text{ and } \alpha \geq \alpha_{\text{left}})\]
배열에서 극댓값이 어떤 개념인지 명시된 후에는 “극댓값이 만약 존재한다면, 극댓값을 찾아라”라고 문제를 정의할 수 있게 된다.
앞서 말한대로 우리의 목적은 단순히 이 문제를 해결하는게 아니라, 배열이 길어짐에 따라 효율적으로 문제를 해결하는 방법을 찾는 것이다.
총 n개의 배열이라고 한다면, 최악의 경우 n개의 element를 관찰하면서 peak인지 아닌지 확인해야 한다. 이걸 수식으로 표현하면 다음과 같다. \[T(n) = O(n)\]
“n개의 input이 주어졌을 때, 최악의 경우 n에 비례한 시간 복잡도를 가진다”고 이해하면 된다. n이 일차 함수니까 선형 복잡도라고도 할 수 있다.
