Moe's Tech Blog

Step 1: Work example by hand Should be a small problem to solve mentally If problem is unclear --> ask or research If domain knowledge is lacking (i.e. physics behind defining equation of motion) --> research or study till figured out Step 2: Write down what you did Write down exact steps on how you did it, and don't leave anything out This steps are for small instance solved in step 1 (Not gene..

DFS 와 BFS를 구현하려면 재귀 함수의 이해가 필요 영어로는 recursive function이라고 한다 재귀함수란 자기 자신을 다시 호출하는 함수를 의미 function recursiveFunction() { console.log("This is a recursive function"); return recursiveFunction(); } 재귀함수 종료 조건이 없으면 다음의 에러가 나타난다 Maximum call stack size exceeded 재귀함수는 stack 자료구조를 이용한다 가장 마지막에 호출한 함수가 끝나야 그 앞의 호출이 종료된다 재귀 함수 종료 조건 재귀함수를 사용할때는 종료 조건이 꼭 필요 종료 조건이 없으면 에러 뜰때까지 무한 호출 종료할때 if 문 안에 return을 사용..

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 교재에서 “탐욕법”으로 소개된다. 현재 상황에 지금 당장 좋아 보이는 것만 고르는 방법을 의미한다 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다 사전에 외우고 있지 않아도 풀수 있을 가능성이 높은 문제 유형이다. 그리디 알고리즘 문제 풀이 대부분의 그리디 알고리즘 문제에서는 최적의 해 문제 풀이를 위한 해법을 찾고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다. 바로 문제 유형을 파악하기 어렵다면: 그리디 알고리즘을 의심 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민 오랜시간끝 해결방법을 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘등으로 해결할 수 있는지 고민 그리디 알고리즘 예 '큰 수의 법칙'은 일반적..

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수 정렬은 ‘데이터 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있다. 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우는 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. (그 이후는 리스트를 초기화 해야 하기 때문) function countSort(array) { let ans = []; let count = Array(Math.max(...array) + 1).fill(0); for (let i = 0; i < array.length; i++) { count[array[i]] += 1; } for (let..

지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 병합정렬 (Merge Sort) 알고리즘과 함께 라이브러리 근간이 되는 정렬 알고리즘이다 코드 (자바스크립트) function quckSort(array, start, end) { if (start >= end) { return; } let pivot = start; let left = start + 1; let right = end; while (left right { [array[pivot], array[right]] = [array[right], array[pivot]]; } else { [array[left], array[right]] = [array[right], array[left]]; } } quickSort(array, s..

가장 원시적인 방법중의 하나다 선택 정렬 보다 효율적이나 그래도 알고리즘 문제에 사용하기에는 느리다 적절한 위치에 삽입한다는 의미다 코드 (자바스크립트) function insertionSort(array) { for (let i = 1; i = 0; j--) { if (array[j] < array[j-1]) { [array[j], array[j-1]] = [array[j-1], array[j]]; } } } return array; } 시간 복잡도 삽입 정렬의 시간 복잡도는 O(N2) 이다 최선의 경우 (데이터가 거의 정렬된 상태) O(N)의 시간 복잡도를 가진다 이때는 퀵 정렬보다 강력하다 거의 정렬된 상태로 입력이 주어지는..

가장 원시적인 방법중의 하나다 매번 정렬되지 않은 데이터중 가장 작은 것을 선택해 앞으로 보낸다는 의미다 코드 (자바스크립트) function selectionSort(array) { for (let i = 0; i array[j]) { minIndex = j; } } [array[i], array[minIndex]] = [array[minIndex], array[i]]; } return array; } 시간 복잡도 선택 정렬의 시간 복잡도는 O(N2) 이다 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내..

들어가며 우리는 주로 코딩 시험을 연습할 때 "제출 후 채점하기" 버튼을 눌러 틀렸는지 맞았는지를 확인합니다. 연습할 때는 괜찮지만 실전은 다릅니다. 회사에서 일을 할 때 선배에게 "선배님 이게 맞습니까?" 하고 계속 물어볼 수 없습니다. 또한 코딩 테스트에서는 "제출 후 채점하기" 버튼을 누르면 서버에 기록이되 많이 누르면 누를수록 안 좋게 보일 수 있습니다. 필자는 Maurício Aniche의 Effective Software Testing에 나와있는 specification based testing을 공부하며 이 문제 점들을 막을 수 있으라고 생각합니다. Specification Based Testing 절차 Step 1: 문제를 읽고 무엇을 목표로 함수를 만드는지, 함수에 들어가는 매개변수, 제..