본문 바로가기

전체 글78

RB_TREE(삭제) 레드 블랙 트리의 삭제의 경우 삽입보다 다소 복잡하다고 책에서 말한다. (다소?...) 머리가 나빠 동기들이 많이 도와줬음에도 혼자 이해하는데 2일이 꼬박 걸린 듯하다. 아무튼 내가 이해한 바를 정리해 보려 한다. 삭제의 시간 복잡도 삭제도 삽입과 마찬가지로 O(logN)의 시간 복잡도를 가진다. RB트리의 삭제 우선 노드의 삭제는 두 가지 방법으로 진행할 수 있다. 1. 삭제하려는 노드가 (Z)라면 Z의 오른쪽의 최솟값을 이동시켜 값을 보완한다. 2. Z의 왼쪽의 최댓값을 Z의 위치로 이동시켜 값을 보완한다. 그 이유는 RB트리 또한 이진트리의 원칙을 기본으로 하기 때문에 삭제되는 노드의 오른쪽(삭제되는 노드보다 큰 값들의 집합)의 가장 왼쪽(최솟값)을 노드로 이동시킨다면 이진트리의 원칙이 깨지지 않고.. 2021. 12. 8.
RB_Tree(레드블랙트리)_삽입 이진트리의 경우 계속하여 큰값이나 작은값이 들어올 경우 노드가 한쪽으로 치우칠 수 가 있다. 이경우 특정 key값을 탐색하는데 시간이 늘어나는 단점이 있으며 이를 보완한 것이 자가균형이진탐색트리 Red-Black Tree이다. RBtree의 특성 모든 노드의 색은 빨간색 혹은 검은색이다. 루트 노드는 검은색 이어야 한다. 모든 리프노드는 루트노드와 같은 검은색이다. 빨간색 노드의 자식은 모두 검은색이다. 루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다 RBtree 시간 복잡도 O(logn): RBtree 삽입 기본적 삽입은 이진트리의 삽입과 같다 그러나 삽입과정에서 루트 노드는 검은색이어야 하며 빨간색 노드의 자식은 검은색이어야 한다는등 조건이 있어 RB트리의 특성을 만족하.. 2021. 12. 5.
Dynamic Memorry Allocation in C 참고 : 위키피디아 동적메모리할당. 동적 메모리 할당 ? 사용자가 정의한 지역변수와 함수는 스택(stack)영역에 저장되고 함수가 호출되면 스택영역의 메모리를 사용하여 커지고 리턴된면 줄어드는 방식으로 메모리가 사용된다. 작성자가 프로그램의 실행 시간 동안 사용할 메모리 공간을 할당받고자 한다면 메모리 동적할당을 이용하여야한다. 메모리 동적 할당이란 사용이 끝나면 운영체제가 쓸 수 있도록 반납하고 다음 요구가 오면 재 할당을 받을 수 있는것을 말하며 동적 할당된 메모리는 힙(heap)영역에 할당되고 해제된다. C/C++의 경우 동적으로 할당된 메모리는 프로그래머가 명시적으로 해제 하기 전까지 메모리 공간이 계속 유지된다. 힙 영역 동적 메모리 할당은 프로세스의 힙영역에서 할당한다. 프로세스가 종료되면 운.. 2021. 12. 3.
컴파일 시스템 소스파일 (. c)을 실행파일로 번역하기 위해 4단계( 전처리기, 컴파일러, 어셈블러, 링커) 단계를 거치는데 위 단계를 합쳐 컴파일 시스템이라 부른다. #include int main() { printf("Hello, World \n"); return 0; } 전처리 단계 (pre-processor) : 전처리기(CPP)는 C프로그램을 #문자로 시작하는 directive에 따라 수정한다. 위의 예에서 보면 #incluide는 전처리기에 시스템 헤드 파일(stdio.h)을 프로그램 문장에 직접 삽입하라고 지시한다. 그 결과 (. i )로 끝나는 새로운 C 프로그램이 생성된다. 컴파일 단계 (compiler) : 텍스트파일 (. i) 프로그램 파일을 텍스트 파일 (. s) 파일로 번역하며 이 파일에 어셈블.. 2021. 12. 3.
LCS(Longest Common Subsequence) 최장 공통 부분 수열 최장 공통 부분 수열 (Longest Common Subsequence) 문제란? 주어진 여러개의 수열 모두 부분수열이 되는 수열중 가장 긴 것을 찾는 문제이다. 이 문제와 아래 최장공통 부분 문자열 문제와 혼동하면 안된다. 최장 공통 부분 문자열(Longest Common Substring) 문제란? 주어진 여러개의 문자열 모두 부분수열이 되는 문자열 중 가장 긴 문자열을 찾는 문제 예시 가나다라마바사 가하나카마바사 LCSubsequence 가나다라마바사 가하나카마바사 LCSubstring 가나다라마바사 가하나카마바사 LCS 문제는 더 작은 '부분문제'로 나뉠 수 있고 이것을 반복해 더 간단한 부분문제로 쪼갤 수 있다. 즉 동적 프로그래밍 문제풀이기법으로 접근될 수 있다. 부분문제는 수열이 짧아질 수록.. 2021. 11. 26.
DP( Dynamic Programing) 동적프로그래밍 DP 큰 문제를 한번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법으로 작은 문제들을 매번 재계산 하지 않고 값을 저장해두었다가 재사용하는 기법이다. 조건 Problem이 더 작은 Subproblem으로 쪼개질 수 있어야 한다. Subproblem 의 솔루션으로 더 큰 Subproblem의 솔루션을 구할 수 있어야 한다. Subproblem이 겹칠때(memorization을 통해 필요한 계산수를 줄일 수 있다) 백준 피보나치 수열 2 #bottom up방식 fib_array = [0, 1] def fib_dp(n): if n==0: return 0 elif n==1: return 1 for i in range(2, n+1): num = fib_array[i-2]+fib_ar.. 2021. 11. 25.

티스토리툴바