Falling in Love with Coding

정렬의 개요 1. 실행 방법에 따른 분류 1) 비교식 정렬과 분산식 정렬 - 비교식 정렬(Comparative Sort) ▪ 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법 - 분산식 정렬(Distributive Sort) ▪ 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법 2. 정렬 장소에 따른 분류 1) 내부 정렬과 외부 정렬 ① 내부 정렬(Internal Sort) ▪ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 ▪ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 ▪ 내부 정렬 방식 ② 외부 정렬(External Sort) ▪ ..

2-3-4 트리 1. 개요 - 2-3-4 트리의 정의 ▪ O(log2N)과 O(log4N) 사이의 탐색 효율을 가짐 ▪ 추가로 4-노드를 정의 - 자식 노드로 가는 링크(Link)가 4개이고 키가 3개인 노드 - 왼쪽 자식(Left Child), 오른쪽 자식(Right Child), 왼쪽 중간 자식(Left Middle Child), 오른쪽 중간 자식(Right Middle Child)으로 구분 - 2-3-4 트리의 노드 구성 2. 2-3-4 트리의 필요성 1) 2-3-4 트리의 장단점 ▪ 높이를 log4N으로 조금 더 낮추기 위함 ▪ 리프 노드 근처의 널 포인터 공간도 2-3 트리에 비해서 더 많아짐 ▪ 필요시 최대 3개의 키를 비교해야 하는 시간적 부담 2) 단일 패스 삽입 ▪ 2-3 트리는 리프 노..

2-3트리 개요 - 2-3트리의 특징 ▪ AVL은 균형 트리를 지향하는 반면 2-3 트리는 완전 균형 트리를 지향함 ▪ AVL 트리에 비해 상대적으로 단순한 논리 ▪ 2-노드 또는 3-노드 모두 가능 ▪ 이진 탐색 트리와 마찬가지로 리프 노드에 삽입 - 삽입 시 높이 변화의 특성 * 2-3트리 ▪ 반복된 삽입에도 2-3 트리의 높이는 좀처럼 증가하지 않음 ▪ 3-노드를 사용해서 최대한 많은 레코드를 높이 변화 없이 수용 * 이진 트리 ▪ 이진 탐색 트리의 높이는 삽입할 때마다 리프 노드 아래로 1만큼 증가 - 여러 가지 방법 ▪ 삽입, 삭제를 위해서는 삽입 대상 노드의 부모 노드를 접근해야 함 ▪ 삽입 시에 중간 키를 올리기 위해서, 또 삭제 시에 부모 노드의 키를 아래로 내리기 위해서 이진 트리는 부모..

탐색 연산 1. 탐색 연산의 기본 방법 - 연산 방법 ▪ 루트에서 시작함 ▪ 탐색할 키 값 x를 루트 노드의 키 값과 비교함 * 키 값 x = 루트 노드의 키 값 인 경우 => 원하는 원소를 찾았으므로 탐색 연산 성공 * 키 값 x 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행 * 키 값 x > 루트 노드의 키 값 인 경우 => 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행 ▪ 서브 트리에 대해서순환적으로 탐색 연산을 반복함 2. 탐색 연산 알고리즘 1) 이진 탐색 트리에서의 탐색 연산 알고리즘 searchBST(bsT, x) p ← bsT; if (p = null) then return null; if (x = p.key) then return p;..

분할 기법 1. K 번째 작은 수 찾기 1) 문제 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는? 2) 문제 풀이 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수 구하기 1. 10, 7, 2, 8과 3, 1, 9, 6으로 분할 2. 10, 7, 2, 8 중 세 번째 작은 수는 8 3. 3, 1, 9, 6 중 세 번째 작은 수는 6 4. 작은 문제의 해결책이 큰 문제의 해결책으로 이어지지 않는다. 2. 분할(Partition) ① 임의로 피벗 설정 ② 다운 포인터와 업 포인터 설정 ③ 다운은 피벗보다 작거나 같은 것, 업은 피벗보다 크거나 같은 것 찾음 ④ 스와핑 ⑤ 포인터가 일치하거나 교차할 때까지 ③, ④를 반복 ⑥ 업 포인터 ..

재귀란? - 수학이나 컴퓨터 과학 등에서 자신을 정의할 때, 자기 자신을 재참조하는 방법 - 재귀 함수의 형태로 많이 사용 재귀 호출의 개요 1. 재귀 호출이란? 1) 정의 "자기 자신을 호출하여 순환 수행되는 것" ▪ 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식 보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음 2) 특성 대표적인 분할 정복 알고리즘 ① 문제의 크기 N ② 큰 문제를 작은 문제로 환원 ③ 작은 문제 역시 큰 문제와 유사함 ④ Self Call, Boomerang 2. 재귀 호출의 예 1) 팩토리얼(Factorial) 연산 ▪ 1~n의 모든 자연수를 곱하여 구하는 연산 ▪ 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 ..

힙를 이용한 우선 순위 큐 힙와 관련된 주요 개념 이해 1) 힙(Heap) “쌓아 놓은 더미” 2) 용어 - 최대 힙(Max Heap) ▪ 키 값이 큰 레코드가 우선 순위가 높은 것으로 간주 ▪ 루트 노드의 키가 가장 큼 - 최소 힙(Min Heap) ▪ 최대 힙과는 정반대 ▪ 키 값이 작을수록 우선 순위가 높음 - 정렬 ▪ 이진 탐색 트리는 값의 크기를 기준으로 삽입되기 때문에 왼쪽 노드보다 오른쪽 노드가 더 큰 값을 가짐 ▪ 힙은 키를 기준으로 값을 정렬하기 때문에 값들끼리의 상관관계는 없음 힙의 특징 - 힙의 구성 힙 = "완전 이진 트리" ▪ 배열로 표시하는 것이 가장 효율적 ▪ 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행 ▪ 노드 필기하는 순서로 트리를 순회하면서 인덱스를 부여 ▪..

기본 연산 Push와 Pop 1. Push와 Pop 연산 - 스택에서의 원소 삽입/삭제 과정 * 공백 스택에 원소 A, B, C를 순서대로 삽입하고 한번 삭제하는 연산과정 동안의 스택 변화 2. Push 알고리즘 - 스택의 Push 알고리즘 ① top ← top+1; ▪ 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 > 먼저 top의 위치를 하나 증가(+1) ▪ 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 > 오버플로우(Overflow) 상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료 ② S(top) ← x; ▪ 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입 push(S, x) top ← top+1; // ① if (..

1. 개요 - 접근, 삽입 및 삭제 * 스택 탑만 접근 가능 * 한쪽 끝에서 삽입, 삭제 ▷ 삽입, 삭제 위치를 스택 탑 부근으로 제한 ▷ 구현 자료구조에서 탑이 아닌 다른 곳을 접근할 수 있어도 하지 않기로 약속 - 연산 스택 탑에 푸시(Push) - 삽입, 팝(Pop) - 삭제 2. 추상 자료형 스택 - 주요 작업 - 주요 함수 ▪ GetTop(Push(S, X)) = X ▪ Pop(Push(S, X)) = S ▪ IsEmpty(Create( )) = TRUE ▪ IsEmpty(Push(S, X)) = FALSE ▪ GetSize(Push(S, X)) = GetSize(S) + 1 스택의 구현 1. 배열을 이용한 스택의 구현 - 연산 // StackA.h (C Interface by Array) #d..

연결 자료구조 1. 순차 자료구조의 문제점 - 문제점 1) 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요 * 원소의 개수가 많을수록 원소들이 이동 작업으로 인한 오버 헤드가 많음 * 삽입, 삭제, 연산이 많이 발생하는 경우에 성능 상의 문제 발생 2) 순차 자료구조는 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐 2. 연결 자료구조의 정의 - 연결 자료구조(Linked Data Structure) : 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 * 각 원소에 저장되어 있는 다음 원소의 주소(Pointer)에 의해 순서가 연결되는 방식 -> 물리적인 순서를 맞추기 위한 오버 ..