[코드 스테이츠] 83일차, "12주차 복습 (1)"

  오늘 작성할 블로깅의 내용은 코드 스테이츠에서 배운 것보다 간결하게 작성할 예정이다. 그 이유는, 오늘 복습할 내용 중에 알고리즘 문제를 푸는 코드 스테이츠만의 노하우가 많이 담겨 있는 것 같아서 그 부분들은 과감하게 생략하고자 한다. 

---

[ 오늘의 TODO ]

1. 코드 스테이츠) 수 내용 복습
   // 연휴에 맞춰서 휴일에 하나씩 복습 블로깅을 할 생각이다.
   // 앞서 말한 대로 이번 내용은 코드 스테이츠에서 배운 내용보다 빈약하게 작성할 예정이다
2. 패스트 캠퍼스) 인강 3개 이상 듣기 // optional
3. 스터디 그룹) 프로그래머스 문제 풀기
4. 생활) 물 1L 이상 마시기

 

---

[ 오늘의 복습 ]

1.  알고리즘

  알고리즘이란 문제를 해결하는 최선의 선택이다. 컴퓨터를 이용해 문제를 해결할 때는 많은 방법이 존재한다. 그 중에서도 최선의 것, 가장 좋은 방법을 알고 있다면 그 방법을 사용하고 다른 방법은 사용하지 않을 것이다. 사실, 컴퓨터의 연산 속도는 매우 빨라 어떤 방법이든 동일한 효율로 같은 결과를 내는 것처럼 볼 수 있다. 하지만, 연산의 내용이 많아진다면 그 미세한 차이는 점차 큰 격차를 만들어낼 것이다. 그렇기에 개발자로서 가장 최선의 방법, 최선의 알고리즘을 구현하는 것은 극히 자연스러운 일이다.

 

 

1) 시간 복잡도

 

https://en.wikipedia.org/wiki/Time_complexity

 

  시간 복잡도란 연산을 실행할 때 입력값의 변화에 따라서 연산 횟수와 그에 따른 시간이 얼만큼 달라지는 가를 나타내는 지표다. 효율적인 알고리즘을 구현한다는 것은 입력값이 커지더라도 연산 횟수와 연산에 걸리는 시간이 덜 걸린다는 것을 의미한다. 

 

2) Big - O 표기법

  Big - O 표기법이란 시간 복잡도를 표현하는 방식으로, 최악의 상황일 때 얼마만큼 걸리는지를 나타내는 지표다. Big - O 이외에도 다른 지표들이 있지만, Big - O 표기접은 최악의 경우를 상정하고 있기에 불안 요소가 가장 적은 지표라 할 수 있다.

 

O(1)

 

입력값이 증가하더라도 시간이 늘지 않는 경우를 의미한다. 시간 복잡도 그래프에서 1을 가리키는 연보라색 선이다. 입력값의 크기가 무엇이든 즉시 출력값을 얻어낼 수 있는 경우를 의미한다. 

 

function O_1 (arr, index) {
  return arr[index]
}

 

O(n)

 

  입력값이 증가함에 따라 연산하는데 걸리는 횟수나 시간도 동일한 비율로 증가한다. 시간 복잡도 그래프에서 n을 가리키는 연두색 선이다. 

 

function O_N (arr) {

  let sum = 0

  for (let el of arr) {
    return sum += el
  }
  
  return sum
}

function also_O_N (arr, secondArr) {
  let sum = 0
  
  for (let el of arr) {
    sum += el
  }
  
  for (let ele of secondArr) {
    sum += ele
  }
  
  return sum
}

 

  위의 경우, 배열의 요소가 하나 증가하면 연 산 횟수도 한 번 추가된다.  한 가지 주의할 점은 also_O_N 처럼 for 문이 여러 개 나오더라도 같은 O(N) 이라는 점이다. 무한으로 가면 N 앞에 붙는 계수는 의미가 없어진다. 그렇기에 also_O_N 의 시간 복잡도는 O(2N) 이 아니라 O(N) 이다. 

 

O(logN)

  편하게 logN 이라 하지만 사실상, 로그이 밑이 2다. Big-O 표기법 중에서 O(1) 다음으로 효율이 좋은 알고리즘이다. 입력 값이 두 배 늘어나더라도 연산 횟수는 한 번만 더 추가된다. 

 

function O_logN(arr, target) {
	let left = 0
	let right = arr.length - 1
	while (left <= right) {
		let middle = Math.floor((left + right) / 2)

		if (arr[middle] === target) {
			return middle
		} else if (arr[middle] > target) {
			right = middle - 1
		} else if (arr[middle] < target) {
			left = middle + 1
		}
	}

	return `주어진 배열에서 ${target} 요소는 없습니다.`
}

 

  위의 알고리즘은 이진 탐색 방법이다. arr 안에 target 이 존재하는지 찾아낼 때 O(N) 의 방법으로 하나씩 요소를 따져가며 찾는 것이 아니라 arr 를 절반으로 계속해서 나눠가며 나머지 절반은 버리는 방식으로 진행한다. (물론, 위의 코드는 arr 가 오름차순으로 정렬돼 있다는 전제가 필요하다) 나누기 2가 극한으로 가게 되면 밑이 2인 log 의 그래프와 비슷해진다. 

 

 

O(N^2) 

 

입력값이 증가함에 따라서 시간이 n의 제곱 수의 비율로 증가한다.

 

function O_quadratic (arr) {
  let result = []
  
  for(let i = 0 ; i < arr.length ; i++) {
    for(let j = 0 ; j < arr[i].length ; j++) {
      result.push(arr[i][j])
    }
  }
  
  return result
}

O_quadratic([[1, 2, 3], [4, 5, 6], [7, 8, 9]]

 

O(N) 과 마찬가지로 이중 반복문이 여러 개 나온다 한들 N^2 앞에 계수는 붙지 않는다.

 

 

2. 탐욕 알고리즘 (Greedy Alogorithm)

  탐욕 알고리즘은 매 단계별로 최적의 풀이 방법으로 풀어 최종 해답에 도달하는 과정을 의미한다.  탐욕 알고리즘은 총 세 가지의 단계로 이뤄진다.

 

1. 선택 절차: 지금 직면한 문제에 최적의 해답을 선택한다
2. 적절성 검사: 선택된 해법이 문제의 조건을 만족시키는지 확인한다.
3. 해답 검사: 원래 문제가 해결됐는지를 검사하고, 해결되지 않았다면 선택 절차로 돌아간다.

  탐욕 알고리즘의 대표적인 문제는 거스름 돈을 건네줄 때의 상황이다. 손님이 2350 원인 물건을 현금 5000원으로 결제한다고 해보자. 그러면 직원은 거스름돈을 줄 때 가장 먼저 큰 돈부터 차례 대로 계산해서 건네준다. 거슬러 줘야할 돈은 2650원이다. 가장 먼저, 1000원 2개, 500원 1개, 100원 1개, 50원 1개 줄 것이다. 이 얘기를 들으면 "이게 왜?" 라고 생각할 수 있다. 하지만, 이렇게 거스름돈을 주는 이유는 거스름돈으로 건네줄 동전이나 지폐의 개수를 가장 최소한으로 주는 방법이다. 2650원을 준다고 하면 1000원 한 개, 100원 10개, 50원 13개를 줄 수도 있다.