재민의 IT 공부기록

이진트리의 순회는 다음과 같은 과정을 통해 이루어져야 한다. 1) 트리에 있는 모든 노드를 단 한번씩만 방문해야 함 2) 왼쪽 서브트리는 항상 오른쪽 서브트리보다 먼저 방문해야 함 순회 방법으로는 총 세가지가 있는데, LVR(중위순회), VLR(전위순회), LRV(후위순회) 이다. 1) 중위순회 왼쪽 서브트리 방문 > 루트 노드 방문> 오른쪽 서브트리 방문 2) 전위순회 루트노드 방문> 왼쪽 서브트리 방문> 오른쪽 서브트리 방문 3) 후위순회 왼쪽 서브트리 방문> 오른쪽 서브트리방문> 루트노드 방문 class TreeNode: def __init__(self, key): self.left = None self.right = None self.val = key def inorder_traversal(roo..

덱, Deque(Double- ended- Queue)는 큐의 front 와 rear에서 모두 삽입,삭제가 가능한 큐로서, 스택과 큐의 특성을 모두 가지고 있다. 이는 덱을 스택으로도, 큐로도 사용할 수 있음을 의미한다. - 스택으로 사용시: top > rear일때, push() >> deque의 insertRear()와 비슷, Pop() > deleteRear()와 비슷함 - 큐로 사용시 : enqueue > insertRear()와 비슷, Dequeue() > deleteFront()와 비슷 덱도 스택과 큐에서 구현한 방식처럼, 1) 배열로 구현하는 방법과, 2) 연결 리스트를 이용한 방법이 있다. 배열로 구현한 경우, 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서변화가 많..

연결리스트를 이용하여 큐를 구현하는 예제이다. Node class와 Queue class를 이용하여 queue를 구현하였다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def is_empty(self): return self.front is None def enqueue(self, data): new_node = Node(data) if self.is_empty(): self.front = self.rear = new_node else: self.rear.next = new_node self.rear..

[큐 구현: 배열 이용방법] 1. 개요: 큐(Queue)는 데이터를 선입선출(FIFO, First-In-First-Out)의 원칙에 따라 처리하는 자료구조로, 배열을 이용해 구현할 수 있다. 이 보고서에서는 배열을 활용하여 큐를 구현하는 방법과 그 한계점에 대해 다룹니다. 2. 구현 알고리즘: · - Enqueue (삽입): · 큐의 끝에 새로운 원소를 추가하는 작업이다. · 배열의 끝에 원소를 추가하고, 큐의 끝을 업데이트한다. · - Dequeue (삭제): · 큐의 맨 앞에서 원소를 제거하는 작업이다. 배열의 맨 앞에서 원소를 제거하고, 큐의 시작 지점을 업데이트한다. · - Peek (참조): · 큐의 맨 앞에 있는 원소를 조회하는 작업이다. 배열의 시작 부분에 위치한 원소를 반환한다. 3. 예시..

스택을 구현하기 위해서는 이전 포스팅에서 다루었던, 배열을 이용하는 방법과 연결리스트를 이용하는 방법이 있다. 연결리스트는 단순 연결 리스트를 이용하여 진행한다. 단순 연결리스트에서 변수의 top은 가장 최근에 삽입된 요소를 가리키는 변수가 된다. (head와 유사) 초기화시에는 top= NULL로 설정하는데, 이는 공백 스택을 의미한다. 스택에서 가장 먼저 삽입된 요소는 마지막 노드가 되므로(스택의 특징) link field를 NULL로 설정하여야 한다. 그리고 가장 최근에 삽입된 요소는 첫번째 노드가 된다. 이는 단순 연결리스트에서 첫 번째 노드로 삽입하는 연산과 동일하다. [스택 구현: 연결리스트 이용 방법 by 재민] #스택 구현: 연결 리스트 이용 by 재민 class Node: def __in..

스택을 구현하기 위해 배열을 사용할 경우, 일차원 배열 stack[MAX_STACK_SIZE] 를 사용한다. 스택의 변수 top은 가장 최근에 삽입된 요소를 가리키는 변수로, 초기값을 -1로 세팅한다(공백 스택을 의미) 스택에서 가장 먼저 삽입된 요소는 stack[0]에, 가장 최근에 삽입된 요소는 stack[top]에 저장된다 (스택의 개념) [c코드로 스택 구현] #include #define MAX_STACK_SIZE 100 typedef struct { int stack[MAX_STACK_SIZE]; int top; } Stack; // 스택 초기화 void initializeStack(Stack *s) { s->top = -1; // 초기값으로 -1을 설정하여 공백 스택을 나타냄 } // 스택이..

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다. 2) 삭제할 노드의 오른쪽 주소를 삭제할 노드의 왼쪽 노드의 rlink에 저장한다. 3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 4) 삭제할 노드를 삭제한다. [코드로 구현하기] #include #include // 이중 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* llink; // 왼쪽 노드를 가리키는 포인터..

Natural Join은 두 테이블 간에 동일한 이름을 가진 열들을 기반으로 자동으로 결합하는 데이터베이스의 쿼리의 일종이다. Natural Join은 Join시 위험성이 존재하는데, 그 위험성들은 다음과 같다. 1) 의도하지 않은 결합: Natural Join은 열 이름이 동일한 열들을 기반으로 결합하기 때문에, 열 이름이 동일하지만 실제로는 서로 다른 데이터를 나타내는 경우에는 오류가 발생할 수 있다. 2) 향후 스키마 변경에 대한 취약성 : 새로운 열이 추가되거나 삭제될 시 혼란이 생김 3) 쿼리 이식성의 감소 : 다른 데이터베이스로 쿼리를 이식하는 데 무리(특정 열 이름에 의존하기 때문) 4) 성능저하: 다른 조인들보다 많은 계산을 필요로 하기 때문에 성능 저하가 될 수 있음

Doubly Linked List는 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트이다. linked list에서와 마찬가지로 중간노드, 첫번째 노드, 마지막 노드 삽입을 나누어서 보도록 하겠다. https://imsunbow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List-%EC%82%BD%EC%9E%85%EC%A4%91%EA%B0%84-%EB%85%B8%EB%93%9C-%EC%B2%AB%EB%B2%88%EC%A7%B8-%EB%85%B8%EB%93%9C%EB%A7%88%EC%A7%80%EB%A7%89-%EB%85%B8%EB%93%9C%EB%A1%9C-%EC%82%BD%EC%9E%85 [같이 보면 좋은 자료: linked lis..

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..