[코테] 코딩테스트를 위한 알고리즘의 첫 걸음

코테를 준비해야겠다는 생각만 가진 지 어언 3년째....

이제는 더이상 물러날 곳이 없다. 진짜 해야한다는 말.

각 알고리즘의 실행시간을 비교하여 어떤 알고리즘이 더 우수한 지 파악하는 데에 중점이 있다. (알고리즘 간의 효율성)

---

시간복잡도

입력이 커질수록 알고리즘의 실행속도가 어떻게 바뀌는 지 분석함

 

시간 복잡도의 유형

1. 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
2. 빅-세타 : 보통일 때의 연산 횟수를 나타낸 표기법
3. 빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법 (= 실행시간이 가질 수 있는 최대치)

 

Big O 표기법?

빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기
(알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미)

* 입력의 크기와 실행시간의 관계
* 상수를 없애고 n을 중점으로 간단하게 표기하며, 어떤 그래프로 표현될지 확인
(제일 큰 항을 기준으로 표기법을 작성)

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2)

상수 < 로그 < 선형 < 다항< 지수 

 

Big O 표기 방식

- 필요없는 상수는 다 쳐내고 표현한다.

 

1. O(n+10) => O(n)

 

2. O(1000n + 50) => O(n)

 

3. O(n^2 + 5n + 8) => O(n^2)

 

---

문제 1. 특정 숫자까지의 합을 구하는 알고리즘을 작성하라

해결1) O(n)

function addNum(n){
let total = 0;
for(let i=1;i<=n;i++){
total += i
}
return total;
}

console.log(addNum(100));

해결2) O(1) - n의 값이 커질수록 아무변화가 없다(=실행시간은 변하지 않는다)

1부터 n까지의 숫자를 모두 더하는 공식은 N(N + 1) / 2

function addNum2(n){
return n * (n+1) / 2;
}

console.log(addNum(6));

 

둘 중 “더 나은” 코드는 무엇인가?

• 무엇이 더 빠른가?
• 무엇이 더 메모리를 잡아먹지 않는가?
• 얼마나 가독성 있는 코드인가?

=> 결과적으로 셋 다 고려해야 하는 상황 발생

performance.now();

⇒ 창이 열린 시간을 알려줌 (실행 시작시점)
⇒ 항상 이러한 시간 비교를 통해 어떤 알고리즘이 더 빠른지 확인하는 것은 어렵기 때문에 빅오 표기법으로 각 알고리즘의 소요 시간을 간단하게 표현할 수 있다.
⇒ 연산자의 개수에 따라 걸리는 시간이 다를 수 있다.

⇒ n번을 반복했을 때 반복되는 연산의 횟수를 확인하는 것이 중요하다.

---

문제 2. 특정 숫자까지 하나씩 더해서 출력하고 하나씩 빼서 출력해보자

해결 1. O(n) - 반복문에 따로 존재하는 경우

function countUpAndDown(n){
console.log("Going up!");
for(let i = 0;i < n; i++){
console.log(i);
}
console.log("At the top");
for(let j = n - 1; j >= 0; j--){
console.log(j);
}
console.log("Back down. Bye!");
}

countUpAndDown(10);

---

문제 3. 중첩 반복문 (n까지 반복)

해결 1. O(n^2)
function printAllPairs(n){
	for(var i = 0; i < n; i++){
		for(var j = 0; j < n; j++){
		console.log(i, j);
		}
	}
}

printAllPairs(6);

 

Big O 표기를 쉽게 파악할 수 있는 팁

1. 산수도 상수로 생각한다 (+-*/ = 상수)
2. 변수에 값을 배정하는 것도 상수로 생각한다 (x =1000)
3. 리스트나 배열의 특정 값을 찾는 것도 상수로 생각한다. (인덱스, key)
4. 반복문에서 n의 수가 늘어날수록 실행시간 또한 늘어나게 된다. n^2의 반복문이 존재하면 실행시간은 더욱더 늘어나는 것은 당연하다.

---

공간복잡도

• 입력이 커질수록 알고리즘이 얼마나 많은 공간을 차지하는 지 분석함
• 사용되는 메모리를 중점으로 확인

1. JS에서의 불변공간

- 어떤 숫자가 들어가던지 변함없이 같은 공간을 차지함

• boolean
• number
• null
• undefined

---

2. O(n)의 공간을 차지함

• 문자열

ex) 1개의 문자와 50개의 문자는 다른 크기의 공간을 차지하게 됨.

• 참조타입
• 배열
• 객체

 

시간복잡도는 좋지만 공간복잡도는 안좋은 경우가 있을 수 있고,

공간복잡도는 좋지만 시간복잡도는 안좋은 경우가 있을 수 있다.

---

로그

• 지수함수의 역함수
• 알고리즘에서는 log의 밑을 표기하지 않고 그냥 log n으로만 표기하여 나타낸다.
• 특정 알고리즘은 로그 시간복잡도를 가지고 있는 경우가 있다.
• 효율적인 정렬 알고리즘 또한 로그 시간복잡도를 확인할 수 있다.
• 재귀 알고리즘에서 확인하게 될 것이다..공간복잡도를 통해 로그를 확인할 수 있다.

디버깅의 중요성

• 프로그램에서 발생하는 문법오류나 논리오류를 찾아 바로잡는 과정을 디버깅이라고 한다.
• 사용자의 의도와 다르게 동작하는 논리오류가 발생하는 경우 디버깅을 통해 바로잡는다.
• 만약 JAVA로 코테를 준비한다면 자료형 범위 오류는 가장 하기 쉬운 오류이므로 변수는 처음부터 long 형으로 선언할 수 있도록 하자