SunFly의 코딩 및 정보 블로그

DP. 즉 Dynamic Programming은 여러가지 알고리즘 문제들을 풀다보면 간간히 사용하는 경우가 많다. 핵심 내용은 이전에 계산한 값을 다음 실행에 써먹을 수 있고 이러한 계산들이 쌓여서 결과를 도출한다는 것이다. 한마디로 입력값이 이전 계산값이고 출력값이 현재 구하려는 값이다. 백준의 14501번 : 퇴사 문제를 예시로 들어서 보자. 이 문제는 삼성 역량 테스트 문제로도 나온 문제로 대기업 코테에서도 DP 관련 문제가 나올 수 있다는 것을 알아두자. dp 45(35+10) 45 45(35+10) 35(15+20) 15 0 0 0 ♦ 아이디어 방향 1. 그 전에 해당된 날짜의 이익, 상담하는 데에 걸리는 일수를 알고 있어야 다음을 진행할 수 있다. 2. 그 전 값을 기억하는 알고리즘 DP 알고..

※ 첫 record 삽입 ● Root가 아직 NULL인 경우에 해당됨 ● 아직 하나의 record가 삽입되기 전 인덱스 노드 하나를 만들고 이를 Root가 가리키게 함. ptri[0]에 NULL을 넣음(이것은 이 노드가 index 구조의 leaf 노드임을 나타낸다.) 데이터 노드를 하나 만듬. record를 데이터 노드에 삽입. 인덱스 노드의 ptrd[0]가 이 데이터 노드를 가리키게 한다. 인덱스 노드의 ptri[1] 에 0을 넣는다. ≫ 초기상황(아직 B+Tree의 형태를 갖추지 못함.) 임을 나타냄. ※ 초기 상황(초반부) 삽입 ● Root가 NULL이 아닌 경우의 초반부 삽입 Sequence set에 데이터 노드 하나만 존재하는 경우 Root 인덱스 노드의 Pointer[1]이 NULL인지를 체크..

※ 전체 과정 (삽입될 record가 변수 in_rec에 들어있다고 가정한다.(key값은 in_key에 있다.) ) 먼저 in_rec를 leaf 노드에 넣고자 시도한다. leaf 노드를 탐색하기 위해 B-tree의 루트 노드에서 출발하여 pointer를 따라 leaf 노드에 도달할 때까지 내려간다. 도달한 leaf 노드를 Pointer curr 가 가리키게 한다. 쌍 를 curr가 가리키는 노드 내에 적당한 위치 에 넣어야 한다. Case 1: curr 노드에 빈 공간이 존재한다 를 적당한 위치에 삽입하고 알고리즘을 종료한다. Case 2: curr 노드에 빈 공간이 존재하지 않는다. Big node(bnode)를 사용한다. bnode(정상 node보다 record와 pointer가 하나씩 더 많은 노드..

다방향 탐색 트리를 이르는 말. 데이터 레코드의 순차적 처리와 직접적 처리를 모두 지원하는 다단계 트리 구조라고 정의되어 있다. ※ B-tree의 특징 삽입 및 삭제 알고리즘은 Tree가 Balance 되는 것을 보장한다. 즉, 삽입과 삭제가 일어나도 B-tree의 기본 구조를 지켜서 진행된다. (Balance : 모든 leaf 노드가 (거의) 같은 level에 속해야 한다.) Branching factor가 2 이상의 큰 값일 수 있다. ( -> 빠른 탐색 시간을 보장한다.) m-원 탐색 트리 성질을 만족해야 한다. (1. 탐색의 효율성을 증가 2. record들을 정렬된 순서로 출력한다.) 데이터의 저장 및 탐색이 가장 많이 이용되는 데이터 구조 중의 하나이다. ※B-tree의 정의(Definitio..