TIL 32 (시간복잡도) (2021.11.09)

-오늘의 코플릿 2021.11.09-
2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 합니다.
인자 1 : matrix
가로 길이(matrix[i].length)와 세로 길이(matrix.length)가 모두 N인 2차원 배열matrix[i][j]는 number 타입
2차원 배열을 리턴해야 합니다.
Advanced
세로와 가로의 길이가 각각 M, N인 2차원 M X N 배열을 시계방향으로 90도씩 K번 회전시킨 배열을 리턴해 보세요. 회전수가 두 번째 입력으로 주어집니다.

// 90도로 회전시키면 각 행의 0번째 요소가 리턴되는 새로운 matrix 0번째 행의 요소들이 된다.
// 각 행의 1번째 요소가 1번째 행의 요소들이 된다.
// 행의 길이만큼 반복문을 돌려서 집어넣어준다.

첫 수도코드를 기반으로 advanced까지 구현한 코드입니다. 1번 회전하는 코드는 금방 구현할 수 있었는데, advanced로 rotation이 입력될 경우를 구현할 때, while을 써보면 어떨지에 대해서 고민해봤습니다. 근데 생각보다 쉽게 구현되지가 않아서 아래와 같이 코드를 구현하게 되었습니다. 추후에 더 학습하여서 코드를 간단하게 짤 수 있도록 노력해보겠습니다.

const rotateMatrix = function (matrix, rotation) {
	// 빈배열이 matrix로 들어왔을 경우, 빈 배열을 리턴한다.
    if ( matrix.length === 0 ) {
      return [];
    }
    
    // 리턴할 새로운 matrix를 만든다.
    let newMatrix = [];
    // rotation만큼 회전하기 위해서 count를 만들어준다.
    let count = 1;
    
    
    for ( let n = 0; n < matrix[0].length; n++ ) {
      let result = [];
      for ( let j = 0; j < matrix.length; j++ ) {
      // 각 행의 n번째 요소들을 먼저 result에 넣어준다.
        result.unshift(matrix[j][n])
      }
      // 모든 행의 n번째 요소들을 result에 넣었다면,
      // 리턴해줄 matrix에 push해준다.
      newMatrix.push(result)
      // 다음 요소들을 넣기 위해 result 를 빈배열로 만들어준다.
      result = [];
    }
    
    // advanced를 풀기 위해서 rotation이 입력이 안될 경우와, rotation과 count가 같을 경우
    // newMatrix를 리턴한다.
  if ( rotation === undefined || rotation === count ) {
    return newMatrix
  }
  else {
  // rotation만큼 돌지 못했다면, 1씩 빼면서 반복해준다.
    return rotateMatrix(newMatrix, rotation - 1)
  }
};

 

---

시간복잡도

Big-O 표기법

시간 복잡도를 표기하는 방법은 다음과 같습니다.

• Big-O(빅-오)
• Big-Ω(빅-오메가)
• Big-θ(빅-세타)

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법입니다.

 

빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문입니다.

 

"최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능합니다.(최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하기에 다른 표기법보다 Big-O 표기법을 많이 사용합니다.)

 

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법입니다.

---

O(1)

 O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다.

다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미입니다.

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

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

---

O(n)

O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미합니다. 예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있습니다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가합니다. 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있습니다.

 

another_O_n_algorithm 함수는 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가합니다.

하지만 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기합니다.

---

O(log n)

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다.

이진탐색트리(BST)를 이용할 경우, 매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 됩니다. BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)입니다.

---

O(n2)

O(n2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다. 예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

n3과 n5 도 모두 O(n2)로 표기합니다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기합니다.

---

O(2n)

O(2n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다. 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋습니다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘입니다.

 

---

데이터 크기 제한 & 예상되는시간 복잡도

n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)

입력 데이터가 클 경우에는 
O(n) or O (logn)의 시간 복잡도를 만족할 수 있도록 알고리즘 문제를 해결하고, 입력 데이터의 크기가 작을 경우에는, 시간 복잡도가 큰 것에 집중해서 시간복잡도를 낮추기 위해 많은 시간을 투자하는 거보다 문제를 해결하기 위해 고민해보자.

---

Greedy Algorithm

 

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다. 탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있습니다.

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다.

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다.

 

따라서 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못합니다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 합니다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있습니다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있습니다.

---

Dynamic Programming(DP; 동적 계획법)

 

탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식입니다.

 

Dynamic Programming의 원리

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식

 

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄입니다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.

다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있습니다.

• 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems)
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)

첫 번째 조건

큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다 (Overlapping Sub-problems)

=> 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다 는 말과 같습니다.

 

두 번째 조건

작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다(Optimal Substructure)

=> 이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미합니다.

따라서 두 번째 조건을 달리 표현하면, 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 합니다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있습니다.

---

Recursion + Memoization

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용합니다. 이때 결과를 저장하는 방법을 Memoization이라고 합니다. Memoization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술 입니다.

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

---

Iteration + Tabulation

이번에는 반복문을 이용하여 다이내믹 프로그래밍을 구현합니다.

하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 재귀 함수를 이용한 방법과 같습니다. 그러나 재귀 함수를 이용한 방법이 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법입니다. 따라서 이 방식을 Bottom-up 방식이라 부르기도 합니다.

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

---

크롬 개발자 도구에서 함수 실행 시간 측정 방법

함수의 실행 시간을 측정하는 방법은 여러 가지가 있습니다. 그중에서 다음의 방법으로 간단하게 함수의 실행 시간을 확인할 수 있습니다. 실행 환경에 따라 결과가 다르므로 측정 결과는 학습 용도로만 사용하세요.

var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')

---

짐 나르기
김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.
예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.
박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.
짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

function movingStuff(stuff, limit) {
    // TODO: 여기에 코드를 작성합니다.
  let currentStuff
  let count = 0
  // 최소 박스 수를 구하기 위한 변수
  let maxWeight = 0;
  // 가장 큰 무게를 달성하는 지 여부를 확인할 변수
  let idx;
  // splice하기 위한 인덱스

  while ( stuff.length ) {
    currentStuff = stuff.shift()
    // stuff 배열 중 첫번쨰 요소를 제거한다.
    for ( let n = 0; n < stuff.length; n++ ) {
    // 제거한 요소와 나머지 stuff 배열의 요소들 중, limit 이내이면서, 가장 무게가 많이 나가는 조합을 찾는다.
      if ( currentStuff + stuff[n] <= limit && currentStuff + stuff[n] > maxWeight ) {
        maxWeight = currentStuff + stuff[n];
        idx = n
      }
    }
    // idx에 값이 들어와있다면, splice해준다.
  if ( idx !== undefined ) {
      stuff.splice(idx, 1)
  }
  count++
  // 포장 가능 갯수는 1 올리고,
  // maxweight, idx는 초기화
  maxWeight = 0
  idx = undefined
  }
  return count;
}

---

편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다. 현재 가지고 있는 동전은
1원, 5원, 10원, 50원, 100원, 500원
으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다. 동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.
number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.

function partTimeJob(k) {
    // TODO: 여기에 코드를 작성하세요.
    let result = 0
    let coin = [500, 100, 50, 10, 5]
    // 거슬러 줄 수 있는 동전들을 배열로 만든다.
    // 1원은 따로 계산하지 않고, 맨 마지막에 남는 만큼 거슬러 주는 동전 갯수에 더할 예정

    while( k > 5 ) {
    // k가 5원 밑으로 떨어질 때까지 빼준다 => 1원 단위는 계산하지 않는다.
        for (let n = 0; n < coin.length; n++ ) {
            let num = parseInt(k / coin[n]);
            // 해당 동전으로 k를 나눴을 때 몫을 구한다.
            k = k - coin[n] * num
            // 구한 몫만큼 해당 동전을 곱해서 k에서 빼준다.
            result = result + num
            // 몫은 동전의 갯수이니 리턴할 값에 더해준다.
        }
    }
    return result + k
    // 남은 1원 단위는 동전 갯수와 동일하니 더해준다.
}

=> 이 문제를 풀 때, 변수에다가 동전을 넣는 방식으로 구현을 했었는데, 코드가 너무 지저분했습니다. 다행스럽게도 배열을 생각해서 위와 같이 구현할 수 있었는데, 처음부터 배열을 생각하지 못한 점이 많이 아쉽습니다.

---

문제
N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.
좌표 왼쪽 상단(0, 0)에 말을 놓는다.말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.조작의 기회는 딱 한 번 주어진다.조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.예시: UDDLLRRDRR, RRRRR한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.방문한 곳을 또 방문해도 숫자를 획득할 수 있다.보드 밖을 나간 말은 OUT 처리가 된다.칸 안의 숫자는 0 또는 1이다.단, 좌표 왼쪽 상단(0, 0)은 항상 0이다.획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.
보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.
만약, 말이 보드 밖으로 나갔다면 즉시 OUT 을 반환합니다.

function boardGame(board, operation) {
    // TODO: 여기에 코드를 작성하세요.
    let sum = 0;
    let m = 0;
    let n = 0;
    let arr = operation.split('')
  
    while( arr.length ) {
      let current = arr.shift();
      if ( current === 'U' ) {
        m = m - 1
        if(board[m] !== undefined) {
          sum = sum + board[m][n]
        }
        else {
          return 'OUT'
        }
      }
      if ( current === 'D' ) {
        m = m + 1
        if(board[m] !== undefined) {
          sum = sum + board[m][n]
        }
        else {
          return 'OUT'
        }
      }
      if ( current === 'R' ) {
        n = n + 1
          if(board[m][n] !== undefined) {
          sum = sum + board[m][n]
        }
        else {
          return 'OUT'
        }
      }
      if ( current === 'L' ) {
        n = n - 1
        if(board[m][n] !== undefined) {
          sum = sum + board[m][n]
        }
        else {
          return 'OUT'
        }
      }
    }
    return sum;
  };

=> 해당 문제는 단순하게 생각해서 조건문을 걸어주고 board상에 존재하지 않는다면, OUT를 리턴하고, board 내부라면 진행을 했습니다. 이 방법으로 구현은 쉬웠지만, 코드가 너무 지저분 한 것 같아 레프런스를 통해서 추가적으로 학습을 해보았습니다.

function boardGame(board, operation) {
  // TODO: 여기에 코드를 작성하세요.
  const DIR = {
    'U': [-1, 0],
    'D': [1, 0],
    'L': [0, -1],
    'R': [0, 1]
  }
  const LEN = board.length;
  const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;

  let Y = 0;
  let X = 0;
  let score = 0;
  for (let i = 0; i < operation.length; i++) {
    const [dY, dX] = DIR[operation[i]];
    Y += dY;
    X += dX;
    if (isValid(Y, X) === false) return 'OUT';
    score += board[Y][X];
  }
  return score;
};

제가 구현한 코드의 장황한 if문을 DIR로 정리를 하고, 구조분해할당을 한 점에서 부족함을 느낄 수 있었습니다. 해당 방법뿐만 아니라 다양한 방법에 대해서 학습하고 직관적이고 간결한 코드를 구현할 수 있도록 노력해야겠습니다.