[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 3

Ch 03. 알고리즘의 효율 분석

시간 복잡도란?

• 문제를 빠르게 푸는 알고리즘이란?
  • 시간 복잡도로 판별한다.
  • 시간 복잡도란?
    • 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다.
    • 시간 복잡도는 낮으면 낮을수록 좋다.
  • 입력 크기란?
    • 알고리즘이 처리해야할 데이터의 양
• 알고리즘 수행 시간을 측정하는 방법
  • 절대 시간을 측정하는 방법과 시간 복잡도를 측정하는 방법이 있다.
  • 절대 시간을 측정하는 방법 : 시간을 측정하면 된다.
  • 시간 복잡도를 측정하는 방법 : 
    • 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타낸다. (최선, 보통, 최악)
    • 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내야 한다.
    • 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 접근적 표기법이라고 한다.
    • 코딩 테스트에서는 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로 시간 복잡도는 최악의 경우를 가정하여 이야기하는 것이 일반적이다.
• 최악의 경우 시간 복잡도를 표현하는 빅오 표기법
  • 가장 많이 사용하는 점근적 표기법은 상한성을 활용하는 방법이다. 그리고 이 방법을 빅오 표기법이라고 한다.
  • 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워 O(..)와 같이 표기한다.
  • 
• 예시
  n = x일 때 f(x) = x² + 3x +5가 있다면
  
  다음을 만족하는 C가 있으면 f(x)의 최악의 시간 복잡도는 O(g(x))라고 쓴다.
  - 특정 x 시점 이후부터 항상 f(x) <= C * g(x)를 만족
  - C는 상수
  
  쉽게 말해 g(x)에 상수 C를 곱했을 때 시점부터 f(x)를 넘어서는지 여부를 보면 된다.
  C가 2라면 g(x)는 x ²이다.
  x = 4부터 항상 2x²가 f(x)를 넘으므로 위 공식을 만족한다.
  
  한 마디로 최악의 수를 판별해서 시간 복잡도를 나타낼 수 있다는 뜻 같다.  
   
  • 빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 계수를 지울까?
    • x³, x², x 그래프를 비교했을 때 x는 x값이 무한하게 커지면 격차가 심해진다. 하지만 x²과 x³은 무시할 수 있을 정도로 격차가 작다.
    • 지수함수와 로그함수의 경우도 'x가 무한히 커진다'라는 것만 상상하면 쉽게 이해 가능하다.
    • 로그함수는 다항 함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가한다.
    • 그러므로 최고 차항만 남기는 작업에서 우선순위는 다음과 같다.

    • 

      

• 시간 복잡도를 코딩 테스트에 활용하는 방법
  • 코딩 테스트 문제는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있다.
  • 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있다.
  • "컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억번이다."라는 기준으로 알고리즘을 선택한다.
  • 코딩 테스트의 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유롭게 지정한다.
  • 따라서 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.
  • 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘을 사용하면 안된다.
  • 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 가용 범위는 다음과 같이 생각하면 된다.

  • 

  • 시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 된다.

 

시간 복잡도 계산해보기

• 문제 정의 -> 연산 횟수 측정 -> 시간 복잡도 분석 순서로 공부해야 한다.
• 예시) 박테리아 수명 문제
  • Y년 후의 박테리아의 수는 (½)^Y * N이다.
  • 최초로 1보다 작아질 때를 구하려면 (½)^Y * N <= 1인 Y를 찾으면 된다.
  • 정리하자면
    • (½)^Y은 ½^Y로 생각해 (½)^Y * N는 N/2^Y < 1이다.
    • 양변에 2^Y를 곱해 식을 정리하면 2^Y > N이고
    • 양변에 로그를 취하면 Y < log₂N이다.
  • 이를 통해 알고리즘은 O(log₂N)의 시간 복잡도를 가진다는 것을 알 수 있다.
• 앞으로 문제를 풀 때 특정 값을 계속 반으로 줄이는 동작을 한다면 시간 복잡도를 O(logN)이라 생각하면 된다.