연관 포스팅(RB Tree 이론) [Krafton Jungle | TIL_22.11.27] RB Tree 이론 균형 이진 탐색 트리(Balanced BST) 루트 노드로 부터 시작해서 찾고자하는 key 를 각 레벨에 따라 한번의 비교를 통해 key 값을 찾을 수 있다. $O(h)$ (h : 높이) 의 시간 복잡도를 가진다. insert, delete 연 olive-su.tistory.com ☁️ Overview 이진 트리의 특성을 기반으로 한다. RB Tree의 특성 모든 노드는 레드이거나 블랙이다. 루트는 블랙이다. 모든 리프는 블랙이다. 노드가 레드이면 그 노드의 자식은 모두 블랙이다. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 블랙 노드를 포함한다. ADT(Abstract..

균형 이진 탐색 트리(Balanced BST) 루트 노드로 부터 시작해서 찾고자하는 key 를 각 레벨에 따라 한번의 비교를 통해 key 값을 찾을 수 있다. $O(h)$ (h : 높이) 의 시간 복잡도를 가진다. insert, delete 연산 모두 search의 영향을 받는다. 이진 트리의 높이 $lg(n+1)

헤더파일로 나 를 포함시켜야한다. 메모리 할당 함수 : malloc 메모리 할당 및 초기화 : calloc 메모리 추가 할당 : realloc 메모리 해제 함수 : free 동적할당: 프로그램 실행 중에 동적으로 메모리를 할당하는 것 동적으로 메모리를 할당할 때는 ‘Heap’영역에 할당한다. 정적 메모리 할당 방법(static) : 데이터를 저장할 때 변수를 선언하고 사용하는 방식 프로그램이 시작하기 전에 사용할 메모리공간을 정해놓고 시작 정적 메모리 할당의 문제점 메모리의 크기에 따라 메모리가 낭비되거나 필요에 따른 메모리 공간이 부족해 프로그램을 다시 짜야하는 경우가 발생 void* malloc(size_t size); malloc이 void* 를 리턴하는 이유 동적으로 메모리를 할당할 때 정수를 저..

C언어에서의 자료형 크기 구분 자료형 크기 범위 기본형 void – – 문자형 (signed) char 1 byte -128 ~ 127 unsigned char 1 byte 0 ~ 255 wchar_t 2 byte 0 ~ 65,535 정수형 bool 1 byte 0 ~ 1 (signed) short (int) 2 byte -32,768 ~ 32,767 unsigned short (int) 4 byte 0 ~ 65,535 (signed) int 4 byte -2,147,483,648 ~ 2,147,483,647 unsigned int 4 byte 0 ~ 4,294,967,295 (signed) long (int) 4 byte -2,147,483,648 ~ 2,147,483,647 unsigned long ..

☑️ To-do 이진 트리 이론 정리 전위, 중위, 후위 순회 Introduction to Algorithms 이진 트리 Week03 문제 풀이 1707 / 21606 이진 트리 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리 자식 노드의 최대 개수는 2이다. 💡 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다! 완전 이진 트리 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리 마지막 레벨을 제외하고 모든 레벨에 노드를 가득채운다. 왼쪽으로 노드들이 치우친 상태 이진 검색 트리(Binary Search Tree) Field key : 키 값 left : 왼쪽 자식 right : 오른쪽 자식 p(parent) : 부모 노..

☑️ To-do 그래프 이론 기본 정리 Week03 문제 풀이 1991 / 11725 / 1707 / 2178 / 1260 / 11724 / 2606 / 5639 그래프 🆚 트리 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 트리(tree) 관련 용어 노드(node) (=정점) 엣지(edge) (=간선) 루트(root) : 최상위 노드 리프(leaf) 단말 노드 (terminal node) 외부 노드 (external node) 리프를 제외한 노드 : 비단말 노드(non-terminal node = inter..

문제 1 소요 시간 : 30분 카테고리 : 분할 정복, 재귀 input이 잘린 걸 모르고 이상한 input으로 테스트하다가 문제가 이해가 안돼서,, 문제 이해에만 10분을 날렸다. 문제를 제대로 안읽어서 전체가 0또는 1일때도 () 안에 넣어서 출력하게끔 구현해서 10분을 삽질함 🏃‍♂️ Try 1 Fail 83% import sys input = sys.stdin.readline n = int(input()) graph, answer = [], [] dx = [0, 1, 0, 1] dy = [0, 0, 1, 1] for _ in range(n): graph.append(list(input().rstrip())) # 색이 모두 동일한 지 판단 def validation(n, x, y): color = g..

☑️ To-do 이분 탐색 이론 정리 이론 탐색 문제 접근 방식 정리 Week02 문제 풀이 11053 / 2630 / 1629 / 10830 / 6549 / 13334 이분 탐색(Binary Search) 데이터가 정렬되어있는 상태 타깃 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 시간복잡도 $$O(lgN)$$ 이진 탐색 과정 1. mid 값 특정 2. if mid > target, 왼쪽 탐색 3. if mid < target, 오른쪽 탐색 4. if mid == target, 탐색 종료 파라메트릭 서치(Parametric Search) 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것 1. 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경..

☑️ To-do 힙 정렬 코드 내, heapify 부분 로직 이해 스택 계산기 코드 이해 프로젝트 AWS NBP로 마이그레이션 프로젝트 자문 멘토링 소프트웨어 아키텍쳐 고민 📝 문제 특정 배열의 원소들이 정렬되는 과정을 힙과 배열로 그려 본다. 스택을 활용해 사칙 연산이 가능한 계산기를 구현하는 과정을 공부해본다. 📄 1번 문제 이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조 완전 이진 트리: 좌우 균형을 이루는 이진 트리 def heap_sort(arr): def down_heap(arr, left, right): temp = arr[left] parent = left # 왼쪽 노드의 인덱스(부모 노드라고 가정) while parent < (right + 1) // 2: ..