덕짱 블로그 덕짱 블로그

DP(다이나믹 프로그래밍) 알고리즘의 기초 문제이다. 동적계획법이라고도 불리는 DP알고리즘은 큰 문제를 잘게 나누었을 때 하위구조에서 동일한 문제가 반복되는 경우 작은 문제의 답을 저장하여 큰 문제를 해결하는 알고리즘이다. 기초라고 하는데 나는 잘 이해가 되지 않아 많이도 해맸다. 몇가지 개념들을 학습하고 시간을 엄청 쏟은 뒤에야 이해하고 문제를 풀 수 있었다. 우선 이 문제를 이해하려면 다음 3가지 개념을 알아야 한다. 1. 피보나치 수열의 원리 2. 재귀함수의 원리 3. DP알고리즘에서 메모이제이션 위 세가지 개념을 먼저 이해했다면 이제 피보나치 수열을 재귀로 똑같이 진행하는데 메모이제이션 기법을 활용해 나가면 된다. 문제에서는 0과 1이 호출되는 횟수를 리턴하라고 되어있으므로 fib(n-1) + f..

선택정렬은 다음과 같은 논리를 가진다. 버블정렬과 비슷하지만 큰 값을 배열 끝에 위치시키는 대신, 작은 값을 루프를 돌때마다 한 번에 하나씩 앞쪽부터 차례대로 정렬시킨다. 그러니까 정렬된 데이터가 점점 누적되는 논리를 가진다. 먼저 첫번째 숫자를 min(가장 작은숫자)로 선택하고 차례대로 비교한다. 두번째 숫자인 44는 19보다 크기 때문에 지나친다. 38도 19보다 크기 때문에 지나친다. 그러다가 5를 만나면 5가 19보다 작기때문에 새로운 min이 된다. 이후 마지마까지 비교하게 되고 가장 작은 숫자인 5를 찾게된다. 그러면 이제 현재 i인 19와 min인 5의 자리를 교환한다. 그다음은 44부터 시작하게 되고 (5는 정렬된 상태) 이 과정을 반복하게 되면 오름차순 정렬이 완성된다. 구현한 코드는 다..

sort(정렬)알고리즘들 중에서 버블정렬 알고리즘은 효율적이지 않다. 흔히 사용되지도 않는다. 실제로 버블정렬을 구현할 일이 거의 없기 때문에 배우는 사람도 많지 않다고 한다. 하지만 다른 정렬 알고리즘이 왜 버블정렬 알고리즘보다 더 좋은지 이유에 대해 이해할 수 있다. 그리고 버블정렬은 매우 재밌는 문제이고, 이를 어떻게 사용하는지 알면 재밌는 알고리즘이다. 버블 정렬의 개념: 배열을 오름차순으로 정렬해야 할 경우 더 큰숫자가 한번에 하나씩 뒤로 이동한다. 루프를 돌면서 각 항목을 다음항목과 비교하는 것이다. 그리고 이 숫자가 비교대상보다 더 큰지 확인하고, 더 크면 순서를 교환한다.(swap) 29는 10보다 크기 때문에 29는 10과 자리를 바꿔 뒤로 가게된다. 이렇게 첫번째로 배열 끝까지 버블 정..

str1(long)과 str2(short)가 주어졌을때 str2가 str1에 들어있으면 1을 리턴 없으면 0을 리턴 str1을 for loop으로 돈다. 그안에 2중포loop으로 str2를 돈다. 먼저 str2[j]하고 str1[i]하고 다르면 break해준다. (첫문자부터 틀리면 str2는 돌릴필요가 없기때문에) 핵심 = str2[j]와 str1[j+i]가 같으면 count ++ 해준다 (이중포문에서 j하고 i를 동시에 비교하고싶을때 사용) j만 증가하지만 i에다가 j를 더해주면 동일한 idx를 비교가 가능하다. const naiveSearch = (long, short) => { let count = 0; for (let i = 0; i < long.length; i++) { for (let j = ..

스킬트리 문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요. 제..