오늘

• 시간 복잡도
• 알고리즘 접근법(greedy, dynamic programing)

지금

시간복잡도

먼저, 알고리즘을 간단하게 짚어보면
알고리즘과 자료구조은 간단 기능의 프로그램에서는 중요하지 않다.

하지만, 생각하는 힘을 기르기위한 운동이라고 생각 할 수 있다.

시간 복잡도란,

해당하는 프로그램이 실행되는 시간을 최소, 평균, 최대 값에 따라 지표로 나타내는 방식

시간 복잡도의 표기

• 최대 시간 : 빅-오 표기법 (문제를 해결하기 위한 최대한의 연산 횟수)
• 평균 시간 : 빅-세타 표기법 (빅-오와 빅-오메가의 중간값 => 평균 연산횟수)
• 최소 시간 : 빅-오메가 표기법 (문제를 해결하기 위한 최소한의 연산 횟수)

알고리즘을 실행하면서,
각각 알고리즘 내에서 데이터에 따라 처리하는 시간을 최대, 최소, 평균으로 나누어 표기하는 방법이다.

우리는 3가지 표기법 중 빅오 표기법(Big-O Notation)을 중점적으로 알아보게 된다.
최악의 경우를 고려하여 프그래밍이 하는 것이 안전하게 구동된다고 볼 수 있기 때문이다.

시간 복잡도의 크기

복잡한 순서에 따라 나누면,
O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(sqrt(x)) > O(logn) > O(1)
n^2, n^3등의 차수의 변화등은 무시한다. 데이터의 크기(n)가 충분히 크다면 무시할 정도이기 때문이다.
log의 밑또한 같은 이유로 무시한다. 그저 연산횟수에 따라 크게 나누어진다고 볼 수 있다.

시간 복잡도는 충분히 큰 데이터를 처리할 때 유효하다.

알고리즘 접근법

알고리즘은 자료를 처리하는 방식을 결정하는 것으로, 자료구조와 밀접한 관련이 있다.
오늘 찾아본 두 개의 접근 방법은 크게 사용되는 자료구조형식은 없지만, 해당 데이터를 처리하는 방법론이다.

그리디 (greedy)

탐욕적 선택 방식, 전체의 상황을 작은 단위로 나누어 각 단위 마다 가장 효율 적인 선택을 하는 방법

그리디는 탐욕이라는 뜻으로, 알고리즘 접근방식도 탐욕적 선택을 따른다.
전체 상황을 가장 작은 케이스로 나누고 해당 케이스에서 가장 효율적인 선택을 연속적으로 취해 원하는 결과를 산출하는 방식이다.

다음과 같은 특성이 있다.

1. 탐욕 선택 속성(greedy choice property) : 당장 최선의 답을 선택한다.
2. 최적 부분 구조(optimal substructure) : 부분의 해결이 곧 전체의 해결을 나타낸다. (재귀로 표현할 수 있다.)

그리디 알고리즘 예시

예를 들어,
식후에 디저트를 고르는 과정을 다음과 같이 정의해보자.

1. 나는 최대 5개의 디저트를 가질 수 있다.
2. 선택한 종류의 디저트를 모두 가져가야 한다.
3. 디저트는 다음과 같다.
   {과일:4, 아이스크림:1, 커피:1, 사탕:2}
4. 가장 많은 디저트를 선택하는 방법

해당 문제를 그리디로 풀이하게 된다면, 먼저 가장 많은 순서로 정렬한다 => {과일:4, 사탕:2, 커피:1, 아이스크림:1}
첫 번째 디저트를 선택한다 => 과일:4
그 다음으로 선택할 수 있는 디저트를 찾는다. => 커피 :1
선택한 디저트를 반환한다. => {과일 :4, 커피:1}

특징

위의 선택처럼 가장 많은 갯수의 디저트를 고르는 방법에서는 효과적이지만,
가장 많은 종류의 디저트를 고르는 선택에서는 그렇지 않다.

가장 많은 종류의 디저트를 선택하기 위해서는,
사탕(2), 커피(1), 아이스크림(1)을 선택할 수 있는 경우(3가지)가 있다.
가장 많은 종류를 선택해야 하는 경우에는 알맞지 않은 접근방법이다.

동적 프로그래밍 (Dynamic Programing)

문제 전체를 아주 작은 단위로 나누어 생각하고, 작은 단위의 문제를 해결하는 방식을 중첩하여 전체 문제에 접근하는 방식이다.
동적 계획법은 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.

가장 대표적인 예시로는 피보나치 수를 구하는 알고리즘이 있다.

const fiboTop = (n, fibos = [0,1,1]) => {
  if(n <= 2) return fibos[n];
  fibos[n] = fiboTop(n-1, fibos) + fiboTop(n-2, fibos)
  return fibos[n];
} // top-down

const fiboBot = (n, fibos = []) => {
  if(n <= 2) return 1;
  
  for(let i = 3; i <= n; i++) {
      fibos[i] = fibos[i-1] + fibos[i-2]
  }
  return fibos[i]
} //bottom-up

fiboTop(n)라는 함수는 n <= 2인 구간에서는 1을 반환하고,
숫자가 커짐에 따라서 n-1,n-2의 입력 결과를 반환한다.

결국 n<=2의 구간 결과를 가지고 연산한 답을 다시 연산하는 과정을 거친다.
이를 통해 우리가 원하는 n에 대한 피보나치 수를 찾을 수 있다.

memoization

지금처럼 결과를 저장하여 다음 연산에서 저장된 결과값이 있다면,
다시 연산하지 않고 실행에 적용할 수 있도록 사용하는 방식을
메모이제이션(memoization)이라고 한다.

내일

• 내일 수업
• 일찍 일어나기