알고리즘 문제들은 매우 어렵다. 처음 문제를 접하고 풀리지 않는 문제를 볼 때는 무섭기까지 했다. 하지만 결국, 우리는 피해 갈 수 없다. 아무리 실무에서 안 쓴다더라, 누구는 안 하고도 코딩 잘하더라 하지만 어떻게 보면 가장 쉽게 코딩 실력을 키우고 좋은 곳에 취직을 할 수 있는 방법이 알고리즘을 잘 푸는 것이 아닐까? 그래서 오늘도 이렇게 삽질을 하고 있다.
2. 알고리즘?
문제를 가장 효율적으로(최단 시간과 연산 과정에서의 반복을 최선으로 줄인) 해결하는 방법이다. 일명, 극한의 이득충
분명, 모든 경우의 수를 다 확인한다면 반드시 답에 접근이 가능하다. 하지만 문제에서 아주 다양한 방법으로 제한사항을 두고 일상생활과 같은 곳에서 볼 수 있는 상황을 코드로 만들 수 있는가? 와 같은 다양한 상황에 마주치게 된다.
3. 어떻게 접근할 것인가?
문제를 이해한다. '이해'한다. 사실은 이것이 50%이다. 대부분의 알고리즘 문제들은 문제를 읽는 것도 길고, 문제가 원하는 의도를 찾는 것도 쉽지 않다. 그러므로 일단 어떤 식으로 입출력 예시들이 작동하고 있는지를 이해하고 문제의 의도를 파악한다.
수도 코드를 적는다. 난의도가 어려워질수록 더욱 필요하다. 코드 자체가 길어지기 때문에 내가 무엇 때문에 지금 이 코드 한 줄을 이용해 무엇에 접근하려고 하는지를 까먹게 된다. 필요하다면 그림을 그리거나, 이해한 것을 타인에게 설명해 보아도 좋을 것이다.
4. 시간복잡도 (Time Complexity)
간단하게 말해서 이 알고리즘이 연산될 때마다, 얼마나 시간이 걸리는가? 를 묻는 것이다.
이것을 줄이는 것이 우리가 생각하는 알고리즘 문제가 될 것이다.
주로 우리는 Big-O (빅-오) 표기법으로 시간 복잡도를 표현한다.
최고의 효율인 Big-Ω(오메가), 평균적 효율인 Big-θ(세타) 표기법도 있지만, 평가가 어려워서 잘 사용하지 않는다고 한다.
5. Big-O
Big-O 표기법의 복잡도를 나타낸다.
O(1) : 입력과 상관없이 바로 출력이 가능한 복잡도. index를 받아서 바로 출력하듯이, 얼마나 많은 입력이 있는 것은 상관없이 바로 해당 index에 접근해서 출력하게 된다.
function O1(arr, index) {
return arr[index];
}
let arr = [1, 2, 3];
let index = 1;
let result = O1(arr, index);
console.log(result); // 2
O(n) : 입력과 함께 시간 복잡도가 똑같은 비율로 증가한다. 반복문을 사용해 모든 요소를 돌면서 데이터를 조작할 때처럼, 입력이 많아지면 돌아야 할 요소가 많아지는 것처럼 말이다.
function On(n) {
let arr = [];
for (let i = 0; i < n; i++) {
arr.push(i)
}
return arr;
}
On(3) // [0, 1, 2]
On(5) // [0, 1, 2, 3, 4]
O(log n) : 한번 연산이 될 때마다, 연산해야 할 요소들이 절반으로 줄어든다. BST가 O(log n)에 속한다.
