알고리즘이나 데이터 구조를 공부하는 건 아직 나랑은 먼 얘기인 것 같고 프론트엔드 개발자에게 알고리즘이 그렇게 중요하지 않을 것 같다는 선입견이 있어 흐린 눈을 하며 지내왔다. 지금 생각해보니 말도 안되는 선입견이었다.
코딩을 하는 목적이 무언가를 해결하기 위함인데 알고리즘이나 자료구조에 대한 지식이 있으면 구현하고자 하는 기능을 보다 쉽고 효율적으로 만들 수 있고, 따라서 코딩을 하는 개발자라면 프론트, 백 상관 없이 이런 기본 지식이 필요하다는 걸 최근에야 깨닫게 되었다. 특히 요즘 코딩테스트를 보는 기업이 많은데 이런 배경 지식 없이 예제만 푸는 게 뭔가 밑 빠진 독에 물붓는 느낌이라 더 공부하고 싶다는 생각이 들었다.
일단 하버드 컴퓨터과학 입문 강좌로 유명한 CS50를 들으면서 알고리즘, 메모리, 자료구조 등에 대한 기본적인 내용을 익히고 현재는 유데미에서 'Master the Coding Interview: Data Structures + Algorithms' 강의를 듣고 있는데 의도했던 건 아니지만 CS50로 먼저 공부했던 게 지금 큰 도움이 되고 있는 것 같다.
일단 CS50은 자막과 강의 요약본, 그리고 퀴즈가 한국어로 제공되어서 생소한 컴퓨터 과학 내용도 비교적 쉽게 이해할 수 있었기 때문이다. 그리고 유데미에서 Big-O 표기법과 각각의 자료구조를 배우고 있는 지금, 하루하루 새로운 시야가 확장되고 있는 느낌이라 너무 신기하고 재밌게 공부하고 있다.
시간 복잡도, 공간 복잡도 그게 뭐죠? 🧐 아무것도 모르고 항상 인자 두 개 받아 비교하거나 짝 지어야 하는 문제가 나오면 냅다 중첩 반복문 돌렸던 과거의 내가 생각나면서 왜 코테를 그렇게 떨어졌었는지 바로 납득 완.
좋은 코드란?
- Readable
- Time Complexity
- Space Complexity
언제나 그렇듯, 좋은 코드는 본인을 위해서든 협업하는 동료를 위해서든 가독성이 좋아야 한다. 그리고 시간 복잡도, 공간 복잡도가 낮은 코드를 작성하는 것이 중요하다. 보통 이 둘의 관계는 trade-off라서 하나를 택하면 하나를 포기해야 하는 경우가 많다.
Big-O Notation
출처: freeCodeCamp Big-O Complexity Chart
Big-O 표기법의 O는 'on the order of'의 약자로 '~만큼 정도로 커지는'이라는 뜻으로 해석될 수 있다. 알고리즘의 효율성✨을 표기할 때 사용되며 시간 복잡도, 공간 복잡도 개념에 모두 사용될 수 있다. Big-O 표기법은 다음과 같은 규칙을 갖는다.⭐Big-O Rule
1. 항상 최악의 결과로 가정하기
Big-O는 알고리즘의 상한 시간📈을 나타낸다. 예를 들어 선형 검색에서 n개의 항목이 있을 때 운이 좋다면 첫 요소에서 바로 검색을 마칠 수도 있지만, 항상 최악의 결과를 가정해 최대 n번의 검색을 해야 하는 것처럼 결과를 예측해야 한다는 걸 의미한다. 반대로 실행 시간의 하한은 Big Ω 표기법으로 나타낼 수 있다.
2. 상수는 버려
function printFirstItemThenFirstHalfThenSayHi100Times(items) {
console.log(items[0]); // (1)
let middleIndex = Math.floor(items.length / 2);
let index = 0;
while (index < middleIndex) { // (2)
console.log(items[index]);
index++;
}
for (let i = 0; i < 100; i++) { // (3)
console.log("hi");
}
}(⚠위 함수명은 함수를 설명하기 위해 과하게 작성된 것일뿐 이렇게 절대 사용하지 않습니다)
위의 코드를 보면
(1)에서 인자로 입력 받은 배열의 첫 요소를 출력하고 => O(1)
(2)에서 인자로 입력 받은 배열의 앞 절반 크기 만큼의 요소를 순회하며 출력하고 => O(n/2)
(3)에서 for 반복문을 돌며 'hi'를 100번 출력하고 있다 => O(100)
이 내용을 Big-O 표기법으로 나타내면 O(1 + n/2+ 100)이지만
n이 굉장히 커진다고 가정했을 때 아주 작디 작아져 의미가 없어지는 1과 100같은 숫자를 지워버리고 1/2도 없는 셈 치게 되어 O(n)이라고 표기하는 것을 의미한다.
3. input이 다르면 표기도 다르게
function compressBoxesTwice(boxes, boxes2) {
boxes.forEach(function (boxes) {
console.log(boxes);
});
boxes2.forEach(function (boxes) {
console.log(boxes);
});
}위의 코드를 보면 forEach 메서드가 두번 실행되어 O(2n)이고, 위의 상수 제거 규칙 때문에 O(n)이라고 생각할 수도 있다. 하지만 함수의 인자로 받고 있는 boxes와 boxes2는 엄연히 다른 input이다. 이런 경우에는 표기법에도 O(a + b), O(n + m) 과 같이 구분을 해주어야 한다.
4. 1등만 기억하기
function printAllNumbersAndPairSums(numbers) {
console.log("these are the numbers: ");
numbers.forEach((number) => { // (1)
console.log(number);
});
console.log("and these are their sums: ");
numbers.forEach((firstNumber) => {
numbers.forEach((secondNumber) => {
console.log(firstNumber + secondNumber); // (2)
});
});
}
printAllNumbersAndPairSums([1, 2, 3, 4, 5]);위 함수는 인자로 숫자가 담긴 배열을 받고 있고, 함수 내에서 각각의 요소를 출력하고 중첩 함수를 통해 요소들 각 쌍의 합을 출력하고 있다. (1)에서 배열의 개수만큼 forEach의 콜백 함수가 실행되므로 O(n), (2)에서는 함수가 중첩되어 요소 개수만큼 실행되므로 O(n^2)이다. 하지만 이 알고리즘의 시간 복잡도는 O(n + n^2)가 아니라 O(n^2)이다. 이 역시 n이 엄청 커질 때를 대비해 가장 중요한 요소만 남기고 나머지는 무시하는 규칙이다.
위 규칙을 숙지하니 Big-O로 시간 복잡도를 이해하고 계산할 수 있게 되었다.
코딩 인터뷰 연습
유데미 강의에서 굉장히 구체적으로 코딩 인터뷰를 어떻게 치뤄야 하고 각 단계에서 어떻게 논리적으로 설명하고 코드를 짜야하는지 설명하고 있지만 이 글에서는 나한테 가장 중요하다고 생각했던 부분 위주로 정리해보려고 한다.
💬 예시로, 두 배열을 인자로 받아 서로 공통된 요소가 있다면 true, 아니라면 false를 반환하는 함수를 짜는 문제가 나왔다고 가정해보자.
1. 문제를 명확히 하기
문제 풀이 중간에 이해를 잘못해 다시 원점으로 돌아오는 것보다 처음부터 문제를 명확히 하고 진행 방향을 생각하는 것이 훨씬 효율적일 것이다. 예를 들어 정렬 문제인지 탐색 관련인지, input으로는 무엇을 받고 array라면 크기 제한은 없는지, input과 output은 무언인지 등등을 확인해볼 수 있다. 여기서는 공간 복잡도는 고려하지 않고 시간 복잡도만 고려해서 설명할 예정이다.
위의 예제에서 input은 배열 두 개, output으로는 boolean이 요구사항인 것이다.
2. 가장 쉬운 접근법으로 시작하기
이 단계는 보통 코드로 작성할 필요는 없고 구두로 설명만 하고 왜 최선의 방법이 아닌지 덧붙이면 충분하다고 한다. 예를 들어 위 예제라면
function containsCommonItem(arr1, arr2) {
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j]) {
return true;
}
}
}
return false;
}이처럼 중첩 반복문을 돌릴 수 있겠다. 그동안 내가 주구장장 사용하던 사용하던 방식....🤦♀️..
반복문 안에 반복문이 실행되는 것이기 때문에 Big O 표기법으로 하면 O(n^2)이고 O(n^2)은 효율이 아주 떨어지는 표기법 중 하나이므로 개선의 여지가 있을 확률이 높다.
3. 더 나은 접근법 떠올리기
다음으로, 위보다 나은 코드를 설명 혹은 주석을 통해 단계적으로 접근한다.
function containsCommonItem(arr1, arr2) {
// (1) loop through first array and create object where properties === items in the array
let map = {};
for (let i = 0; i < arr1.length; i++) {
if (!map.arr1[i]) {
const item = arr1[i];
map[item] = true;
}
}
// (2) loop through second array and check if item in second array exists on created object
for (let j = 0; j < arr2.length; j++) {
if (map.arr2[j]) {
return true;
}
}
return false;
}위의 코드를 보면
(1)에서 빈 객체를 생성한 뒤 첫 번째 인자로 받은 배열을 순회하며 객체의 프로퍼티 값으로 넣어주고
(2)에서 두 번째 인자로 받은 배열을 순회하며 (1)에서 생성된 객체의 프로퍼티 중에 존재하는지 확인하는 과정을 반복문으로 실행하고 있다.
이 방식으로 코드를 짜면 두 번째 단계의 중첩 반복문 없이 독립적인 두 개의 반복문으로 처리되기 때문에 O(n^2)에서 O(a + b)로 복잡도가 감소한 것을 확인할 수 있다. 이 방식을 처음 알고 진짜 신세계였다. 이런 방식으로 해결할 수 있다니 아직 나는 갈 길이 멀구만🏃♂️
4. 에러 확인 및 개선 사항 떠올리기
인자로 꼭 요소가 들어있는 배열이 온다는 보장이 없다. 빈 배열이 오거나 undefined, null, 0등 예외처리 할 수 있는 부분을 어떻게 대응할지에 대해서 생각해봐야 한다.
또 바로 위단계의 코드를 자바스크립트 메서드 체이닝 등을 통해 더 개선해볼 수도 있다.
function containsCommentItem(arr1, arr2){
return arr1.some((item) => arr2.includes(item));
}오 너무 재밌다 유레카..................🔥
다음에는 지금 공부하고 있는 자료 구조에 대해 정리해볼 예정이다. 자료구조, 알고리즘에 대한 내용이 어느정도 숙지가 되면 유형별 코딩 테스트 문제를 다양하게 풀어보고 적용시켜보고 싶다.
💌 혹시 잘못된 내용이 있다면 꼭 피드백 부탁드립니다! 더 공부해서 보충/수정하겠습니다 :)
