비전공자 개발자로서 CS 지식이 부족하다고 항상 생각해왔고, 아직 실무에서 깊은 CS 지식이 필요하지는 않지만 추후에 최적화나 성능 관련 이슈를 해결하려면 기본이 되어야 한다고 생각한다. 이런 생각을 팀장님께 말씀드렸더니 실무에 적용할 수 있는 자료구조와 알고리즘 관련 공부를 시작으로 범위를 확대해 나가는게 좋겠다고 의견을 주셔서 자료구조와 알고리즘 공부를 시작해보려고 한다.
부트캠프에서 자료구조와 알고리즘 관련된 학습과 코딩 문제들을 풀어보긴 했지만 프로젝트와 취업 준비를 하면서 공부했던 내용을 많이 잊어버리게 되었다. 이미 알고 있는 내용이더라도 놓치고 있는 부분이 있을 수도 있고 복습한다는 생각으로 기초부터 정리되어 있는 책을 통해 공부를 시작하려고 한다.
이 책은 비전공자도 쉽게 이해할 수 있도록 정리해놓은 책으로 더북(https://thebook.io/080274/)에서 5장까지 공개되어 있고, 추후 구매하여 끝까지 학습할 예정이다.
알고리즘
정렬된 배열
이진 검색
//부트캠프에서 풀었던 이진 검색 알고리즘을 사용한 코딩 문제
const binarySearch = function (arr, target) {
let up = 0
let down = arr.length-1
while(up <= down) {
let half = Math.floor((up+down)/2)
if(arr[half]=== target) return half;
if(arr[half] > target) {
down = half -1
}
else {
up = half + 1
}
}
return -1
};
버블 정렬(bubble sort)
1. 배열의 처음부터 연속된 두 항목을 비교하여 올바른 위치로 바꾼 후 그 다음 항목도 배열의 마지막 항목 차례가 될때까지 같은 방식으로 정렬한다. (길이가 n인 배열 : 0,1비교 -> 1,2 비교 ... n-2,n-1 비교)
2. 1번 과정을 패스 스루라고 하며, 더 이상 항목간 자리 교환이 일어나지 않을 때까지 패스 스루를 반복한다.
//버블 정렬 예시
const bubbleSort = function (arr) {
let temp = 0
for (let i=0; i<arr.length-1; i++) {
let breakcheck = 0
for (let j=0; j<arr.length-1-i; j++) {
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp
breakcheck ++
}
}
if(breakcheck === 0) break;
}
return arr
};
```
버블 정렬의 효율성
N2 개선
//시간복접도 O(N^2)의 중복 여부 검사 함수
function hasDuplicateValue(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(i !== j && array[i] === array[j]) {
return true;
}
}
}
return false;
}
//배열의 인덱스를 활용하여 O(N)으로 시간 복잡도 개선
function hasDuplicateValue(array) {
let existingNumbers = [];
for(let i = 0; i < array.length; i++) {
if(existingNumbers[array[i]] === 1) {
return true;
} else {
existingNumbers[array[i]] = 1;
}
}
return false;
}
누구나 자료구조와 알고리즘의 목차를 읽어보니 대부분은 이미 알고 있는 내용이여서 복습하는 식으로 공부한 이후에 추가적으로 학습할 수 있는 책이나 알고리즘을 활용한 코딩 테스트를 공부할 예정이다. 이번에 정리한 1~3강 역시 이미 배운 내용이었지만 부트캠프를 진행하면서 짧은 시간에 학습했기 때문에 빠진 내용은 없었는지 꼼꼼하게 읽어보면서 정리하였다.