220302 D+51 Algorithm, Time Complexity(시간 복잡도), greedy Algorithm, Implementation

1. 알고리즘(Algorithm)

: 문제를 해결하는 최선의 선택.

for문을 사용해도 되지만 배열 메소드 같은 경우는 지향하지 않음.

3. 코드부터 치지 말고 문제를 분석하는 데에만 사용할 것(생각처럼 잘 되지 않는 경우가 더 많을 수 있음).

 

① 문제를 이해한다.

→ 문제에서 주어진 조건을 토대로 문제가 무엇인지 이해하는 것부터 시작한다.

문제 푸는 시간의 3~50%는 문제 분석에 사용한다.

(for문을 사용해도 괜찮지만 배열 메소드 같은 경우엔 지향하지 않음)

 

② 문제를 해결하기 위한 전략을 세운다(코드부터 작성하려 하지 말 것).

→ 수도코드를 작성하기 전, 문제에 대해 생각하고 전체적인 그림을 그려간다.

→ 코드를 작성하기 전 수도코드를 먼저 작성한다.

 

③ 문제를 코드로 옮긴다.

→ 전략을 코드로 옮겨본다. 그렇게 구현한 코드의 최적화를 시도한다.

입력과 공간 상한을 확인한 후, 완전탐색으로 문제를 풀어본다(알고리즘이 바로 떠올랐다면 그렇게 풀어도 무방함).

 

✷ 기본적으로 알아두어야 할 유형

(꼭 외울 것, 코테 직전에 템플릿 보고 갈 것)

① GCD

② 순열 / 조합

③ 정렬은 Array.prototype.sort 사용할 것(최적화가 이미 다 되어있음)

④ DFS(재귀) / BFS(큐)

⑤ 분할정복(재귀), DP

⇒ 난이도 상, 감 잡는 것이 어렵기 때문에 케이스 스터디 필요

(Geeksforgeeks 같은 곳에 들어가서 기본 템플릿을 보고 스터디할 것)

 

 

2. 시간 복잡도(Time Complexity)

: 입력값과 실행되는 시간이 비례함이 어느 정도인지 나타내는 것.

: 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가

⇒ 효율적인 알고리즘을 구현하는 것.

→ 대부분의 문제는 실행 시간: 1초(1억 번의 연산당 1초)에 가깝게 디자인된다.

 

✷ 1초가 걸리는 입력의 크기(암기할 것)

‣ O(n): 100,000,000

‣ O(nlogn): 5,000,000

‣ O(n²): 10,000

‣ O(n³): 500

‣ O(2ⁿ): 26

‣ O(n!): 11

 

ex)

1 <= n <= 10만 일 때 걸리는 시간

O(1) 1 : 1e-8초

O(n) 10만 : 0.01초

O(n²) 100억 : 100초(불가능, O(n) 또는 그 이하로 풀어야 함) 

 

✷ 공간 복잡도

: JS에서 보통 변수 하나는 8 byte이다.

일반적으로 알고리즘 문제에서 128 / 256 / 512MB가 자주 등장한다.

 

KB = 1000 byte

MB = 1000K = 100만 byte

GB = 1000M = 10억 byte

(시간 복잡도를 통과하면 공간 복잡도는 대부분 통과하지만,

만약 공간 복잡도를 통과하지 못하면 메모리를 차지하는 배열 같은 것들이 있을 수 있음)

 

시간 복잡도를 표기하는 방법에는 빅-오메가, 빅-세타, 빅-오가 있다.

여기서는 빅-오 표기법에 대한 내용이 주를 이룬다.

 

‣ Big-Ω(빅-오메가)

: 최선의 경우를 고려하여 나타내는 방법.

 

‣ Big-θ(빅-세타)

: 중간(평균)의 경우를 고려하여 나타내는 방법.

 

① Big-O(빅-오)표기법

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

→ 최악의 경우도 고려하여 나타내는 방법.

→ 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.

→ 이 정도 시간까지 걸릴 수 있다 라는 것을 고려하는 것.

 

‣ O(1) (constant complextiy)

 : 입력값이 증가하더라도 시간이 늘어나지 않음.

→ 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있음.

// O(1) 시간 복잡도를 갖는 알고리즘의 예시
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

// arr의 길이와 무관하게 즉시 해당 index 값에 접근하여 값을 반환할 수 있음.

 

‣ O(n) (linear complexity)

: 입력값이 증가함에 따라 시간도 같은 비율로 증가하는 것.(for문이 한 번 돌아간다는 것을 알 수 있음)

// O(n) 시간 복잡도를 갖는 알고리즘 예시
// 입력값이 1 증가할 때마다 코드의 실행시간이 1초씩 증가
// n이 커질수록 계수(n 앞에 있는 수)가 주는 영향력이 퇴색되기 때문에
// 같은 비율로 증가하고 있다면 2배, 5배, 10배로 증가해도 O(n)으로 표시한다.
function O_n_algorithm(n) {
  for (let i = 0; i < n; i++) {
  // do something for 1 second
  }
}

// 입력값이 1 증가할 때마다 코드의 실행시간이 2초씩 증가
function another_O_n_algorithm(n) {
  for (let i = 0; i < 2n; i++) {
  // do something for 1 second
  }
}

‣ O(log n) (logarithmic complexity)

: O(1) 다음으로 빠른 시간 복잡도를 가짐.

→ BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. up & down을 예로 들 수 있다.

1~100 중 하나의 숫자를 플레이어1이 30을 골랐다고 가정합니다.
50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
1 ~ 50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
25보다 크므로 up을 외친다.
경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있다.

BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

 

‣ O(n²) (quadratic complexity)

: 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것.

(for문이 2번 돌아간다는 것을 알 수 있음)

⇒ 최대한 여기서 해결할 수 있으면 좋음

// O(n²) 시간 복잡도를 갖는 알고리즘 예시
// n이 커질수록 지수가 주는 영향력이 퇴색되므로 모두 O(n²)으로 표기함
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
      }
    }
  }
}

‣ O(n³)

: 입력값이 증가함에 따라 시간이 n의 세제곱수의 비율로 증가하는 것.

(for문이 세 번 돌아간다는 것을 알 수 있음)

 

‣ O(2ⁿ) (expotential complexity)

: 가장 느린 시간 복잡도를 가짐.

// O(2ⁿ) 시간 복잡도를 갖는 알고리즘 예시
// 우리가 잘 알고 있는 재귀로 구현한 피보나치 수열
// n이 100 이상이면 평생 결과를 반환받지 못할 수도 있음.
function fibonacci(n) {
  if (n <= 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

② 입력데이터가 클 때와 작을 때

‣ 입력 데이터가 클 때는 O(n) / O(log n)의 시간 복잡도를 만족할 수 있도록 예측한다.

‣ 입력 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 푸는 것에 집중할 것.

 

✷ 데이터 크기에 따른 시간 복잡도

데이터 크기 제한	예상되는시간 복잡도
n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)

 

3. greedy Algorithm(탐욕 알고리즘)

: 문제 해결 과정에서 매순간 최적이라 생각되는 해답(locally optimal solution)을 찾으며 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식.

→ 항상 최적의 결과를 보장하지는 못하지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있어 근사 알고리즘으로 사용할 수 있음.

→ 탐욕 알고리즘은 탐욕적 선택 속성(Greedy Choice Property / 앞의 선택이 이후의 선택에 영향을 주지 않음)과 최적 부분 구조(Optimal Substructure / 문제에 대한 최종 해결 방법: 부분 문제에 대한 최적 문제 해결 방법으로 구성)과 같은 두 가지 조건을 성립하여야 적용할 수 있다.

 

✷ Coin Change Algorithm(동전 교환 알고리즘)

: 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘.

→ 거스름돈은 가장 적게 내어주면서도 그것에 맞는 경우의 수를 구하는 알고리즘.

1. 선택한 동전의 결과를 저장할 배열을 초기화한다.
2. 구해야하는 값보다 작은 동전 중 가장 큰 동전을 찾는다.
3. 발견된 동전을 결과에 추가한다. 추가한 동전의 금액을 구해야하는 값에서 차감한다.
4. 구해야하는 값이 0이 되면 결과를 리턴하고,
그렇지 않으면 구해야하는 값의 새 값에 대해 2,3단계를 반복한다.

4. Implementation

① 알고리즘 문제를 푼다 === 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다

‣ 정렬: N개의 숫자들을 특정한 기준에 맞게 순서를 조정하는 것.

‣ 그래프 탐색 - 탐색 방식에 따른 카테고라이징. DFS / BFS.

⇒ 각 카테고리는 원하는 의도가 분명히 있고, 내가 생각한 로직을 코드로 구현한다.

 

② 완전 탐색

: 가능한 모든 경우의 수를 전부 탐색하여 문제를 푸는 방식.

→ 답이 무조건 있기 때문에 문제를 해결할 수는 있지만 효율적으로 동작할 수 없는 경우가 있다.

→ 무차별 대입, 재귀, 순열, DFS, BFS 등이 있음.

 

‣ 무차별 대입(brute force): 조건 / 반복을 사용하여 해결하는 방법.

 

ex)

세 명의 아이들이 있습니다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다.

먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고,

좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다.

 

세 아이의 식성은 이렇습니다.

첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)

둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)

셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)

 

100 개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때,

가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요?

단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.

 

// 단순히 100 개의 반찬을 첫째, 둘째, 셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다.

for(let i = 0; i < 100; i++) {
  if(첫째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(둘째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(셋째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
}

return 많이 먹은 아이;

// 각각 몇 가지 음식을 얼마나 먹을 수 있는지 각각 계산한 후, 
// 제일 많이 먹는 아이와 제일 적게 먹는 아이를 파악할 수 있다. 
// 문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 
// 간결한 코드를 위한 문법을 사용한다고 하더라도 
// 배열을 전부 탐색하여 세 명의 값을 도출한다는 것엔 변함이 없다.

 

③ 시뮬레이션(simulation)

: 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 시뮬레이션 하는 것과 동일한 모습을 그린다.

→ 모든 과정과 조건이 제시되어 그 과정을 거친 결과가 무엇인지 확인하는 유형.

 

무엇을 위한 조직인지는 모르겠지만, 비밀 조직 '시크릿 에이전시'는 소통의 흔적을 남기지 않기 위해

3일에 한 번씩 사라지는 메신저 앱을 사용했습니다.

그러나 내부 스파이의 대화 유출로 인해 대화를 할 때 조건을 여러 개 붙이기로 했습니다.

해당 조건은 이렇습니다.

 

• 캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분합니다.
• 소속은 'true', 'false', 'null' 중 하나입니다.
• 소속이 셋 중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿉니다.
• 아이디와 닉네임은, 길이를 2진수로 바꾼 뒤, 바뀐 숫자를 더합니다.
• 캐릭터와 대화 내용을 구분할 땐 공백:공백으로 구분합니다: ['Blue', 'Green', 'null'] : hello.
• 띄어쓰기 포함, 대화 내용이 10 글자가 넘을 때, 내용에 .,-+ 이 있다면 삭제합니다.
• 띄어쓰기 포함, 대화 내용이 10 글자가 넘지 않을 때, 내용에 .,-+@#$%^&*?! 이 있다면 삭제합니다.
• 띄어쓰기를 기준으로 문자열을 반전합니다: 'abc' -> 'cba'
• 띄어쓰기를 기준으로 소문자와 대문자를 반전합니다: 'Abc' -> 'aBC'

시크릿 에이전시의 바뀌기 전 대화를 받아,

해당 조건들을 전부 수렴하여 수정한 대화를 객체에 키와 값으로 담아 반환하세요.

같은 캐릭터가 두 번 말했다면, 공백을 한 칸 둔 채로 대화 내용에 추가되어야 합니다.

대화는 문자열로 제공되며, 하이픈- 으로 구분됩니다.

문자열은 전부 싱글 쿼터로 제공되며, 전체를 감싸는 문자열은 더블 쿼터로 제공됩니다.

예: "['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'"

 

문제는 대화 내용이 담긴 문자열을 입력받아, 문자열을 파싱하여 재구성을 하려고 한다.

"['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'" 
1. 입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱을 하고, 
파싱한 문자열을 상대로 캐릭터와 대화를 구분한다.

첫 번째 파싱은 - 을 기준으로 
['Blue', 'Green', 'null'] : 'hello. im G.', 
['Black', 'red', 'true']: '? what? who are you?' 
두 부분으로 나눈다.

두 번째 파싱은 : 을 기준으로 ['Blue', 'Green', 'null'] 배열과 'hello. im G.' 문자열로 나눈다.

2. 배열과 문자열을 사용해, 조건에 맞게 변형.
소속이 셋 중 하나인가 판별.

['Blue', 'Green', 'null'] 아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더한다: [1, 2, 'null']
'hello. im G.' 10 글자가 넘기 때문에 .,-+@#$%^&* 를 삭제: 'hello im G'
'hello im G' 띄어쓰기를 기준으로 문자열 반전: 'olleh mi G'
'olleh mi G' 소문자와 대문자 반전: 'OLLEH MI g'

3. 변형한 배열과 문자열을 키와 값으로 받아 객체에 넣는다.
{ "[1, 2, 'null']": 'OLLEH MI g' }

문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐없이 처리해야 정답을 받을 수 있다.

하나라도 놓친다면 통과할 수 없게 되고, 길어진 코드 때문에 헷갈릴 수도 있으니 주의한다.

 

5. Dynamic Programming(DP, 동적 계획법)

: 모든 경우의 수를 조합하여 최적의 해법을 찾는 방식.

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

→ 하위 문제 계산, 그 해결책 저장, 동일한 하위 문제인 경우 저장된 해결책을 적용하여 계산 횟수 줄이기.

⇒ 하나의 문제는 단 한번만 풀도록 하는 알고리즘.

 

✷ Memoization

: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거, 프로그램 실행 속도를 빠르게 하는 기술.

 

동적 계획법은 다음과 같은 두 가지 조건이 만족할 때 사용할 수 있다.

‣ 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다

   (Overlapping Sub-problems)

‣ 작은 문제에서 구한 정답은 그를 포함하는 큰 문제에서도 같다.

   작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다(Optimal Substructure).

 

ex)

// 재귀함수로 구현한 피보나치 수열
function fib(n) {
  if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...


fib(7)을 구하는 과정은 
fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
.....
--> 이 과정에서 동일한 계산을 반복적으로 수행해야 한다.
--> 부분 문제의 반복이라는 조건을 만족한다.

// 동적 계획법을 적용한 피보나치 수열
// fibMemo 함수의 파라미터로 n과 빈 배열을 전달한다
// 빈 배열은 하위 문제의 결괏값을 저장하는데에 사용한다
function fibMemo(n, memo = []) {

  // 이미 해결한 하위 문제인지 찾아본다
  // n번째 인덱스에 어떠한 값이 저장되어 있다면
  // 저장되어 있는 값을 그대로 사용한다
  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;
}

다이내믹 프로그래밍을 적용한 피보나치 수열에서 
fib(7)을 구하기 위해 fib(6)을, fib(6)을 구하기 위해 fib(5)을 호출한다. 
이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같다. 
큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라 부르기도 한다.

‣ 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];
}

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

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