1. 알고리즘이란?

문제를 풀어나가는 매커니즘.
따라서 알고리즘의 본질로써, 모든 문제는 '가능한 모든 경우의 수를 찾는 행위'로 해결할 수 있다.
예) (0,0)에서 (5,5)로 가는 최단 경로는? -> 단순히 가능한 모든 경우의 수를 찾고, 그 중 최단 경로를 찾으면 문제 해결이 가능하다.

2. 완전탐색과 그리디

앞서 설명한 '가능한 모든 경우의 수를 찾는 행위'가 완전탐색이다.
그런데, 모든 문제를 완전탐색으로 해결하면 안된다. 왜? 컴퓨터 프로그램에서 자원(메모리, 서버 등..)은 한정되어있고, 따라서 비용을 줄이는 것이 마땅하다. 그래서 코테에서 시간 제한과 메모리 제한을 두는 것
완전탐색에서 비용을 줄이는 단순한 생각은 누가봐도 답이 아닌 것을 쳐내는, 가지치기가 있다.
그리디 알고리즘은 대표적인 가지치기 알고리즘으로, 여러 경우에서 하나를 결정할 때마다 '그 순간 최적이라고 생각하는 것을 선택'하는 알고리즘이다.

문제를 풀었을 때 걸리는 시간.
코딩테스트에서는 주로 연산 1억번 = 1초로 간주한다.
예) 어떤 입력 N <= 100,000이 주어졌다 하자. N이 배열의 원소 개수이고, for문을 통해 해당 배열을 첫 원소부터 끝 원소까지 두 번 탐색한다면? 최악의 경우인 N = 100,000이라면, N^2 = 100억 = 100초가 걸린다.
이 때 for문을 통해 위의 배열을 첫 원소부터 끝 원소까지 두 번 탐색하는 알고리즘을 ~~어려운말로~~ big-O 표기법으로 O(N^2)이라 한다.
결국 시간복잡도를 줄인다는 말은, O(N^2)인 알고리즘을 O(NlogN), O(N)과 같이 줄인다는 말이고, 위의 예시처럼 for문을 모두 순회하는 O(N^2)의 완전탐색을 가지치기로 O(NlogN), O(N)과 같이 줄이자는 것이다.
여담) 코딩테스트를 보는 눈: 입력이 10만대를 넘어서면 완전탐색은 절대 안된다는 것이다.