211006 CodeStates 53일차

오늘부터 이틀간 알고리즘에 대하여 공부한다.
오늘은 알고리즘과 시간복잡도에 대한 정의를 살펴보고, Greedy 알고리즘과 Dynamic Programming이 무엇이고 어떻게 적용할 수 있는지를 공부했다.
개념을 공부한 후에는 페어분과 함께 공부했던 개념들을 적용하여 문제를 푸는 시간을 가졌다.

알고리즘과 시간복잡도

알고리즘은 문제를 해결하는 최선의 선택이다.
개발자가 되기 위해서는 새로운 문제에 봉착했을 때, 전략과 알고리즘을 구상하여 실제로 코드를 구현하는 경험이 매우 중요하다.
컴퓨터의 문제해결방식과 알고리즘을 이용해 최선의 선택을 찾을 수 있어야한다.

시간복잡도

시간복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 의미한다.
효율적인 알고리즘을 구현한다는 것은 다시말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구현한다는 의미이다.

시간복잡도는 다음과 같이 세가지 방법으로 표기할 수 있다.

• Big-O(빅오표기법): 최악의 경우에 대한 시간복잡도
• Big-Ω(빅-오메가): 최선의 경우에 대한 시간복잡도
• Big-θ(빅-세타): 평균의 경우에 대한 시간복잡도

빅오표기법은 최악의 경우를 고려한 시간복잡도이기에, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.
"최소한 특정시간 이상 걸린다"처럼 최솟값(최선의 경우)을 중점으로 고려하는 것보다는 "이 정도 시간까지 걸릴 수 있다"처럼 최댓값(최악의 경우)을 중점으로 고려하는 것이 그에 맞는 대응이 가능하기 때문에 빅오표기법이 가장 자주 사용된다.

Big-O Notation(빅오표기법)

빅오표기법은 "입력값의 변화에 따라 연산을 실행할 때, 연산횟수에 비해 시간이 얼마만큼 걸리는가?" 를 표기하는 방법이다.
빅오표기법으로 시간복잡도를 표기할 때 최고차항만을 고려하며 이때 최고차항의 계수도 무시한다.
예를들어 입력값 n에 대해 $3n^2+2n+3$

• $O(1)$
  $O(1)$은 constant complexity라고 부르며, 입력값이 증가하더라도 연산에 걸리는 시간이 증가하지 않는다.(시간이 일정한 상수값을 갖는다)
  입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있다.
  아래의 함수는 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.
  (arr의 길이가 100만이고, index가 50만이어도 즉시 해당 index에 있는 값을 반환할 수 있다.)

function O_1_algorithm(arr,index){
  return arr[index];
}

• $O(n)$
  $O(n)$은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간또한 같은 비율로 증가하는 것을 의미한다.
  입력값이 1일때 1초가 걸리고, 입력값이 100일때 100초의 시간이 걸리는 알고리즘은 $O(n)$의 시간복잡도를 갖는다고 할 수 있다.
  $O(n)$의 시간복잡도를 갖는 알고리즘을 선형시간 알고리즘이라 한다.
  아래의 함수는 arr배열을 순회하며 최댓값을 찾는 함수이다.
  배열의 크기가 커질수록 걸리는 시간도 그에 비례하여 증가한다.

function O_n_algorithm(arr){
  let max=arr[0];
  for(let i=1;i<arr.length;i++){
    if(arr[i]>max){
      max=arr[i];
    }
  }
  return max;
}

• $O(log$ $n)$
  $O(log$ $n)$은 logarithmic complexity라고 부르며, O(1)다음으로 빠른 시간복잡도를 갖는다.
  이진탐색이 $O(log$ $n)$의 시간복잡도를 갖는다.

• $O(n$ $log$ $n)$
  $O(n$ $log$ $n)$은 병합정렬과 같은 효율좋은 정렬 알고리즘이 이에 해당된다.
  적어도 모든수에 대해 한번 이상은 비교해야하는 비교기반 정렬 알고리즘은 $O(n$ $log$ $n)$보다 빠를 수 없다.

• $O(n^2)$
  $O(n^2)$는 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱의 비율로 증가하는 것을 의미한다.
  예를들어 입력값이 1일 경우, 1초가 걸리는 알고리즘이 입력값이 5가 되었을 때, 25초가 걸린다면 이는 $O(n^2)$의 시간복잡도를 가진 알고리즘이라 할 수 있다.
  버블정렬과 같은 비효율적인 정렬 알고리즘이 이에 해당된다.

• $O(2^n)$
  $O(2^n)$은 exponential complexity라고 부르며, 빅오표기법중 가장 느린 시간복잡도를 갖는다.
  입력값이 1증가할 때마다 이전에 비해 시간이 2배씩 증가하는 것을 의미한다.
  재귀를 이용해 피보나치 수열을 구하는 알고리즘이 $O(2^n)$의 시간복잡도를 갖는 대표적인 알고리즘이다.
  

Greedy Algorithm

Greedy는 "탐욕스러운,욕심많은"이란 의미의 단어이다.
Greedy Algorithm은 말 그대로 선택을 해야하는 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
Greedy Algorithm을 다음과 같이 단계적으로 구분할 수 있다.

• 선택절차: 현재상태에서 최적의 답을 선택한다.
• 적절성 검사: 선택된 답이 문제의 조건을 만족하는지 검사한다.
• 해답검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 다시 선택절차로 돌아가 위의 과정을 반복한다.

동전으로 거스름돈 160원을 거슬러줘야할 때, 동전의 갯수를 최소화하고 싶다면 어떻게 해야할까?

• 선택절차: 동전의 종류는 10원, 50원, 100원이므로 가장 가치가 큰 100원부터 선택한다.
• 적절성검사: 선택절차에서 선택된 동전의 갯수를 1씩 늘려가며 거슬러줘야하는 금액을 초과하는지 검사한다.
  만약 초과한다면 마지막으로 늘린 동전을 삭제하며 다시 선택절차로 돌아가 그 다음으로 큰 동전을 선택한다.
• 해답검사: 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다.
  액수가 부족하다면 다시 선택절차부터 반복한다.

위의 과정을 거치면 100원 1개, 50원 1개, 10원 1개 총 동전 3개로 160원을 거슬러 줄 수 있다.

Greedy Algorithm은 문제를 해결하는 과정에서 매 순간마다 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종문제의 해답에 도달하는 문제해결방식이다.
하지만 항상 최적의 결과를 보장하지는 않는다.

위의 거스름돈 문제에서 만약에 기존의 동전들과 새로운 80원짜리 동전이 존재한다고 가정하면, 최적의 답은 80원짜리 동전 2개로 거스름돈을 거슬러주는 것이 동전의 수를 최소화하는 최적의 결과일 것이다.
하지만 위의 방법대로 100원, 80원, 50원, 10원의 순서대로 검사를 하는 Greedy Algorithm은 최적의 답에 도달할 수 없다.

Greedy Algorithm은 다음 조건들을 만족하는 특정한 상황에서만 최적의 해를 보장한다.

• 탐욕적 선택속성: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적부분구조: 문제에 대한 최종해결방법은 부분문제에 대한 최적 문제해결방법으로 구성된다.

항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 구할 수 있다는 점이 Greedy Algorithm의 큰 장점이다.

Dynamic Programming(동적계획법)

Dynamic Programming은 주어진 문제를 여러개의 하위 문제로 나누고, 하위 문제들의 해결방법을 결합하여 최종문제를 해결하는 문제해결방식이다.
Dynamic Programming은 Greedy Algorithm과 비슷하게 작은 문제에서 출발한다는 점은 같으나, Greedy Algorithm이 매 순간 최적의 선택을 쫓는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 해답을 찾는 방식이다.

다음 두가지 조건을 만족하는 상황에서 Dynamic Programming을 적용하여 문제를 해결할 수 있다.

• 큰문제를 작은 문제로 나눌수 있고, 이러한 작은 문제가 중복해서 발견된다.
  큰 문제로 나누어진 작은 문제는 큰 문제를 해결할 때 여러번 반복해서 사용될 수 있어야한다.
  전에 재귀를 배우며 피보나치 수열에 대해 블로그에 정리할 때의 그림이다.
  
  fib(5)를 구하기 위해서는 fib(4)와 fib(3)을 구해 더해줘야하고 fib(3)은 트리의 오른쪽부분에서 fib(4)를 구할때에도 필요하기 때문에 동일한 계산을 반복해야한다.
  이렇게 작은문제(fib(3))가 큰 문제를 해결하기 위해 여러번 반복하여 사용할 수 있을 때, 부분문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.

• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)
  조건에서 말하는 정답은 최적의 해결방법을 의미한다.
  주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법을 찾아야한다.
  그렇게 찾은 작은 문제들의 최적의 해법을 결합하면, 결국 전체문제의 최적의 해법을 구할 수 있을 때, 해당 조건을 만족한다.
  
  
  

오늘 Dynamic Programming을 구현할 때 1)재귀를 이용하는 방법과 2)반복문을 이용하는 방법을 배웠다.

• Recursion+Memoization
  재귀를 이용해 큰 문제를 작은 문제들로 나누어 문제를 해결한다.
  작은문제들의 정답을 저장한 후, 동일한 작은문제가 나왔을 경우 저장해놓은 정답을 이용한다.
  이때 작은문제의 정답을 저장한느 방법을 Memoization이라고 한다.
  동일한 계산을 반복하지 않고 저장된 값을 이용하기 때문에 반복된 계산횟수를 줄여 실행속도를 빠르게 할 수 있다.

// 재귀와 memoization을 이용한 피보나치 수열
function fibMemo(n,memo=[]){
  if(n<2){
    return 1;
  }
  if(memo[n]===undefined){
    memo[n]=fibonacci(n-1,memo)+fibonacci(n-2,memo);
  }
  else{
    return memo[n];
  }
}

• Iteration+Tabulation
  반복문을 이용하여 Dynamic Programming을 구현하는 방법이다.
  작은문제의 결과값을 배열에 저장하고 필요할 때 조회하여 사용하는 것은 재귀를 이용하는 방식과 같다.
  하지만 재귀를 이용한 방식은 큰문제에서 작은문제로 나누어가며 문제를 해결해 나갔다면, 반복문을 이용한 방식은 작은문제에서 시작하여 큰문제를 해결하는 방식이다.

// 반복문을 이용한 피보나치 수열
function fibIter(n){
  let fibNum=[1,1];
  for(let i=2;i<=n;i++){
  	fibNum[i]=fibNum[i-1]+fibNum[i-2];
  }
  return fibNum[n];
}

완전탐색

완전탐색이란 문제를 풀때 가능한 모든 경우의 수를 검사해보는 방법이다.
모든 경우의 수를 찾아 검사하는 코드를 작성하게 되면 문제의 정답을 무조건 찾아낼 수 있다는 장점이 있지만 효율적인 측면에서는 상당히 불리해진다.
오늘 크루님의 말을 들어보니 대부분의 알고리즘 문제들의 실행시간은 1초로 정해져있다고 한다.
1초에 보통 1억번의 연산을 수행할 수 있으며 빅오표기법의 시간복잡도와 문제의 조건에서 입력값의 범위를 파악하여 대략적으로 1억번의 연산안에 해결될 수 있다면 완전탐색을 사용해도 큰 지장은 없을 듯하다.
알고리즘 문제를 풀때 왠만하면 완전탐색은 처음에는 배제한후 다른 방법이 모두 사용 불가능할 때, 사용하는 것이 바람직할 것 같다.