투 포인터

2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.

 

- 문제

어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)을 몇 개의 연속된 자연수의 합으로 나타내는 가짓수를 알고 싶다. 이 때 사용하는 자연수는 N이어야 한다. 예를 들어 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다.

 

① 문제분석하기

시간 제한은 2초이다. N의 최댓값은 10,000,000으로 "매우 크게 잡혀"있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다.

파이썬의 연산은 1초에 2000번~1억 번사이다. 최악의 경우인 2000번으로 이해한다.

 - O(n)일 경우에 1초에 5,000,000번 이하이다. 1초에 2천 번이라고 생각하면 범위 안에 들어온다(O)

 - O(logn)일 경우애 1초에 3천 번 이하이다. 1초에 2천 번이라고 생각하면 범위 안에 들어온다(X)

→ 이래서 시간 복잡도를 계산해야 하는구

 

 

- 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항).

- 시간제한이 1초인 문제를 만났을 때, 일반적인 기준

 

    - N의 범위가 500인 경우 : 시간 복잡도가 O(n^3)인 알고리즘을 설계하면 문제를 풀 수 있다.

    - N의 범위가 2,000인 경우 : 시간 복잡도가 O(n^2)인 알고리즘을 설계하면 문제를 풀 수 있다.

    - N의 범위가 100,000인 경우 : 시간 복잡도가 O(nlogn)인 알고리즘을 설계하면 문제를 풀 수 있다.

    - N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(n)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

 

 

※ 문제점 

- 매우 크게 잡혀 있다는 의미

 

이 부분은 내 블로그의 시간 복잡도 + Do it 알고리즘 코딩테스트(p. 18)에 나와 있는 내용이다. 즉, 상위에 있을수록 빠르다는 것인데 이를 빠르게 캐치하는 능력도 키워야한다.

 

O(1) - Constant Time(상수)

일정한 시간이 걸리는 알고리

 

O(n) - Linear Time(선형)

입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘이다.

n이 1늘어날 때마다 처리 시간이 1증가하여 처리 시간이 선형적으로 증가.

 

O(log n) 

이진검색이 대표적인 예이다

 

ex) 100 중에 원하는 숫자를 고를 때

50보다 큰가? Yes... -> 75보다 큰가?.... NO .......................

 

O(n^2) - Quardratic Time

이중 포문이나 배열의 크기가 커질수록 나타나는 복잡도

-> for문이 10개 있다고 해서 그럼 더 느려지는 걸로 의미되는가? No for문 하나를 상수처리해서 제곱으로 사용되므로 무시된다.

 

O(2^N) - Exponential Time

2n과 같이 n이 하나씩 증가할 때마다 걸리는 시간이 배로 증가하기 때문에

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
재귀 함수로 구현하는 피보나치(Fibonacci) 수열로 비유할 수 있다.