알고리즘 선택의 기준_시간복잡도

취업 준비기간에 알고리즘 학습용 책을 구매했었는데, 문제풀이 참고용으로만 사용하여 "진짜" 학습을 하지는 못한 것 같아서 다시 천천히 공부해보려 한다. 목표는 매일 한 챕터씩 학습하고 정리하는 것이다. 

취업 이후 실무에서 작업을 하는 도중 마주치는 문제는 항상 단연코 '좀 더 빠르게', '메모리를 좀 더 효율적으로'일 것 같다. 나름 알고리즘을 열심히 풀어서 좀 한다고 생각했지만,,, 원리를 모르고 문제를 풀이하는 방법만 공부해왔던 것 같아서 다시 제대로 정리해보려 한다. 

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
모든 개발자들이 바라는 효율적인 알고리즘이란 쉽게 말하면 입력값이 커짐에 따라 증가하는 연산 시간의 비율을 최소화하는 것이다. 
일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 실제로 시간 복잡도를 정의하는 3가지 유형은 아래와 같다. 

1. 빅 - 오메가 표기법 : 최선일 때의 연산 횟수를 나타낸 표기법
2. 빅 - 세타 표기법 : 보통일 때의 연산 횟수를 나타낸 표기법
3. 빅 - 오 표기법 : 최악일 때의 연산 횟수를 나타낸 표기법

public class timeComplexityExample1 {
	public static void main(String [] args) {
    	//1~N 사이의 값 랜덤 선택
        int findNumber = (int)(Math.random()*N);
        for(int i=1; i<=N; i++){
        	System.out.println(i);
            break;
        }
    }
}

위의 코드를 예시로 들어보자면
빅 - 오메가 표기법을 사용하면 전체 경우의 수 N중에서 최선은 바로 수를 뽑는 경우이기 때문에 1이 될 것이다. 
빅 - 세타 표기법을 사용하면 전체 경우의 수 N중에서 보통은 딱 중간이 되므로 N/2가 될 것이다. 
빅 - 오 표기법을 사용하면 전체 경우의 수 N중에서 최악은 모든 경우의 수를 순회한 후 가장 마지막에 수를 뽑는 N이 된다.

보통 알고리즘을 고민한다는 것 자체는 특정한 문제를 효율적으로 해결하기 위함인데, 단위 테스트의 개수가 단 하나뿐이지는 않을 것이다. 어떠한 환경에서도 해당 문제를 해결할 수 있어야 하기 때문에 최선과 보통보다는 최악의 경우의수를 기점으로 시간복잡도를 고려하곤 한다.

간단한 문제를 하나만 보면서 적합한 알고리즘을 찾아보자. 
https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

위의 문제는 주어진 수를 오름차순으로 정렬하는 간단한 문제이다. 하지만 입력값의 범위가 백만이기 때문에 흔히 알고 있는 버블정렬을 사용할 경우 제한된 시간을 초과하고 말 것이다.
기본적인 정렬알고리즘을 아직 정리하지 않았지만, 추후에 마저 정리할 예정이므로 지금은 결과부터 말하고 가겠다. 기본적으로 버블정렬과 병합 정렬의 최악의 시간복잡도는 각각 O(n^2), O(nlogn)이 된다. 

오름차순의 경우 쉽게 생각할 수 있는 최악의 경우(데이터의 크기가 가장 큰 경우)는 내림차순으로 정렬되어 있는 수들을 오름차순으로 다시 정렬하는 경우이다. 이 때 수의 개수가 백만개라면 가장 최악이 될 것이다. 

제한된 시간 2초 안에 해결해야 한다는 말은 2억번의 연산안에서 어떠한 경우의수더라도 결과를 도출해야 한다는 뜻이된다.
--- 알고리즘 적합성 평가 ---
버블 정렬 : (1,000,000)^2 -> 1,000,000,000,000
병합 정렬 : 1,000,000 * log(1,000,000) -> 6,000,000
즉, 2억번의 연산안에 결과를 도출하기 위해서는 버블 정렬보단 병합정렬이 더 효율적인 알고리즘이라는 결론을 도출할 수 있다. 

여기에서 알 수 있는 한 가지는 특정 문제를 해결하기 위해서는 시간 복잡도를 분석하여 알고리즘을 선택해야 하는데, 이 기준으로 입력으로 주어지는 데이터의 크기(N)을 단서로 사용해야 한다는 것이다.

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다. O(n)이나 O(3n)은 크게 차이가 없다. 
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준이 된다.
   1. O(n^2 + 15n + 5) 이런 시간 복잡도가 있다고 했을 때, 거듭제곱 아래는 아무리 n이 커지더라도 제곱보다 커질 수 없기 때문에 무시해도 된다.
3. 가장 핵심은 내가 작성한 코드의 시간복잡도를 직접 계산할 수 있어야 한다는 점이다.
4.  

---

20240718

시간 복잡도 

• '입력 크기에 대해 얼마나 빠르게 실행되는가?' 를 나타낸 지표
• 최상/평균/최악 세가지 표기법이 있지만 보통 알고리즘에서 시간 복잡도는 최악인 O(N) 빅오 표기법을 사용

빅오 표기법

• 프로그램 동작 시간에 가장 큰 영향을 주는 값을 중심으로 시간복잡도 표기
  • 빅오 표기법은 표기로만 사용하고, 문제를 풀 때는 실제 연산 횟수를 계산하는 것이 좋다. 

예시 (계수는 버린다.)

시간복잡도(실제 연산 횟수)	빅오 표기법
f(n, m, k) = 3n^2 + 2m + 4k + 1000	O(n^2 + m + k)
f(n) = 10000	O(1)

문제에 자주 등장하는 시간 복잡도 

O(1) : 입력 크기가 수행 시간에 영향을 주지 않음. [수학 관련 문제]
O(log n) : 탐색 단계 마다 입력의 크기를  반으로 줄인다. [이분 탐색]
O(n) : 선형 탐색의 시간으로 입력의 크기만큼 수행한다. [대부분 문제는 입력을 최소 1회 탐색해야 하므로 가장 효율적]
O(n^k) : 중첩 for문 / 특수한 재귀도 포함. [조합 nCk의 시간 복잡도]

공간 복잡도

• 프로그램이 얼마나 많은 메모리 공간을 사용하는지 나타내는 지표
• 마찬가지로 빅오 표기법으로 사용하며, 문제를 풀이할 때 시간복잡도 만큼 크게 고려할 사항은 아님

백준 문제 제출 기준 허용 공간 

시간복잡도 : 1초에 1억번의 연산
공간복잡도 : int 자료형 기준 1MB = 100만 개의 메모리 공간

시간 제한이 n초 일때, 나의 풀이가 n*1억 번 이하의 연산이 나온다면 시간 초과가 나지 않을 확률이 높다. 
나의 풀이가 5000만개 이하의 공간을 할당하는 코드라면 메모리 초과가 나지 않을 확률이 높다.