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을 사용..

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세..

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

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수 정렬은 ‘데이터 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있다. 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우는 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터 차이가 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번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내..