알고리즘 시작

백준이나 여타 문제 풀이 사이트에서 문제를 풀다보면, 제한시간이 있는것을 볼 수 있다.

 

학교에서 했던 문제풀이 과제역시 시간제한이 있었지만, 수업시간에 배웠던 알고리즘에서 문제가 나오기에 그것으로 풀면 어찌저찌 테스트 케이스는 통과 하도록 만들어 제출했던 기억이난다.

 

제한시간나 메모리 제한을 통해 적합한 알고리즘을 선택하거나 한다는 것은 생각조차 못했다.

 

어찌저찌 완성한 답변은 항상 시간제한이나 메모리에서 걸렸다. 더이상 시간복잡도나 메모리 제한을 무시할 수 없을것 같아 이번기회에 공부한 내용을 정리하고자 한다.

---

시간 복잡도 (TimeComplexity)

시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상할 수 있다.

 

표기법으로 대문자 O를 사용한다. 다양한 시간 복잡도가 많지만, 보통 Big-O만 사용한다.

 

입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법으로 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

 

시간 복잡도는 소스를 보고도 계산할 수 있는데, 아래 소스를 보고 시간 복잡도를 계산해보자.

 

아래 소스는 모두 1부터 N까지 합을 계산하는 소스다.

int sum = 0;

for (int i=1;i<=N;i++) {
	sum += i;
}

• for 루프에서 총 N번 돌기에 해당 소스는 O(N)의 시간복잡도를 가진다.

 

int sum = 0;

for(int i=1;i<=N;i++) {
  for(int j=1; j<=N; j++) {
    if(i == j) {
      sum += j;
      }
  } 
}

• 해당 소스는 N번의 루프안에 N번 반복되는 루프가 하나더 있음으로 총 O(N^2)의 시간복잡도를 가진다.

 

int sum =0;
sum = N*(N+1)/2;

• 위 소스들과 달리 N만 알면 단번에 합을 구할 수 있다. 때문에 O(1)의 시간복잡도를 갖는다.

 

모두 같은 결과를 도출하지만 시간복잡도는 1에서 N^2까지 다양한것을 볼 수 있다.

---

알고리즘들의 대표적인 시간 복잡도는 아래와 같다.

 

• O( 1 )

• O(lgN )

• O(N)

• O(NlgN )

• O(N^ 2 )

• O(N^ 3 )

• O( 2^N)

• O(N!)

 

그리고 알고리즘의 시간복잡도를 계산할 때, 상수가 있으면 빼고

 

두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버리고 계산한다.

 

아래 예시를 살펴보자.

 

• O(3N^2) => O(N^2)
• O(1/2 N^2) => O(N^2)
• O(5) => O(1)
• O(N^2 + N) => O(N^2)
• O(N^2 + NlgN) = O(N^2)

---

 

문제들을 보면 값의 범위 또한 같이 제공되는데, 알고리즘의 시간복잡도에 값 범위를 대입해보면 대략의 시간을 도출 해  낼수 있는데,  시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도라고 한다.

 

문제를 풀면서 풀이를 다 생각했음에도 번번히 시간에 걸려 통과못하는 경우가 많았는데, 다음부터 꼭 시간부터 계산하고 적합한 알고리즘을 먼저 생각해서 다풀고도 통과못하는 삽질을 줄여보자. ㅠ