SunFly의 코딩 및 정보 블로그

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

※ Deletion(불완전한 버전) ex)Delete X(2) HA record link 0 NULL 1 W(1) 2 2 Z(2) 3 3 Y(1) 5 4 NULL 5 M(3) NULL 6 NULL (1) h = 1 (2) h (=1)로부터 chain에서 삭제할 record 찾음 -> loc 2에서 X 발견 (4) s = 2 (5) s (=2)로부터 chain에서 2를 HA로 가지는 마지막 record 찾음 -> loc 4에서 Z 발견 (7) r = 4 (8) loc r (=4)의 record Z를 loc s (=2)의 record로 copy Z (2) (9) s = r (= 4) (10) Go to (5) (5) s (=4)로부터 chain에서 4를 HA로 가지는 마지막 record 찾음 (6) 발견 실..

※ Chain을 이용한 방법(=Chaining, 폐쇄주소법이라고도 불림.) -> 동일 Chain 내에서 Coalescing이 일어나므로 coalesed hashing이라고 불림. ※Hashing의 Insertion 방법 1. record의 key값이 HA(Home address)를 얻어 삽입되기 위해서 Hash되어야한다. ≫case 1. HA가 비어있는 경우, 그 주소에 record를 삽입한다. (만약 동일한 record가 이미 존재하면 삽입하지 않고 제거한다.) ≫case 2. HA가 이미 차있다면, table의 맨 밑에서부터 올라오면서 빈자리를 찾는다.(만약 table에 빈자리가 없다면 record는 삽입될 수 없다.) 빈자리에 record를 넣고 삽입된 주소의 pointer를 HA의 pointer와..

※ 맨 아래층이 아닌 인덱스 노드로의 삽입 : type-2 curr가 맨 아래층보다 위의 층의 노드이며 여기에 삽입하는 경우 B-tree의 삽입과 동일한 방식으로 일어남. 다만, 사용할 포인터 필드는 ptri 이다. (즉, index node에 대한 Pointer를 저장하는 필드.) Case 1: 빈자리가 있는 경우 : 순서에 맞춰 삽입하고 종료 Case 2: 빈자리가 없는 경우 : overflow 발생 ● Case 1: 빈공간이 있는 경우 ● Case 2: 빈공간이 없을 경우 ※ 삽입 과정에서 부모 주소의 관리 : Stack 이용 삽입과정에서 데이터노드를 찾아가는 과정에서 각 노드의 Pointer를 stack에 저장 인덱스 구조의 Root에서 시작 아래로 내려갈 때마다 그 직전에 노드의 주소를 stac..

※ 정상상황에서의 삽입 ● 초기상황이 아닌 경우가 정상 상황(Root 노드의 ptrd[1] != NULL인 상황) ● Root에서 출발하여 삽입할 record가 들어가야 할 데이터 노드를 찾아야 한다. 삽입할 record의 key값이 new_key라고 하자. Root노드에서 출발하여 navigation을 반복하여 인덱스 구조의 leaf노드에 도달하도록 한다. "new_key

※ 첫 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인지를 체크..

■ 실제로 가장 널리 활용되는 구조 ■ 인덱스 구조와 시퀀스셋(data node set)으로 구성됨. ※ 인덱스 구조(Index) 각 노드가 record 대신 key값만 저장된 B-tree 구조 노드의 key값은 데이터 노드로 찾아가는데 이용하는 navigation에 이용 B-tree의 요구와 조건은 모두 충족시켜야함. ※ 시퀀스셋(data node set) 데이터 노드들의 연결리스트로 구성됨. 노드는 데이터 즉 record들을 가짐. (모든 레코드가 저장됨.) 모든 record는 key값 순서로 정렬되어 있음. ▶인덱스 구조의 루트 노드를 제외한 모든 노드들은 "at least half full(절반 이상)" 조건을 만족함. (단, 초기 상황은 예외) ※ B+tree의 장점 범위 탐색(Range Sea..

■ 탐색을 효육적으로 하기 위한 자료구조 ※ 특징 이진트리이며 모든 원소는 서로 다른 유일한 키(key)를 가진다. (왼쪽 sub-트리의 key값) 루트 노드의 키값) : 루트 노드의 오른쪽 sub-트리에 대해서 탐색연산 수행. ▷예시 코드 BinTree* searchBST(BunTree* b..

※B-tree 개발 • 내용 B-tree 프로그램을 구현하고 실험한다. 주어진 데이타를 B-tree 에 모두 저장하고, 여기의 레코드를 탐 색, 삭제 해 보는 작업을 실험해 본다. B-tree 노드의 capacity order d 는 다음처럼 상수로 선언되도록 하고 이 d 를 이용하여 모든 변수의 타입을 선언하도록 하고 프로그램에서도 이 d 를 이용토록 한다. (capacity order d = 2 로 해서 실험 해 볼 것). • 삽입할 데이타는 두 개의 텍스트 화일 Com_names1.txt , Com_names2.txt 에 들어 있는 업소명들 이다. 하나의 업소명은 하나의 레코드에 저장된다. 레코드는 업소명의 문자열과 업소명의 길이의 두 개 의 필드를 가지며 다른 필드는 없다. 따라서 하나의 레코드의..

※ 삭제(Deletion) 알고리즘 (0) 삭제하고자 하는 key값을 가진 노드 탐색 (1-1) 찾은 노드가 단말 노드라면 단말 노드에서 해당 레코드를 삭제 (1-2) 찾은 노드가 단말 노드가 아니라면 ① 삭제될 record의 오른쪽 포인터가 가리키는 sub-트리에서 가장 작은 key값을 가지는 record를 찾음. ② 삭제될 레코드의 key값과 찾은 record의 key값을 교환하고 단말노드로 옮김. ③ 단말 노드에서 해당 record를 삭제 (2) record 삭제 후 남아있는 record의 수가 노드가 유지될수 있는 최소한의 수(d개) 미달이면 underflow상황을 처리한다. (2-1) Redistribution(재분배)가 가능(=최소 record 수 이상을 포함한 형제 노드에서 이동) (즉, f..