Krafton_Jungle/Study

RB-Tree RB-Tree란? 자가 균형 이진 탐색 트리의 일종으로, 이진탐색 트리를 가지고 있고, 노드의 삽입과 삭제를 할 때 전체 트리의 높이를 균형있게 제한하는 이진 탐색 트리이다. RB-Tree의 특징 RB-Tree의 가장 큰 특징은 각각의 노드가 색깔에 관한 정보를 갖는다는 점과, 규칙을 만족하지 않으면 케이스 별로 노드를 회전시키며 균형을 맞춘다는 점이다. (노드를 승격시키는 B트리와의 차별점) NIL 노드 NIL 노드란, 실제 데이터를 갖는 트리가 아닌, 리프노드 끝에 NULL 대신 NIL 노드를 선언해 해당 트리의 끝을 알린다. (NIL 노드를 사용하면 트리의 끝을 NULL 포인터로 처리하는 대신 트리의 모든 노드를 동일한 방식으로 처리할 수 있다. 이로 인해 코드의 일관성과 가독성이 향..

C, 키워드 포인터 주소값 모든 데이터는 해당 데이터를 담고 있는 주소값을 가지고 있다. 여기서 주소값이란 데이터가 저장되어 있는 메모리의 위치. 만약 int형 데이터를 선언한다면, 해당 시작 주소값으로부터 4byte만큼의 메모리 영역을 사용하게 된다. 포인터의 개념 여기서 해당 int 자료형의 첫번째 주소값을 가르키도록 선언할 수 있는데, 이것을 포인터라고 한다. int n = 100; // 변수의 선언 int *ptr = &n; // 포인터의 선언 포인터의 연산자 해당 데이터가 저장되어있는 첫번째 주소값은 주소연산자(&) 로 표현하고 이를 가르키는 포인터는 참조연산자(*)로 선언하게 된다. 여기서 주소 연산자 앰퍼샌드(ampersand)라고 부르며, 사용법은 위에 보이는 예시와 같이 변수 이름 앞에 ..

자료구조 Binary Search Tree 기본 제공 함수 ////////////////////////////////////////////////////////////////////////////////// /* CE1007/CZ1007 Data Structures Lab Test: Section F - Binary Search Trees Questions Purpose: Implementing the required functions for Question 5 Implementing 'remove node' operation for BST*/ ////////////////////////////////////////////////////////////////////////////////// #includ..

자료구조 Stack and Queues 기본 제공 함수 ////////////////////////////////////////////////////////////////////////////////// /* CE1007/CZ1007 Data Structures Lab Test: Section C - Stack and Queue Questions Purpose: Implementing the required functions for Question 1 */ ////////////////////////////////////////////////////////////////////////////////// #include #include ///////////////////////////////////////..

알고리즘 1890 점프 # 실패코드! import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) queue = deque() # x,y 좌표값 추가 queue.append((0,0)) res = 0 while queue: cur_y, cur_x = queue.popleft() if cur_y == n-1 and cur_x == n-1: res += 1 continue distance = arr[cur_y][cur_x] new_x = cur_x + distance if distance !..

11723 집합 import sys input = sys.stdin.readline def add(S, x): x = int(x) S |= (1

CSAPP 기계수준 프로그램에서 제어와 데이터의 결합 포인터 포인터 이해하기 지금까지 어셈블리어를 사용하며 계속 사용했던 () 참조 방식을 포인터라고 생각하고 학습했다. 포인터는 C 언어의 핵심으로 주소의 값을 가르키는 화살표라고 이해하면 된다. 모든 포인터는 특정값을 가진다. 이 값은 특정 자료형을 갖는 어떤 객체의 주소다. 포인터에 대한 이해는 linked list를 직접 구현해가며 학습했다. #include #include #include // // Created by 전병준 on 24. 4. 9. // typedef struct NODE{ int data; struct NODE* next; } node; node* list; // 초기화 void init() { if (list == NULL) {..

CSAPP 이기종 자료구조 (Heterogeneous) 이기종 자료구조란? 다른 여러가지의 데이터를 포함하고 있는 구조체(struct)와 공용체(Union)을 뜻한다. 구조체(struct) C 언어의 구조체(structure)는 다양한 데이터 타입의 멤버들을 하나로 묶어서 새로운 데이터 타입을 정의하는 데 사용. 자바의 class의 개념과 아주 약간 비슷함 구조체의 offset 각 구조체의 필드값에 따른 byte 용량으로 정한다. char = 1byte, long = 8byte... 공용체(union) 말 그대로 필드값의 가장 큰 Byte만큼만 메모리를 할당하고, 그 메모리를 모든 필드값들과 공유하며 사용함. 메모리를 효율적으로 사용할 수 있지만, 한번에 하나의 필드값밖에 할당할 수 없어 지금은 잘 사용..

알고리즘 Dynamic Programming DP란? 점화식을 사용해 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 큰 문제에 대입해서 푸는 방법 계산값을 재탕한다는 의미로 받아들였다. 알게모르게 알고리즘 문제를 풀이하며 여러번 사용했던 방법. DP를 사용하는 이유 난 이 이유를 백준의 피보나치를 풀이하며 찾았는데, 기존 피보나치의 경우 일반적인 재귀로 풀면 O(n²)이지만 dp로 값을 재탕하면 시간 복잡도를 O(n)으로 줄일 수 있다. 자세한 내용은 2748 피보나치수 2 문제를 풀어보면 바로 감이 잡힌다. 구현법 젓번째로는 Bottom-Up 방식으로 DP 테이블을 만들어 해당 테이블을 만족하는 점화식을 생성하고, 그 식을 바탕으로 반복문을 사용해 접근하는 방식이다. 해당 방식의 장점은 재..

CSAPP 프로세서 데이터 전송 대부분의 데이터 전달은 레지스터를 통해서 일어난다. (rax, rsi, r8 등등) 레지스터에 저장되는 값을 프로시저에서 다시 호출해 데이터를 전달하는 형식. 함수가 여섯개 이상의 정수형 인자를 가질 때, 다른 인자들은 스택으로 전달된다. (인자를 저장하는 영역이 따로 있음) 스택에서의 지역 저장 공간 지역 데이터가 스택 내부 Local variables에 저장되는 경우는 다음과 같다. 지역 변수의 수가 레지스터보다 더 많을때, 지역변수의 &연산자가 사용되어, 변수의 주소를 생성해야 할 때, 배열 또는 구조체일때 레지스터를 이용하는 지역저장소 프로그램 레지스터들은 모든 프로시저들이 공유함 피호출자 레지스터는 호출자가 나중에 사용할 경우를 고려해서 레지스터 값을 덮어쓰지 않..