문제 1

• 문제 : N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는?
• 시간제한 : 1초
• 입력 : 2 <= N <= 1,000,000

이 경우에는 N에 입력되는 수를 최악으로 두고 시간 복잡도를 파악해보아야하는데, 시간복잡도는 $O(N^2)$ 이에 1,000,000을 대입해보면 $(10^6)^2$ 가 된다.

시간제한은 1초이고, 1초에 약 1억 번의 연산이 가능하다고 봤을 때, 이를 훨씬 초과하기에 완전탐색으로 풀이할 수 없는 문제라고 인지할 수 있어야 한다.

풀이

완전탐색으로는 풀이가 불가능하기 때문에 다른 방법을 고안해야하는데, N을 sort하고 처리하는 방법을 생각해본다.

그럼 가장 큰 수가 index 기준 마지막, 마지막-1 에 위치할 것이다.

일반적인 정렬의 시간 복잡도 : $O(NlogN)$

1,000,000을 이에 대입해보면 1억보다 작은 수가 나온다.