[알고리즘] Time Complexity와 Greedy

이제 알고리즘과 코딩 테스트 준비가 시작되었다.
이게 맞나 싶다.

우선 알고리즘을 생각할 때 가장 중요한건 문제를 이해하고 -> 전체적인 흐름을 확인해서 전략을 세우고 -> 코드를 작성하는 것이다.
이런 과정을 위해 의사코드 (pseudocode)를 작성하는 것이다.

의사 코드는 구체적으로 써야한다. 사람이 소통하기 위해 작성하는 이유도 있지만, 작성한 의사코드를 바탕으로 컴퓨터에게 명령할 것이기 때문이다.

Time Complexity (시간 복잡도)

문제 해결을 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려해야한다.
입력 값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지 고려해야한다는 것이다.
Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타) 이렇게 3가지 방법이 있는데, 이중에서
Big-O(빅-오) 표기법을 가장 자주 사용한다.

Big-O 표기법이 최악의 경우를 고려하는 것이기 떄문이다. 최소한 n시간 걸린다, 아니면 이정도 걸릴 것으로 예상된다 하는 것보다 최대 이정도 시간까지 걸릴 수 있다. 를 고려해야 최악에 상황에 맞는 대응이 가능하기 때문이다.

Big-O 표기법에는 다음과 같은 종류가 있다.

• O(1) : 입력 값이 증가해도 시간이 늘어나지 않는다. (입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다는 말이다.)

//예시 
public int O_1_algorithm(int[] arr, int index) {
  return arr[index];
}

int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = O_1_algorithm(arr, index);
System.out.println(results); // 2

• O(n) : 입력 값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 말한다.
  ex) 입력이 1일때 1초 , 입력이 100일 때 100배인 100초가 걸리는 알고리즘을 구현했으면 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 한다.

• O(log n) : O(1) 다음으로 빠른 시간 복잡도를 가진다.
  ex) BST의 값 탐색도 같은 로직

• O(n^2) : 입력 값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 말한다.

//예시 
public void O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			// do something for 1 second
		}
	}
}

public void another_O_quadratic_algorithm(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
				// do something for 1 second
			}
		for(int k = 0; k < n; k++) {
				// do something for 1 second
			}
		for(int l = 0; l < n; l++) {
				// do something for 1 second
			}
		}
	}
}

• O(2^n) : 가장 느린 시간 복잡도를 가진다. 그래서 내가 구현한 알고리즘의 시간 복잡도가 O(2^n)라면 다른 접근방식을 고민해보자..
  ex) 피보나치 수열

Greedy (탐욕 알고리즘)

선택이 필요할 때마다 당장의 최적의 상황으로 최종적인 해답에 도달하는 방법을 말한다.
Greedy로 문제를 해결하려면 다음과 같이 구분할 수 있다.

• 1) 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택.

• 2) 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검색.

• 3) 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

  greedy알고리즘을 사용하는 대표적인 예로, 거스름돈을 줄 때나 어떤 가방을 채울 때를 생각하면 된다.

오늘 위의 과정을 공부하고 페어와함께 알고리즘 문제를 풀었는데, 개털렸다.
총 4개 문제중에 1~3은 영차영차 풀었는데, 4번을 딱 보자마자 wow를 외쳤다.
배열에 들어온 값들을 이용해 target양을 채우기위해 나오는 경우의 수를 확인하는 문제였는데, 이게 배열 수와 target 제한이 100이하이다보니 여태까지 했던거처럼 하나하나 확인하고 넣어줄 수가 없었다.
내가 생각한 알고리즘이 O(2^n)의 시간복잡도를 가지는 것이 아니었을까 생각한다...
그래서 결국엔 GG치고 구글링과 해답을 보면서 풀었지만.. 아직은 혼자하라고하면 못할 것같다..
정말 지치는 밤이다..