Falling in Love with Coding

AVL 트리의 개요 1. AVL의 균형 1) 균형 인수(Balance Factor) ▪ 트리의 균형을 점검할 때 사용하는 인수 ▪ 노드 마다 오른쪽 서브 트리의 높이에서 왼쪽 서브 트리의 높이를 뺀 것 ▪ AVL 트리에서 균형 인수의 값은 반드시 -1, 0, +1 중 하나임 2) 균형 인수의 점검 ① 왼쪽 트리로부터 노드 K를 삭제하면 균형 인수 중 -2가 생겨 오른쪽 트리처럼 균형이 깨지게 됨 ② 왼쪽 트리에서 노드 F의 오른쪽 자식에 삭제가 가해졌다면 루트 F를 기준으로 오른쪽 서브 트리의 높이가 감소하게 됨 ③ 삭제로 인해 어떤 노드의 균형 인수가 범위를 벗어난 경우 : 균형이 깨진 노드는 삭제 위치의 부모 노드(F)의 왼쪽 자식 노드와 손자 노드까지 가는 길목에 있는 F, D, E 중에 존재하게 ..

히프 트리 구조 1. 히프의 개요 1) 정의 ▪ 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 ▪ 최대 히프(Max Heap) - 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≥ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 큰 노드 ▪ 최소 히프(Min Heap) - 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 - {부모 노드의 키 값 ≤ 자식 노드의 키 값} - 루트 노드: 키 값이 가장 작은 노드 2) 히프 트리 예 3) 히프의 추상 자료형(ADT Heap) ▪ 데이터 : n개의 원소로 구성된 완전 이진 트리 ▪ 각 노드의 키 값은 그의 자식 노드의 키 값보다 크거나 같음 - 부모 노드..

탐색 연산 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) ▪ 최대 힙과는 정반대 ▪ 키 값이 작을수록 우선 순위가 높음 - 정렬 ▪ 이진 탐색 트리는 값의 크기를 기준으로 삽입되기 때문에 왼쪽 노드보다 오른쪽 노드가 더 큰 값을 가짐 ▪ 힙은 키를 기준으로 값을 정렬하기 때문에 값들끼리의 상관관계는 없음 힙의 특징 - 힙의 구성 힙 = "완전 이진 트리" ▪ 배열로 표시하는 것이 가장 효율적 ▪ 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행 ▪ 노드 필기하는 순서로 트리를 순회하면서 인덱스를 부여 ▪..

큐, 스택과 달리 중요도에 따라 먼저 처리하는 방식 - 시간에 따른 우선 순위 : 스택, 큐 -시간 외 다른 가치 우선 순위 : 우선 순위 큐 ▪ 우선 순위 큐는 스택이나 큐 보다 일반적인 구조 - 키의 필요 여부 ▪ 에서는 키(= 우선 순위 값) 필드가 필요 ▪ , 에서는 시간에 따라 자료구조를 조직화하게 되므로 키 필드가 불필요 추상 자료형 우선 순위 큐 - 용어 ▪ Create : 새로운 우선 순위 큐를 만들기 ▪ Destroy : 사용되던 우선 순위 큐를 파기하기 ▪ Add : 현재 우선 순위 큐에 새로운 레코드를 삽입하기 ▪ Remove : 가장 우선 순위가 높은 레코드를 삭제하기 ▪ IsEmpty : 현재 우선 순위 큐가 비어있는지 확인하기 - 우선 순위 큐에서의 삭제(Remove) 작업 ▪ ..

큐잉 이론(Queueing Theory) - 서버의 수 : 2대 - 각 서버의 수행 시간 : 1분 - 객체의 유입량 : 30명 / 1시간 * 평균 고객 수, 기다리는 고객 수 예상 1. 추상 큐(Abstract Queue) 1) 구성 및 삽입과 삭제 방법 ▪ 선형 정렬을 이용 ▪ 삽입과 삭제가 개별적으로 실행 ▪ 삽입(Push Into)에 어떤 객체든 제한이 없으며, 그 객체는 큐의 Back ▪ 큐의 처음 객체는 Front ▪ 삭제(Pop From)는 큐의 현재 Front에서 실행 2) 선입 선출(Firtst-In-First-Out, FIFO) 자료구조 3) 4가지 연산 * 2가지 예외 상황 ▪ 빈 큐에서 삭제(Pop) 연산 혹은 첫 객체(Front) 참조 시 정의되지 않음 2. 응용 분야 1) 손님-제..

스택의 괄호 검사 1. 개요 - 스택의 괄호 검사 ▪ 수식에 포함되어 있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어 있음 ▪ 후입선출 구조의 스택을 이용하여 괄호를 검사함 ▪ 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사 ① 왼쪽 괄호를 만나면 스택에 Push ② 오른쪽 괄호를 만나면 스택을 Pop하여 마지막에 저장한 괄호와 같은 종류인지를 확인 - 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임 ▪ 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨 - 수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임 2. 알고리즘 - 괄호의 쌍 검사 알고리즘 testPair( ) exp ← Expression; Stack ..

기본 연산 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 (..