devkty 님의 블로그

5주차 퀴즈 복습시간이 좀 됐지만, 5주차의 마무리를 해야하므로 퀴즈 내용을 복습해봤다. B-Tree를 설명할 정도로 능숙했지만, 문제를 잘 못 읽어 1, 2번 문제 틀린게 아직까지 마음이 아프다… 1번 문제차수가 3인 아래 B-Tree에서 17을 새로 삽입한 후의 결과를 그려보세요.→ 이것은 내가 전에 설명한 B-Tree 삽입 로직을 생각하여 풀면된다. 17이 들어가면 15보다 크고, 23보다 작으므로 [20, 22] 자식 노드에 포함되게 된다. 그러나 해당 트리는 차수가 3이므로 자식이 최대 2개이다.그러므로 [17, 20, 22]에서 중간 인자인 20은 승급한다. 승급된 이후 부모노드가 [20, 23, 27]이므로 부모노드에서도 23이 승급합니다. 그러면 그 위의 부모노드도 [10, 15, 23]에..

DP란?복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘입니다.즉, 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘입니다.상황에 따라 구현 방식은 다르다. 가장 쉬운 문제는 피보나치 문제이다.원래 피보나치 수열은 N번째 항을 재귀로 호출해 중복된 연산으로 계산이 오래걸린다. 그러나 DP를 통해 하위의 배열을 미리 만들고, 중간 결과를 저장해서 시간복잡도를 O(N)까지 줄일수 있습니다.DP문제가 어려운 이유는 문제를 보고 DP를 생각해내기 어렵다는 점입니다. 테이블을 정의해야하고 점화식을 찾은 후에 초기 값을 정의해야합니다. 의외로 점화식 찾기가 어렵기 때문에 많은 문..