어려운 문제

우리는 문제를 풀 때 종종 어려운 문제를 만나곤 한다. 어려운 문제란 무엇일까?
컴퓨터의 연산으로 생각해보면, 연산이 많아서 사람의 힘으로 풀기 어려운 문제를 컴퓨터는 빠르게 연산하여 답을 찾아낸다.
그러나 그 컴퓨터도 연산하는데 시간이 오래걸린다면,, 그 문제는 '어려운' 문제가 된다.

1 ~ N 까지의 합을 출력하라는 문제가 주어졌다고 해보자.

이 문제를 풀기 위해 코딩을 한다면 가장 빠르게 생각해 볼 수 있는 것은 -> 반복문일 것이다.
반복문을 돌려 1~N까지 더해주게 되면 결과를 얻을 수 있다.
그러나 이 코딩은 N 값이 크면 클수록 덧셈의 횟수도 증가하게 된다. 즉, 계산하는 횟수가 많아지면서 그만큼 시간이 오래 걸리게 되는 것이다.

그러나 이 문제를 시간을 단축시키는 방법으로 풀 수 있다.
N(N+1)/2 연산으로 풀게 되면 컴퓨터는 한 번의 연산으로 문제의 정답을 낼 수 있게 된다.

즉, 알고리즘에 따라서 답을 구하는 시간이 다르게 되고, 이 시간이 짧을수록 성능 좋은 알고리즘이라 할 수 있게 된다.

---

시간 복잡도 (Time Complexity)

시간 복잡도란 알고리즘의 최악의 경우의 실행 시간을 말한다.

빅오 표기법 (Big-O notation)

연산에서 가장 크게 증가하는 항을 나타내는 표기법이다.

• $12 + 3N$ 연산의 솔루션은: $O(12 + 3N) = O(N)$
• $2N^2$ + 4N + 8 연산의 솔루션은: $O(2N^2 + 4N + 8) = O(N^2)$
• $k2^N$ 연산의 솔루션은: $O(k2^N) = O(2^N)$

시간 복잡도는

• $O(1)$ 상수 시간
• $O(logN)$ 로그 시간
• $O(N)$ 선형 시간
• $O(NlogN)$ 로그 선형 시간
• $O(N^2)$ 이차 시간
• $O(N^3)$ 삼차 시간
• $O(2^N)$ 지수 시간

순서대로 시간이 더 오래 걸리게 된다.

코딩 테스트 문제를 풀면서 해당 알고리즘의 정확한 시간을 계산할 수는 없을 것이다.
그렇기에 '1초 = 1억'이라는 개념을 가지고 가면 좋을 것이다!
1초에 연산이 1억번이 넘어간다면 알고리즘 문제에서 주어진 시간을 초과할 수도 있다.

---

공간 복잡도 (Space Complexity)

프로그램은 메모리를 많이 쓸수록 걸리는 시간이 적고, 메모리를 적게 쓸수록 시간이 오래 걸린다.
그래서 메모리를 아낄지, 시간을 줄일지는 선택해야 한다.

시간 제한이 1초가 있고, 메모리 제한이 128MB가 있고,
입력 값이 -1000 ≤ N ≤ 1000 일 때,
가능한 시간 복잡도/공간 복잡도는 어떻게 될까

N의 범위는 2000이다.
O(N)은 시간 제한이 1초=1억번 이기 때문에 2000번 연산은 가능할 것이다.
O($N^2$)는 $2000^2$ = 4,000,000 (4백만)이기 때문에 1억번 보다 작아 연산이 가능할 것이다.
공간 복잡도를 계산하면, int를 기준(4Bytes)으로 $2000^2$를 계산해 16MB가 나와 충분히 가능하게 된다.

---

Baekjoon Online Judge --> 알고리즘 문제들이 있는 페이지""