인프런 워밍업 클럽 4기 CS 전공지식 3주차 미션

컴퓨터 구조다운로드 링크문제 1. STOREB(1001) 명령어를 만들어보세요.,(OPcode는 1001이고 operand가 가리키는 RAM주소에 현재 레지스터B의 데이터 저장하는 기능) 문제 2. A와 B를 비교해서 A와 B가 같으면 0, A가 더 크면 1, B가 더 크면 2를 출력 레지스터에 출력하는 어셈블리어를 작성해보세요. 자료구조와 알고리즘문제여러분은 문서 압축 프로그램을 개발해야 합니다. '허프만 코딩'이라는 압축 알고리즘을 사용하여, 아래와 같은 결과가 나오도록 구현해보세요. (필요하다면 사용된 자료구조를 수정해도 좋습니다.) ✅ 허프만 코딩이란?문자의 빈도수에 따라 가변 길이의 이진 코드를 부여하여전체 데이터를 무손실 압축하는 알고리즘✅ 핵심 개념자주 나오는 문자 → 짧은 코드,드물게 나오는 문자 → 긴 코드트리 기반 구조로, 모든 문자는 prefix-free한 이진 코드로 인코딩됨 ✅ 작동 원리 (요약)각 문자의 등장 횟수(빈도)를 센다가장 빈도 낮은 두 문자부터 묶어서 이진 트리로 만든다루트까지 도달하는 경로를 따라:왼쪽 자식 = 0오른쪽 자식 = 1모든 문자는 이진 문자열(코드)을 갖게 된다huffmanCompress.cpp#include #include #include #include #include #include using namespace std; class HuffmanNode { public: char ch; int freq; HuffmanNode* left; HuffmanNode* right; bool isLeaf; HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr), isLeaf(true) {} HuffmanNode(HuffmanNode* l, HuffmanNode* r) : ch(0), freq(l->freq + r->freq), left(l), right(r), isLeaf(false) {} }; struct Compare { bool operator()(HuffmanNode* a, HuffmanNode* b) { if (a->freq == b->freq) { // 둘 다 리프 노드일 경우 문자 기준 비교 if (a->isLeaf && b->isLeaf) return a->ch > b->ch; // 리프 노드가 아닌 경우엔 리프 노드를 우선 return b->isLeaf; } return a->freq > b->freq; } }; void buildCode(HuffmanNode* node, const string& code, unordered_map& codeMap) { if (!node) return; if (!node->left && !node->right) { codeMap[node->ch] = code; } buildCode(node->left, code + "0", codeMap); buildCode(node->right, code + "1", codeMap); } vector> huffmanCompress(const string& str) { unordered_map freqMap; for (char ch : str) freqMap[ch]++; priority_queue, Compare> pq; for (auto& [ch, freq] : freqMap) { pq.push(new HuffmanNode(ch, freq)); } while (pq.size() > 1) { HuffmanNode* left = pq.top(); pq.pop(); HuffmanNode* right = pq.top(); pq.pop(); pq.push(new HuffmanNode(left, right)); } HuffmanNode* root = pq.top(); unordered_map codeMap; buildCode(root, "", codeMap); vector> result; for (auto& [ch, code] : codeMap) { result.emplace_back(ch, code); } sort(result.begin(), result.end(), [](const pair& a, const pair& b) { return a.first 출력 결과int main() { string str = "Lorem ipsum dolor sit amet consectetur adipiscing elit. Consectetur adipiscing elit quisque faucibus ex sapien vitae. Ex sapien vitae pellentesque sem placerat in id. Placerat in id cursus mi pretium tellus duis. Pretium tellus duis convallis tempus leo eu aenean."; vector> result = huffmanCompress(str); for (const auto& [ch, code] : result) { cout

인프런 워밍업 클럽 4기 CS 전공지식 3주차 발자국

컴퓨터 구조✅ 프로그램 실행 구조PC (Program Counter): 다음 명령어 주소를 저장하는 레지스터SP (Stack Pointer): 함수 호출, 지역 변수 관리를 위한 스택 위치 추적Fetch-Execute 사이클:명령어 인출 (PC → 메모리)명령어 실행 (ALU, 메모리 접근, 분기 등)✅ 명령어 종류 요약NOP: 아무 작업 안 함LOADA: 메모리 → A 레지스터LOADI: 상수 → A 레지스터STOREA: A 레지스터 → 메모리ADD: 덧셈SUB: 뺄셈OUT: A 레지스터 출력HLT: 프로그램 종료 ✅ 분기 명령어JMP addr: 무조건 점프JMPC: Carry 플래그가 1일 때 점프JMPZ: Zero 플래그가 1일 때 점프 ✅ 제어 장치/출력 구성출력 레지스터: 출력 대기 중인 데이터를 저장제어 장치: 명령어 해석 → ALU, 레지스터, 메모리 제어 신호 생성 ✅ 기계어 vs 어셈블리어기계어: 2진수 코드 (01101001)어셈블리어: 사람 친화적 언어 (LOAD, ADD)어셈블러: 어셈블리어 → 기계어로 번역자료구조와 알고리즘 ✅ Trie란?문자열 검색/자동완성에 특화된 트리 형태의 자료구조 ✅ 핵심 개념각 노드는 문자 하나를 표현루트부터 자식 노드들을 따라가며 문자열을 구성한 노드에서 다음 노드로 이동할 때 문자 하나씩 비교 ✅ 특징 요약자료구조 : 형태다진 트리 (보통 26개 자식 노드: 알파벳 a~z)저장 단위 : 문자열 전체가 아닌, 문자 하나씩 저장검색 속도 : O(문자열 길이) (문자 수만큼 비교)공간 사용량 : 중복 접두사를 공유하므로 공간 효율적사용 용도 : 자동완성, 사전 검색, 접두어 필터링 등 ✅ 장점검색과 삽입이 O(L) (L = 문자열 길이)공통 접두어 공유로 공간 절약자동완성, 필터링, 문자열 집합 처리에 탁월 ✅ 단점구현이 복잡할 수 있음알파벳 수가 많으면 공간 낭비 가능 (자식 노드 많음) Trie#pragma once #include #include using namespace std; class TrieNode { public: unordered_map children; bool isEndOfWord = false; }; class Trie { public: Trie(); ~Trie(); void Insert(const string& word); bool Search(const string& word); vector Autocomplete(const string& prefix); private: void Dfs(TrieNode* node, const string& path, vector& results); TrieNode* _root; }; #include "Trie.h" #include #include #include #include Trie::Trie() { _root = new TrieNode(); } Trie::~Trie() { delete _root; } void Trie::Insert(const string& word) { TrieNode* node = _root; // 루트에서 시작 for (char c : word) { if (!node->children.count(c)) node->children[c] = new TrieNode(); // 해당 문자 노드가 없으면 생성 node = node->children[c]; // 다음 글자로 이동 } node->isEndOfWord = true; // 마지막 글자에서 단어 종료 표시 } bool Trie::Search(const string& word) { TrieNode* node = _root; // 루트에서 시작 for (char c : word) { if (!node->children.count(c)) return false; node = node->children[c]; // 다음 글자로 이동 } return node->isEndOfWord; } // 사용자가 입력한 접두어로 시작하는 모든 단어를 찾아 반환하는 함수 vector Trie::Autocomplete(const string& prefix) { vector results; TrieNode* node = _root; for (char c : prefix) { // 중간에 접두어에 해당하는 경로가 없으면, 자동완성 결과도 없음 (빈 벡터 반환) if (!node->children.count(c)) return results; node = node->children[c]; } // 접두어의 마지막 노드까지 도달한 후, 거기서부터 모든 하위 단어를 Dfs로 찾음 Dfs(node, prefix, results); return results; } // 현재 노드부터 시작해서 하위 모든 단어를 탐색하고, 완성된 단어를 results에 저장 // 이로써 "ap" -> "apple", "april", "app" 등 다양한 자동완성 결과 생성 void Trie::Dfs(TrieNode* node, const string& path, vector& results) { // 지금까지의 경로가 하나의 완성된 단어라면 results에 추가 if (node->isEndOfWord) { results.push_back(path); } for (auto& [c, nextNode] : node->children) { // 각각의 자식 문자 붙여서 자식 호출 Dfs(nextNode, path + c, results); } } 출력 결과int main() { Trie trie; trie.Insert("apple"); trie.Insert("app"); trie.Insert("april"); trie.Insert("bat"); trie.Insert("ball"); string prefix = "ap"; vector suggestions = trie.Autocomplete(prefix); cout ✅ 그래프(Graph)란?- 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조- 정점끼리의 연결 관계를 표현- 방향성, 가중치, 연결 여부 등에 따라 다양하게 분류됨 ✅ DFS (깊이 우선 탐색)- 한 방향으로 계속 깊이 들어가며 탐색- 스택(Stack) 또는 재귀(Recursion) 사용- 방문 → 깊이 탐색 → 백트래킹- 미로 찾기, 백트래킹 등에 적합- 시간복잡도: O(V + E) ✅ BFS (너비 우선 탐색)- 현재 노드의 인접 노드를 모두 방문 후 다음 단계로 진행- 큐(Queue) 사용- 최단 거리 문제에 유리 (간선 가중치 동일할 때)- 시간복잡도: O(V + E)✅ DFS vs BFS 요약 비교항목 : DFS | BFS--------:----------------------------|-------------------------------방식 : 깊이 우선 (한 방향으로 쭉) | 너비 우선 (레벨 순으로)자료구조 : 스택 / 재귀 | 큐특징 : 백트래킹, 경로 탐색 적합 | 최단 거리 탐색에 적합시간복잡도: O(V + E) | O(V + E) DFS#include #include #include #include #include using namespace std; class DFS { struct Vertex { string data; }; public: void CreateGraph() { vertices.resize(8); vertices = { {"Ben"}, {"Ivy"}, {"Joy"}, {"Jake"}, {"Anna"}, {"David"}, {"Elin"}, {"Owen"} }; // 인접 리스트 adjacent["Ben"] = { "Ivy", "Jake", "Anna", "David" }; adjacent["Ivy"] = { "Ben", "Joy" }; adjacent["Joy"] = { "Ivy", "Jake" }; adjacent["Jake"] = { "Ben", "Joy" }; adjacent["Anna"] = { "Ben" }; adjacent["David"] = { "Ben", "Elin" }; adjacent["Elin"] = { "David", "Owen" }; adjacent["Owen"] = { "Elin" }; } void Dfs(const string& here) { // 방문 visited.insert(here); cout vertices; unordered_map> adjacent; unordered_set visited; }; 출력 결과int main() { DFS d; d.CreateGraph(); d.DfsAll(); return 0; }BFS#include #include #include #include #include using namespace std; class BFS { struct Vertex { string data; }; public: void CreateGraph() { vertices.resize(8); vertices = { {"Ben"}, {"Ivy"}, {"Joy"}, {"Jake"}, {"Anna"}, {"David"}, {"Elin"}, {"Owen"} }; // 인접 리스트 adjacent["Ben"] = { "Ivy", "Jake", "Anna", "David" }; adjacent["Ivy"] = { "Ben", "Joy" }; adjacent["Joy"] = { "Ivy", "Jake" }; adjacent["Jake"] = { "Ben", "Joy" }; adjacent["Anna"] = { "Ben" }; adjacent["David"] = { "Ben", "Elin" }; adjacent["Elin"] = { "David", "Owen" }; adjacent["Owen"] = { "Elin" }; } void Bfs(string here) { // 누구에 의해 발견 되었는지? unordered_map parent; // 시작점에서 얼만큼 떨어져 있는지? unordered_map distance; queue q; q.push(here); discovered.insert(here); parent[here] = here; distance[here] = 0; while (q.empty() == false) { here = q.front(); q.pop(); cout vertices; unordered_map> adjacent; unordered_set discovered; }; 출력 결과int main() { BFS b; b.CreateGraph(); b.BfsAll(); return 0; }✅ 다익스트라 알고리즘이란?하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(단, 모든 간선 가중치는 0 이상이어야 함) ✅ 핵심 개념방문하지 않은 정점 중에서 가장 가까운 정점을 반복적으로 선택선택된 정점의 인접 정점 거리들을 갱신우선순위 큐(Min Heap)를 사용하면 성능을 높일 수 있음거리 배열과 방문 배열을 함께 사용 ✅ 특징 요약알고리즘 유형 : 그리디 알고리즘 (Greedy)그래프 조건 : 방향/무방향 그래프 + 양의 가중치시간 복잡도 : O(E log V) (우선순위 큐 + 인접 리스트 사용 시)자료구조 : 거리 배열, 우선순위 큐, 방문 여부 배열적용 분야 : GPS, 게임 경로 탐색, 네트워크 최단 경로 등 ✅ 장점모든 정점까지의 최단 거리를 빠르게 구할 수 있음우선순위 큐와 함께 사용하면 성능이 우수실제 현실 문제에 널리 사용됨 (지도, 경로 탐색 등) ✅ 단점음수 가중치가 있는 그래프에서는 동작하지 않음경로가 아닌 거리 정보만 기본 출력됨 (경로 추적은 따로 저장해야 함)단순 구현(O(V²))은 느릴 수 있음 (우선순위 큐 사용 필요)Dijkstra#include #include #include #include #include using namespace std; class DIJKSTRA { struct Vertex { string name; int cost = INT32_MAX; }; public: vector vertices; vector> adjacent; void CreateGraph() { vertices = { {"서울"}, {"원주"}, {"강릉"}, {"대전"}, {"전주"}, {"대구"} }; adjacent = vector>(6, vector(6, -1)); adjacent[0][1] = 87; adjacent[0][2] = 165; adjacent[0][3] = 140; adjacent[0][4] = 187; adjacent[1][0] = 87; adjacent[1][2] = 95; adjacent[1][3] = 118; adjacent[1][5] = 178; adjacent[2][0] = 165; adjacent[2][1] = 95; adjacent[2][5] = 212; adjacent[3][0] = 140; adjacent[3][1] = 118; adjacent[3][4] = 56; adjacent[3][5] = 122; adjacent[4][0] = 187; adjacent[4][3] = 56; adjacent[4][5] = 130; adjacent[5][1] = 178; adjacent[5][2] = 212; adjacent[5][3] = 122; adjacent[5][4] = 130; } void Dijkstra(int here) { vector parent(6, -1); priority_queue, vector>, greater> pq; // cost, vertex vertices[here].cost = 0; parent[here] = here; pq.push({ 0, here }); while (!pq.empty()) { auto [cost, here] = pq.top(); pq.pop(); if (vertices[here].cost " path; int current = i; while (current != here) { path.push(vertices[current].name); current = parent[current]; } path.push(vertices[here].name); while (!path.empty()) { cout "; } cout 출력 결과int main() { DIJKSTRA D; D.CreateGraph(); D.Dijkstra(0); // 서울에서 출발 return 0; }✅ Prim 알고리즘이란?모든 정점을 최소 비용으로 연결하는**최소 신장 트리(MST, Minimum Spanning Tree)**를 만드는 알고리즘 ✅ 핵심 개념하나의 정점에서 시작해서MST에 포함되지 않은 정점 중 가장 싼 간선을 반복적으로 선택선택된 간선을 통해 트리를 확장우선순위 큐(Min Heap)를 이용해 효율적으로 구현 가능 ✅ 특징 요약알고리즘 유형 : 탐욕 알고리즘 (Greedy)그래프 조건 : 무방향 그래프, 연결 그래프시간 복잡도 : O(E log V) (우선순위 큐 + 인접 리스트 사용 시)자료구조 : 우선순위 큐, MST 포함 여부 배열, 비용 배열적용 분야 : 네트워크 구축 비용 최소화, 전기 회로 설계, 도로 연결 최적화 등 ✅ 장점모든 정점을 사이클 없이 연결 가능가중치가 양수인 무방향 그래프에서 항상 동작시작점 하나만 정해주면 자동으로 전체 MST 구성 ✅ 단점간선 수가 적은 그래프에선 Kruskal 알고리즘이 더 효율적일 수 있음가중치가 음수여도 가능하지만 MST 정의 상 무의미할 수도 있음구현 시 MST 포함 여부나 간선 비용 갱신 처리가 조금 번거로울 수 있음Prim#pragma once #include #include #include #include using namespace std; class PRIM { public: struct Vertex { string name; bool inMST = false; }; vector vertices; vector> adjacent; void CreateGraph() { vertices = { {"서울"}, {"원주"}, {"강릉"}, {"대전"}, {"전주"}, {"대구"} }; adjacent = vector>(6, vector(6, -1)); adjacent[0][1] = 87; adjacent[0][2] = 165; adjacent[0][3] = 140; adjacent[0][4] = 187; adjacent[1][0] = 87; adjacent[1][2] = 95; adjacent[1][3] = 118; adjacent[1][5] = 178; adjacent[2][0] = 165; adjacent[2][1] = 95; adjacent[2][5] = 212; adjacent[3][0] = 140; adjacent[3][1] = 118; adjacent[3][4] = 56; adjacent[3][5] = 122; adjacent[4][0] = 187; adjacent[4][3] = 56; adjacent[4][5] = 130; adjacent[5][1] = 178; adjacent[5][2] = 212; adjacent[5][3] = 122; adjacent[5][4] = 130; } void Prim(int start) { int totalCost = 0; priority_queue, vector>, greater> pq; // (cost, to) pq.push({ 0, start }); while (!pq.empty()) { auto [cost, now] = pq.top(); pq.pop(); if (vertices[now].inMST) continue; vertices[now].inMST = true; totalCost += cost; cout 출력 결과int main() { PRIM P; P.CreateGraph(); P.Prim(0); // 서울에서 시작 return 0; }✅ Ford-Fulkerson 알고리즘이란?흐를 수 있는 경로(증가 경로)를 찾아 유량을 반복적으로 보내며,최대 유량(Maximum Flow)을 계산하는 알고리즘 ✅ 핵심 개념유량이 흐를 수 있는 경로(잔여 용량 > 0)를 DFS 또는 BFS로 탐색해당 경로에 가능한 만큼 유량을 보냄이런 과정을 경로가 더 이상 없을 때까지 반복역방향 유량도 고려 (되돌릴 수 있도록) ✅ 특징 요약알고리즘 유형 : 그리디 + 네트워크 플로우그래프 조건 : 방향 그래프 + 간선에 용량이 존재해야 함시간 복잡도 : O(E × max_flow) (단순 DFS 사용 시)자료구조 : 잔여 용량 배열, 유량 배열, 방문 배열적용 분야 : 네트워크 최대 전송량, 작업 배정, 이분 매칭 등 ✅ 장점아이디어가 간단하고 직관적최대 유량 보장 (정확한 답)다양한 문제(이분 매칭 등)로 응용 가능성 매우 높음 ✅ 단점무한 루프 발생 가능성 있음 (소수점 유량일 때)시간 복잡도가 높음 (max_flow에 비례)안정적 성능을 원할 경우 BFS 기반 Edmonds-Karp 알고리즘 사용 권장Ford Fulkerson#include #include #include #include using namespace std; const int V = 6; // 정점 수 (0 ~ V-1) class FORDFULKERSON { public: int capacity[V][V]; // 간선 용량 int flow[V][V]; // 현재 유량 bool visited[V]; FORDFULKERSON() { for (int i = 0; i 0) { int d = dfs(v, t, min(f, residual)); if (d > 0) { flow[u][v] += d; flow[v][u] -= d; // 역방향 처리 return d; } } } return 0; } int fordFulkerson(int s, int t) { int maxFlow = 0; int f = 0; while (true) { memset(visited, false, sizeof(visited)); f = dfs(s, t, INT_MAX); if (f == 0) break; maxFlow += f; } return maxFlow; } }; 출력 결과int main() { FORDFULKERSON ff; // 예제 간선 설정 ff.capacity[0][1] = 10; ff.capacity[0][2] = 10; ff.capacity[1][2] = 2; ff.capacity[1][3] = 4; ff.capacity[1][4] = 8; ff.capacity[2][4] = 9; ff.capacity[3][5] = 10; ff.capacity[4][3] = 6; ff.capacity[4][5] = 10; int source = 0, sink = 5; int result = ff.fordFulkerson(source, sink); cout

인프런 워밍업 클럽 4기 CS 전공지식 2주차 발자국

[컴퓨터 구조]멀티플렉서 (Multiplexer, MUX)여러 개의 입력 중 하나를 선택해 출력하는 회로2^n개의 입력 → 1개의 출력선택 신호(Select Line)로 출력 결정예: 4:1 MUX는 입력 4개, 출력 1개, 선택선 2개주요 역할: 다수의 데이터 중 필요한 것만 선택디멀티플렉서 (Demultiplexer, DEMUX)하나의 입력을 선택된 출력 하나로 전달하는 회로1개의 입력 → 2^n개의 출력선택 신호로 어느 출력으로 보낼지 결정주요 역할: 하나의 데이터를 여러 대상 중 하나로 분배디코더 (Decoder)n개의 입력을 받아 2^n개의 출력 중 하나를 활성화특정 입력 조합 → 해당 출력 하나만 1(활성화), 나머지는 0예: 3→8 디코더는 입력 3개 → 출력 8개주요 역할: 특정 주소 또는 명령어를 구분해 선택컨트롤 버퍼 (Control Buffer)제어 신호(Control Signal) 또는 제어 정보(Control Data)를 일시 저장하거나 전달하는 버퍼 회로CPU 내부, 메모리 컨트롤러, I/O 디바이스 제어 등에서 사용동기화, 속도 차 완충, 임시 저장, 전달 안정화 등의 역할 수행경우에 따라 컨트롤 레지스터(Control Register) 와 혼용되기도 함주요 역할:제어 신호의 전달 시 타이밍 조절동기화 문제 해결제어 흐름의 안정성 유지반가산기 (Half Adder)두 개의 1비트 이진수(A, B)를 더하는 회로출력: 합(Sum), 자리올림(Carry)논리식:Sum = A ⊕ BCarry = A ∧ B특징: 이전 자리에서의 올림값(Carry-in)을 처리할 수 없음전가산기 (Full Adder)세 개의 1비트 이진수(A, B, Carry-in)를 더하는 회로출력: 합(Sum), 자리올림(Carry-out)논리식:Sum = A ⊕ B ⊕ CinCout = (A ∧ B) ∨ (B ∧ Cin) ∨ (A ∧ Cin)특징: 자리올림 입력을 처리할 수 있어 다비트 덧셈 가능조합 논리 회로 (Combinational Logic Circuit)현재 입력에만 의존하여 출력이 결정되는 회로과거 상태(기억)를 고려하지 않음 → 메모리 없음출력 = 입력의 조합 결과특징:입력이 바뀌면 출력이 즉시 바뀜클럭 신호 불필요대표 예시:가산기(Adder), 디코더(Decoder), 인코더(Encoder), 멀티플렉서(MUX), 비교기 등순차 논리 회로 (Sequential Logic Circuit)입력 + 현재 상태(과거 출력)에 따라 출력이 결정기억 기능(메모리) 포함클럭(Clock) 신호 사용 → 타이밍 기반 동작특징:출력이 시간의 흐름에 따라 달라짐상태를 저장하고 변화함 (플립플롭, 레지스터 등 포함)대표 예시:플립플롭(Flip-Flop), 레지스터(Register), 카운터(Counter), FSM(상태 기계), 메모리 등SR 래치 (Set-Reset Latch)S(Set), R(Reset) 두 입력으로 출력 Q 제어출력은 이전 상태를 기억함 (순차 회로의 기본 형태)문제점: S=1, R=1이면 출력이 불안정해짐D 래치 (Data or Delay Latch)SR 래치의 문제(S=1, R=1)를 해결하기 위해 설계입력: D(Data), Enable (또는 Clock)Enable이 1일 때만 D값이 Q로 전달됨특징: 항상 안정적인 동작, 메모리 소자에 많이 사용JK 래치SR 래치의 금지 상태를 해결한 구조입력: J, K, ClockJ: Set 역할, K: Reset 역할J=K=1이면 출력 반전특징: 플립플롭 구현에 주로 사용됨클럭 (Clock)디지털 회로에서 동기 신호를 제공하는 주기적인 펄스회로 동작의 타이밍 기준 역할클럭 상승엣지(↑), 하강엣지(↓)에서 동작하도록 회로 설계됨플립플롭 (Flip-Flop)1비트의 정보를 저장할 수 있는 순차 논리 회로클럭에 의해 상태가 변하거나 유지됨D, JK, T 등 여러 종류가 있음레지스터 (Register)여러 개의 플립플롭을 묶은 구조 (보통 8, 16, 32비트 등)CPU 내부에서 데이터를 임시 저장하는 데 사용동기식으로 동작하며 고속 처리 가능RAM (Random Access Memory)데이터를 읽고 쓰기 가능한 임의 접근 메모리전원이 꺼지면 데이터가 사라짐(휘발성)주소 지정으로 원하는 위치의 데이터를 직접 접근[자료구조와 알고리즘] 강의 수강나의 주력 언어는 c++이라서 강의를 토대로 c++버젼으로 바꿔보았다Red-Black Tree자기 균형 이진 탐색 트리(BST)의 일종삽입/삭제 시 균형 유지를 위한 색상(빨강/검정) 속성 사용 Red-Black Tree의 주요 특징노드는 빨강(Red) 또는 검정(Black)루트 노드는 항상 검정모든 리프(NIL)는 검정 (NULL 노드 포함)빨간 노드의 자식은 반드시 검정 (연속된 빨강 없음)임의의 노드에서 리프까지 가는 모든 경로에는 동일한 수의 검정 노드 존재 Red-Black Tree의 장점AVL Tree보다 회전 횟수가 적음삽입/삭제 성능이 더 안정적임Red-Black Tree의 단점AVL보다 탐색 시간이 조금 느림 (균형이 느슨함) 시간 복잡도탐색 / 삽입 / 삭제: O(log n)최악의 경우에도 높이가 log₂(n) 이내로 유지됨Red_BlackTree.h#pragma once #include "BinarySearchTree.h" // Red-Blakc Tree // 1) 모든 노드는 Red or Black // 2) Root는 Black // 3) Leaf(NIL)는 Black // 4) Red 노드의 자식은 Black (연속해서 Red-Red X) // 5) 각 노드로부터 ~ 리프까지 가는 경로들은 모두 같은 수의 Black class Red_BlackTree { public: Red_BlackTree(); ~Red_BlackTree(); void Print(); void Print(Node* node, int x, int y); Node* Search(Node* node, int key); Node* Min(Node* node); Node* Max(Node* node); Node* Next(Node* node); void Insert(int key); void InsertFixup(Node* node); void Delete(int key); void Delete(Node* node); void DeleteFixup(Node* node); void Replace(Node* u, Node* v); // Red-Black Tree void RotateLeft(Node* node); void RotateRight(Node* node); private: Node* _root = nullptr; Node* _nil = nullptr; };Red_BlackTree.cpp#include "Red_BlackTree.h" #include #include using namespace std; enum class ConsoleColor { BlACK = 0, RED = FOREGROUND_RED, GREEN = FOREGROUND_GREEN, BLUE = FOREGROUND_BLUE, YELLOW = RED | GREEN, WHITE = RED | GREEN | BLUE, }; void SetCursorColor(ConsoleColor color) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); ::SetConsoleTextAttribute(output, static_cast(color)); } void SetCursorPosition(int x, int y) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); COORD pos = { static_cast(x), static_cast(y) }; ::SetConsoleCursorPosition(output, pos); } void ShowConsoleCursor(bool flag) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_CURSOR_INFO cursorInfo; ::GetConsoleCursorInfo(output, &cursorInfo); cursorInfo.bVisible = flag; ::SetConsoleCursorInfo(output, &cursorInfo); } Red_BlackTree::Red_BlackTree() { _nil = new Node(); // Black _root = _nil; _root->parent = _nil; } Red_BlackTree::~Red_BlackTree() { delete _nil; } void Red_BlackTree::Print() { ::system("cls"); ShowConsoleCursor(false); Print(_root, 10, 0); } void Red_BlackTree::Print(Node* node, int x, int y) { if (node == nullptr) return; SetCursorPosition(x, y); if (node->color == Color::Black) SetCursorColor(ConsoleColor::BLUE); else SetCursorColor(ConsoleColor::RED); cout key; Print(node->left, x - (5 / (y + 1)), y + 1); Print(node->right, x + (5 / (y + 1)), y + 1); SetCursorColor(ConsoleColor::WHITE); } Node* Red_BlackTree::Search(Node* node, int key) { if (node == _nil || key == node->key) return node; if (key key) return Search(node->left, key); else return Search(node->right, key); } Node* Red_BlackTree::Min(Node* node) { while (node->left != _nil) node = node->left; return node; } Node* Red_BlackTree::Max(Node* node) { while (node->right != _nil) node = node->right; return node; } Node* Red_BlackTree::Next(Node* node) { if (node->right != _nil) return Min(node->right); Node* parent = node->parent; while (parent != _nil && node == parent->right) { node = parent; parent = parent->parent; } return parent; } void Red_BlackTree::Insert(int key) { Node* newNode = new Node(); newNode->key = key; Node* node = _root; Node* parent = _nil; while (node != _nil) { parent = node; if (key key) node = node->left; else node = node->right; } newNode->parent = parent; if (parent == _nil) _root = newNode; else if (key key) parent->left = newNode; else parent->right = newNode; // 검사 newNode->left = _nil; newNode->right = _nil; newNode->color = Color::Red; InsertFixup(newNode); } void Red_BlackTree::InsertFixup(Node* node) { // 1) p = red, uncle = red // -> p = black, uncle = black, pp = red로 바꿈 // 2) p = red, uncle = black (triangle) // -> 회전을 통해 case 3으로 바꿈 // 3) p = red, uncle = black (list) // -> 색상 변경 + 회전 while (node->parent->color == Color::Red) { if (node->parent == node->parent->parent->left) { Node* uncle = node->parent->parent->right; if (uncle->color == Color::Red) // p = red, uncle = red { node->parent->color = Color::Black; // p uncle->color = Color::Black; // u node->parent->parent->color = Color::Red; node = node->parent->parent; } else // p = red, uncle = black { if (node == node->parent->right) { // Triangle 타입 // [pp(B)] // [p(R)] [u(B)] // [n(R)] // [pp(B)] // [p(R)] [u(B)] // [n(R)] node = node->parent; RotateLeft(node); } // List 타입 // [pp(R)] // [p(B)] [u(B)] // [n(R)] // [p(B)] // [n(R)] [pp(R)] // [u(B)] node->parent->color = Color::Black; node->parent->parent->color = Color::Red; RotateRight(node->parent->parent); } } else { Node* uncle = node->parent->parent->left; if (uncle->color == Color::Red) // p = red, uncle = red { node->parent->color = Color::Black; // p uncle->color = Color::Black; // u node->parent->parent->color = Color::Red; node = node->parent->parent; } else // p = red, uncle = black { if (node == node->parent->left) { node = node->parent; RotateRight(node); } // List 타입 // [p(B)] // [pp(R)] [n(R)] // [u(B)] node->parent->color = Color::Black; node->parent->parent->color = Color::Red; RotateLeft(node->parent->parent); } } } _root->color = Color::Black; } void Red_BlackTree::Delete(int key) { Node* deleteNode = Search(_root, key); Delete(deleteNode); } // 먼저 BST 삭제 실행 void Red_BlackTree::Delete(Node* node) { if (node == _nil) return; if (node->left == _nil) { Color color = node->color; Node* right = node->right; Replace(node, node->right); if (color == Color::Black) DeleteFixup(right); } else if (node->right == _nil) { Color color = node->color; Node* left = node->left; Replace(node, node->left); if (color == Color::Black) DeleteFixup(left); } else { // 다음 데이터 찾기 Node* next = Next(node); node->key = next->key; Delete(next); } } // 먼저 BST 삭제 실행... // - Case 1) 삭제할 노드가 Red-> 그냥 삭제! 끝! // - Case 2) root가 DB -> 그냥 추가 Black 삭제! 끝! // - Case 3) DB의 sibling 노드가 Red // -- s = black, p = red (s p 색상 교환) // -- DB 방향으로 rotate(p) // -- goto other case // - Case 4) DB의 sibling 노드가 Black && sibling의 양쪽 자식도 Black // -- 추가 Black을 parent에게 이전 // --- p가 Red이면 Black 됨. // --- p가 Black이면 DB 됨. // -- s = red // -- p를 대상으로 알고리즘 이어서 실행 (DB가 여전히 존재하면) // - Case 5) DB의 sibling 노드가 Black && sibling의 near child = red, far child = black // -- s near 색상 교환 // -- far 방향으로 rotate(s) // -- goto case 6 // - Case 6) DB의 sibling 노드가 Black && sibling의 far child = red // - p s 색상 교환 // - far = black // - rotate(p) (DB 방향으로) // - 추가 Black 제거 void Red_BlackTree::DeleteFixup(Node* node) { Node* x = node; // [Case 1][Case 2] while (x != _root && x->color == Color::Black) { // [p(B)] // [x(DB)] [s(R)] // [1] // [S(B)] // [p(R)] // [x[DB] [1] if (x == x->parent->left) { Node* s = x->parent->right; // [Case 3] if (s->color == Color::Red) { s->color = Color::Black; x->parent->color = Color::Red; RotateLeft(x->parent); s = x->parent->right; } // [Case 4] if (s->left->color == Color::Black && s->right->color == Color::Black) { s->color = Color::Red; x = x->parent; } else { // [Case 5] // [p] // [x(DB)] [s(B)] // [near(R)] [far(B)] // [p] // [x(DB)] [near(B)] // [s(R)] // [far(B)] if (s->right->color == Color::Black) { s->left->color == Color::Black; s->color == Color::Red; RotateRight(s); s = x->parent->right; // near } // [Case 6] // [p] // [x(DB)] [s(B)] // [far(R)] s->color = x->parent->color; x->parent->color = Color::Black; s->right->color = Color::Black; RotateLeft(x->parent); x = _root; // 루프를 빠져나오기 위해서 } } else { // [Case3] Node* s = x->parent->left; if (s->color == Color::Red) { s->color = Color::Black; x->parent->color = Color::Red; RotateRight(x->parent); s = x->parent->left; // [1] } // [Case4] if (s->right->color == Color::Black && s->left->color == Color::Black) { s->color = Color::Red; x = x->parent; } else { // [Case5] if (s->left->color == Color::Black) { s->right->color = Color::Black; s->color = Color::Red; RotateLeft(s); s = x->parent->left; } // [Case6] s->color = x->parent->color; x->parent->color = Color::Black; s->left->color = Color::Black; RotateRight(x->parent); x = _root; } } } x->color = Color::Black; } // u 서브트리를 v 서브트리로 교체 // 그리고 delete u void Red_BlackTree::Replace(Node* u, Node* v) { if (u->parent == _nil) _root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; v->parent = u->parent; delete u; } // [x] // [1] [y] // [2][3] // [y] // [x] [3] // [1][2] void Red_BlackTree::RotateLeft(Node* x) { Node* y = x->right; x->right = y->left; if (y->left != _nil) y->left->parent = x; y->parent = x->parent; if (x->parent == _nil) _root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } // [y] // [x] [3] // [1][2] // [x] // [1] [y] // [2][3] void Red_BlackTree::RotateRight(Node* y) { Node* x = y->left; y->left = x->right; if (x->right != _nil) x->right->parent = y; x->parent = y->parent; if (y->parent == _nil) _root = x; else if (y == y->parent->right) y->parent->right = x; else y->parent->left = x; x->right = y; y->parent = x; } 출력 결과int main() { Red_BlackTree rbt; rbt.Insert(30); rbt.Print(); //this_thread::sleep_for(1s); rbt.Insert(10); rbt.Print(); //this_thread::sleep_for(1s); rbt.Insert(20); rbt.Print(); //this_thread::sleep_for(1s); rbt.Insert(25); rbt.Print(); //this_thread::sleep_for(1s); rbt.Insert(40); rbt.Print(); //this_thread::sleep_for(1s); rbt.Insert(50); rbt.Print(); //this_thread::sleep_for(1s); rbt.Delete(20); rbt.Print(); this_thread::sleep_for(1s); rbt.Delete(10); rbt.Print(); this_thread::sleep_for(1s); }우선순위 큐와 힙우선순위 큐 (Priority Queue)일반 큐와 달리, 요소들이 삽입된 순서가 아니라 우선순위에 따라 처리됨가장 높은 우선순위의 요소가 먼저 나감삽입(Push)과 삭제(Pop)에 평균 O(log n) 시간복잡도내부 구현은 보통 힙(Heap) 자료구조로 되어 있음사용 예:CPU 스케줄러다익스트라 알고리즘이벤트 처리 시스템힙 (Heap)완전 이진 트리의 일종부모 노드가 자식 노드보다 항상 우선순위가 높거나 낮은 특성을 가짐두 종류가 있음:최대 힙 (Max Heap): 부모 ≥ 자식 → 가장 큰 값이 루트최소 힙 (Min Heap): 부모 ≤ 자식 → 가장 작은 값이 루트삽입: 마지막 위치에 추가 후 위로 올라가며 정렬 (Heapify-up)삭제: 루트 제거 후 마지막 노드를 루트로 옮기고 아래로 정렬 (Heapify-down)시간복잡도삽입: O(log n)삭제: O(log n)최대/최솟값 조회: O(1)힙 정렬완전 이진 트리 기반 정렬 알고리즘최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 이용제자리 정렬 가능 (in-place), 안정 정렬은 아님동작 과정배열을 힙 구조로 만든다 (heapify)루트(최대/최소값)를 배열 끝으로 보내고 힙 크기 감소나머지 트리를 다시 heapify이 과정을 배열 전체 크기만큼 반복시간 복잡도힙 구성: O(n)정렬(heapify 반복): O(n log n)총 시간 복잡도: O(n log n) (최악/최선/평균 동일)PriorityQueue.h#pragma once #include #include using namespace std; template, typename Predicate = less> class PriorityQueue { public: void push(const T& data) { // 우선 힙 구조부터 맞춰준다 _heap.push_back(data); // 도장깨기 시작 int now = static_cast(_heap.size()) - 1; // 루트 노드까지 while (now > 0) { // 부모 노드와 비교 int next = (now - 1) / 2; if (_predicate(_heap[now], _heap[next])) break; // 데이터 교체 ::swap(_heap[now], _heap[next]); now = next; } } void pop() { // 맨 뒤에값 루트로 교체 후 맨 뒤값 제거 _heap[0] = _heap.back(); _heap.pop_back(); int now = 0; while (true) { int left = 2 * now + 1; int right = 2 * now + 2; // 리프에 도달한 경우 if (left >= (int)_heap.size()) break; int next = now; // 왼쪽과 비교 if (_predicate(_heap[next], _heap[left])) next = left; // 둘 중 승자를 오른쪽과 비교 if (right 출력 결과int main() { PriorityQueue, greater> pq; //PriorityQueue> pq; pq.push(100); pq.push(300); pq.push(200); pq.push(500); pq.push(400); while (pq.empty() == false) { int value = pq.top(); pq.pop(); cout

인프런 워밍업 클럽 4기 CS 전공지식 2주차 미션

컴퓨터 구조 1. 다음 파일의 모든 연결을 터널로 대체해보세요. Mission_1 circ 링크2. 8비트 32입력 MUX를 제작해보세요. Mission_2 circ 링크3. 10비트 입력 두 개(A, B)를 계산하는 ALU 만들어보세요.Misson_3 circ 링크4. 32비트 RAM을 만들어보세요. 디코더와 MUX는 logisim 기본 내장된 걸 사용해도 좋습니다. Mission_4 circ 링크자료구조와 알고리즘문제여러분은 간단한 운영체제를 개발하고 있습니다. 운영체제의 CPU 스케줄링을 구현해야 하는 차례입니다. 여러 프로세스들이 골고루 실행되도록 하기 위해, 프로세스 실행 횟수(executionCount)가 작은 프로세스의 우선순위를 높게 설정하는 CPU 스케줄링 정책을 만들려고 합니다. 또한, 모든 프로세스가 비슷하게 실행될 때는 사용자의 반응성을 높이기 위해 I/O Bound 프로세스들의 처리를 우선적으로 하려고 합니다. I/O Bound 프로세스는 CPU를 사용하다가 자발적으로 CPU를 반납(cpuReturnCount)하는 것으로 판단할 수 있습니다. 따라서 다음 두 가지 조건으로 CPU 스케줄러를 구현해 보세요: 프로세스 실행 횟수가 가장 적은 프로세스가 우선순위가 높습니다.실행 횟수가 같을 경우, I/O Bound 프로세스가 우선순위가 높습니다. 풀이내가 커스텀해서 만든 PriorityQueue.h를 이용해서 풀어보았다CpuScheduler.cpp#include "PriorityQueue.h" #include #include using namespace std; struct Process { string name; int cpuReturnCount; // CPU를 자발적으로 반납한 횟수 int executionCount; // 실행 횟수 Process(string n, int cpuReturn, int exec) : name(n), cpuReturnCount(cpuReturn), executionCount(exec) {} bool operator other.executionCount; // 실행횟수가 작을수록 우선 return cpuReturnCount pq; }; 출력 결과

인프런 워밍업 클럽 4기 CS 전공지식 1주차 미션

컴퓨터 구조 1. 4입력 AND, OR, NAND, NOR, XOR 연산의 진리표를 작성해보세요.XOR은 1의 개수가 홀수일 때 1, 짝수일 때 02. 다음 불 방정식들을 여러 방법을 이용해 간략화 해보세요. A( (BB)’+ 0A) + (CC)' = (AB’) +CA( (B)' + 0) + (C)' = (AB') + CA(B') + C' = (AB') + CAB' + C' = AB' + C (B’B’) + (AD’ + (CA)’)D = B’ + (DC’) + (DA’)(B') + AD'D + (CA)'D = B' + (DC') + (DA')B' + A0 + (CA)'D = B' + (DC') + (DA')B' + (CA)'D = B' + (DC') + (DA')B' + (C' + A')D = B' + (DC') + (DA')B' + C'D + A'D = B' + DC' + DA' (A’B) + B(B1 + BC) = B(A’B) + B(B + BC) = B(A’B) + BB + BBC = B(A’B) + B + BC = B(A’B) + B = BA’B + B = BB = B B’(1C + BD) + DB = (B’C) + (DB)B’(C + BD) + DB = (B’C) + DBB’C + B’BD + DB = B’C + DBB’C + 0D + DB = B’C + DBB’C + DB = B’C + DB3. 다음 2진수를 10진수로 변환해보세요.110111 =→ 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 1×2⁰→ 32 + 16 + 0 + 4 + 2 + 1 = 5510000001 =→ 1×2⁷ + 0×2⁶ + … + 0×2¹ + 1×2⁰→ 128 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 12911111100000 =→ 1×2¹⁰ + 1×2⁹ + 1×2⁸ + 1×2⁷ + 1×2⁶ + 1×2⁵ + 0×2⁴ + … + 0×2⁰→ 1024 + 512 + 256 + 128 + 64 + 32 = 2016101010 =→ 1×2⁵ + 0×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰→ 32 + 0 + 8 + 0 + 2 + 0 = 42다음 10진수를 2진수로 변환해보세요.1. 10 = 101010 ÷ 2 = 5 → 나머지 05 ÷ 2 = 2 → 나머지 12 ÷ 2 = 1 → 나머지 01 ÷ 2 = 0 → 나머지 1 2. 27 = 1101127 ÷ 2 = 13 → 나머지 113 ÷ 2 = 6 → 나머지 16 ÷ 2 = 3 → 나머지 03 ÷ 2 = 1 → 나머지 11 ÷ 2 = 0 → 나머지 1 3. 86 = 101011086 ÷ 2 = 43 → 나머지 043 ÷ 2 = 21 → 나머지 121 ÷ 2 = 10 → 나머지 110 ÷ 2 = 5 → 나머지 05 ÷ 2 = 2 → 나머지 12 ÷ 2 = 1 → 나머지 01 ÷ 2 = 0 → 나머지 1 4. 516 = 1000000100516 ÷ 2 = 258 → 나머지 0258 ÷ 2 = 129 → 나머지 0129 ÷ 2 = 64 → 나머지 164 ÷ 2 = 32 → 나머지 032 ÷ 2 = 16 → 나머지 016 ÷ 2 = 8 → 나머지 08 ÷ 2 = 4 → 나머지 04 ÷ 2 = 2 → 나머지 02 ÷ 2 = 1 → 나머지 01 ÷ 2 = 0 → 나머지 1 5. 다음 불 방정식을 logisim을 이용해 회로를 만들어보세요.circ파일링크1.(B’C) + (DB)2.(AB’) +C3.B’ + (DC’) + (DA’)자료구조와 알고리즘문제Python, JavaScript, C# 같은 언어는 가비지 컬렉터를 이용해 메모리를 자동으로 정리하는 매니지드 언어(Managed Language)에 속합니다. 매니지드 언어의 가비지 컬렉터는 개발자가 메모리를 요청하면 운영체제의 힙 영역에 할당하고, 더 이상 필요하지 않을 때 자동으로 해제하며 메모리를 관리합니다. 여러분이 속한 회사에서 새로운 매니지드 언어를 개발 중이며, 여러분은 가비지 컬렉터 개발을 담당하게 되었습니다. 특히 메모리 검색 부분을 맡게 되었는데, 사용자가 특정 크기(Byte)의 메모리를 요청하면 사용 가능한 메모리 중 가장 적절한 크기를 찾아 반환하는 GarbageCollector 클래스를 구현해보세요.(같은 크기의 메모리는 없다고 가정) 풀이내가 만든 AVLTree를 이용해서 풀어보았다key와 같거나 큰 값 중 가장 작은 노드를 찾아야 함예: key = 42, 트리에 {6, 13, 34, 40, 48, 61, ...}이 있다면 → 48 반환해야 함GarbageCollector.cpp#include "AVLTree.h" class GarbageCollector { public: void insertFreeMemory(int size) { tree.Insert(size); } void releaseFreeMemory(int size) { tree.Remove(size); } int searchFreeMemory(int size) { AVLTree::Node* node = tree.GetRoot(); AVLTree::Node* result = nullptr; while (node) { if (node->key == size) return node->key; if (node->key > size) { result = node; node = node->left; } else { node = node->right; } } return result ? result->key : -1; } void printFreeMemory() { tree.printTree(); } private: AVLTree tree; };출력 결과int main() { GarbageCollector gc; cout

인프런 워밍업 클럽 4기 CS 전공지식 1주차 발자국

강의 수강나의 주력 언어는 c++이라서 강의를 토대로 c++버젼으로 바꿔보았다이진 트리 BinaryTree.cpp이진 트리의 주요 특징각 노드는 왼쪽과 오른쪽 자식 노드를 최대 하나씩 가질 수 있습니다.노드 수가 n일 때, 최대 높이는 n, 최소 높이는 log₂(n)입니다.재귀적으로 구성되어 있어 왼쪽/오른쪽 서브트리도 이진 트리입니다.트리 순회 방식에는 전위(preorder), 중위(inorder), 후위(postorder), 레벨 순서(level-order)가 있습니다.노드의 위치가 중요하므로, 왼쪽 자식과 오른쪽 자식은 구분됩니다.시간 복잡도 (BST 기준):평균: 삽입, 탐색, 삭제 모두 O(log n)최악: 트리가 한쪽으로 치우친 경우O(n)#include using namespace std; class BinaryTree { private: struct Node { int data; Node* left; Node* right; Node(int data, Node* left = nullptr, Node* right = nullptr) : data(data), left(left), right(right) {} }; Node* root; public: BinaryTree(int data) { root = new Node(data); } ~BinaryTree() { DestroyTree(root); } Node* GetRoot() const { return root; } Node* GetLeftSubTree() const { return root->left; } Node* GetRightSubTree() const { return root->right; } int getData() const { return root->data; } void printTree() const { printTree(root, 0); } private: // 노드 탐색 (data 기준) Node* FindNode(Node* node, int data) { if (node == nullptr) return nullptr; if (node->data == data) return node; Node* leftSearch = FindNode(node->left, data); if (leftSearch) return leftSearch; return FindNode(node->right, data); } // 트리 파괴 void DestroyTree(Node* node) { if (node == nullptr) return; DestroyTree(node->left); DestroyTree(node->right); delete node; } // 전위 순회 void PreOrderTraversal(Node* node) const { if (node == nullptr) return; cout data left); PreOrderTraversal(node->right); } // 중위 순회 void InOrderTraversal(Node* node) const { if (node == nullptr) return; InOrderTraversal(node->left); cout data right); } // 후위 순회 void PostOrderTraversal(Node* node) const { if (node == nullptr) return; PostOrderTraversal(node->left); PostOrderTraversal(node->right); cout data left = subtree->root; } void SetLeftSubTree(int parentData, int data) { Node* parent = FindNode(root, parentData); if (parent) parent->left = new Node(data); } void SetRightSubTree(BinaryTree* subtree) { root->right = subtree->root; } void SetRightSubTree(int parentData, int data) { Node* parent = FindNode(root, parentData); if (parent) parent->right = new Node(data); } void PreOrderTraversal() const { PreOrderTraversal(root); } void InOrderTraversal() const { InOrderTraversal(root); } void PostOrderTraversal() const { PostOrderTraversal(root); } void printTree(Node* node, int depth) const { if (node == nullptr) return; // 우측 자식 먼저 출력 (트리의 오른쪽이 위로 가게) printTree(node->right, depth + 1); // 현재 노드 출력 for (int i = 0; i data left, depth + 1); } }; 출력 결과int main() { BinaryTree tree(1); tree.SetLeftSubTree(1, 2); tree.SetRightSubTree(1, 3); tree.SetLeftSubTree(2, 4); tree.SetRightSubTree(2, 5); tree.SetLeftSubTree(3, 6); tree.SetRightSubTree(3, 7); cout 이진 탐색 트리BST의 주요 특징왼쪽 서브트리에는 현재 노드보다 작은 값들,오른쪽 서브트리에는 현재 노드보다 큰 값들이 위치합니다.이 속성은 모든 하위 노드에서도 재귀적으로 적용됩니다.중위 순회(Inorder Traversal)를 하면 오름차순 정렬된 값이 출력됩니다.삽입, 삭제, 탐색 시 모두 이진 검색(Binary Search) 원리를 기반으로 진행됩니다.시간 복잡도:탐색, 삽입, 삭제 (평균): O(log n)→ 트리가 균형 잡혀 있을 때 (ex: 높이가 log n 수준)탐색, 삽입, 삭제 (최악): O(n)→ 트리가 한쪽으로 치우친 경우 (ex: 정렬된 데이터만 삽입했을 때)BST의 단점:삽입 순서에 따라 트리 구조가 결정되므로, 균형이 무너지기 쉽습니다.트리가 한쪽으로 치우치면 연결 리스트처럼 동작하게 되어 성능이 나빠집니다.이를 보완하기 위해 AVL 트리, Red-Black 트리 같은 자가 균형 이진 탐색 트리가 존재합니다.BinarySearchTree.h#pragma once enum class Color { Red = 0, Black = 1, }; struct Node { Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; int key = {}; Color color = Color::Black; }; class BinarySearchTree { public: void Print() { Print(_root, 10, 0); } void Print(Node* node, int x, int y); void printTree() const { printTree(_root, 0); } void printTree(Node* node, int depth) const; Node* Search(Node* node, int key); Node* Search2(Node* node, int key); Node* Min(Node* node); Node* Max(Node* node); Node* Next(Node* node); void Insert(int key); void Delete(int key); void Delete(Node* node); void Replace(Node* u, Node* v); private: Node* _root = nullptr; }; BinarySearchTree.cpp#include "BinarySearchTree.h" #include #include using namespace std; void SetCursorPosition(int x, int y) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); COORD pos = { static_cast(x), static_cast(y) }; ::SetConsoleCursorPosition(output, pos); } void BinarySearchTree::Print(Node* node, int x, int y) { if (node == nullptr) return; SetCursorPosition(x, y); cout key; Print(node->left, x - (5 / (y + 1)), y + 1); Print(node->right, x + (5 / (y + 1)), y + 1); } void BinarySearchTree::printTree(Node* node, int depth) const { if (node == nullptr) return; // 우측 자식 먼저 출력 (트리의 오른쪽이 위로 가게) printTree(node->right, depth + 1); // 현재 노드 출력 for (int i = 0; i key left, depth + 1); } Node* BinarySearchTree::Search(Node* node, int key) { while (node && key != node->key) { if (key key) node = node->left; else node = node->right; } return node; } Node* BinarySearchTree::Search2(Node* node, int key) { if (node == nullptr || key == node->key) return node; if (key key) return Search(node->left, key); else return Search(node->right, key); } Node* BinarySearchTree::Min(Node* node) { while (node->left) node = node->left; return node; } Node* BinarySearchTree::Max(Node* node) { while (node->right) node = node->right; return node; } Node* BinarySearchTree::Next(Node* node) { if (node->right) return Min(node->right); Node* parent = node->parent; while (parent && node == parent->right) { node = parent; parent = parent->parent; } return parent; } void BinarySearchTree::Insert(int key) { Node* newNode = new Node(); newNode->key = key; if (_root == nullptr) { _root = newNode; return; } Node* node = _root; Node* parent = nullptr; while (node) { parent = node; if (key key) node = node->left; else node = node->right; } newNode->parent = parent; if (key key) parent->left = newNode; else parent->right = newNode; } void BinarySearchTree::Delete(int key) { Node* deleteNode = Search(_root, key); Delete(deleteNode); } void BinarySearchTree::Delete(Node* node) { if (node == nullptr) return; if (node->left == nullptr) Replace(node, node->right); else if (node->right == nullptr) Replace(node, node->left); else { // 다음 데이터 찾기 Node* next = Next(node); node->key = next->key; Delete(next); } } // u 서브트리를 v 서브트리로 교체 // 그리고 delete u void BinarySearchTree::Replace(Node* u, Node* v) { if (u->parent == nullptr) _root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v) v->parent = u->parent; delete u; } 출력 결과int main() { BinarySearchTree bst; bst.Insert(30); bst.Insert(10); bst.Insert(20); bst.Insert(25); bst.Insert(26); bst.Insert(40); bst.Insert(50); bst.Delete(20); bst.Delete(26); bst.Print(); system("pause"); }AVL TreeAVL 트리란?AVL 트리는 높이 균형 이진 탐색 트리(Height-Balanced BST)의 일종으로, 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 균형을 유지하는 트리입니다. 1962년 Adelson-Velsky와 Landis가 고안했으며, 이름도 그들의 이니셜을 따왔습니다. AVL 트리의 주요 특징각 노드마다 균형 인자(Balance Factor)를 유지하며,이는 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이로 계산됩니다.모든 노드의 균형 인자는 -1, 0, +1 중 하나여야 하며, 이를 벗어나면 회전을 통해 자동 복구합니다.탐색, 삽입, 삭제 모두 O(log n) 시간에 수행되도록 보장합니다.트리가 항상 균형을 유지하므로, 최악의 경우에도 성능이 안정적입니다. AVL 트리의 장점항상 트리의 높이가 O(log n)으로 제한되어 있어 탐색 성능이 매우 좋음이진 탐색 트리의 최악의 경우(O(n))를 방지정렬된 데이터를 입력해도 트리가 한쪽으로 치우치지 않음AVL 트리의 단점삽입과 삭제 시 회전 연산이 발생할 수 있어 구현이 복잡삽입/삭제 연산이 많은 상황에서는 Red-Black Tree보다 오버헤드가 클 수 있음AVL 트리는 언제 유용한가?탐색 속도가 매우 중요한 시스템 (예: 데이터베이스 인덱스)정렬된 데이터를 빈번하게 다루는 경우트리의 높이가 항상 낮게 유지되어야 하는 실시간 시스템AVLTree.h#pragma once #include class AVLTree { public: struct Node { Node* parent = nullptr; Node* left = nullptr; Node* right = nullptr; int key = {}; int height = 1; }; public: void Print() { Print(_root, 10, 0); } void SetCursorPosition(int x, int y); void Print(Node* node, int x, int y); void printTree() const { printTree(_root, 0); std::cout AVLTree.cpp#include "AVLTree.h" #include #include using namespace std; void AVLTree::SetCursorPosition(int x, int y) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); COORD pos = { static_cast(x), static_cast(y) }; ::SetConsoleCursorPosition(output, pos); } void AVLTree::Print(Node* node, int x, int y) { if (node == nullptr) return; SetCursorPosition(x, y); cout key; Print(node->left, x - (5 / (y + 1)), y + 1); Print(node->right, x + (5 / (y + 1)), y + 1); } void AVLTree::printTree(Node* node, int depth) const { if (node == nullptr) return; // 우측 자식 먼저 출력 (트리의 오른쪽이 위로 가게) printTree(node->right, depth + 1); // 현재 노드 출력 for (int i = 0; i key left, depth + 1); } AVLTree::Node* AVLTree::Search(Node* node, int key) { while (node && key != node->key) { if (key key) node = node->left; else node = node->right; } return node; } AVLTree::Node* AVLTree::Search2(Node* node, int key) { if (node == nullptr || key == node->key) return node; if (key key) return Search(node->left, key); else return Search(node->right, key); } AVLTree::Node* AVLTree::Min(Node* node) { while (node->left) node = node->left; return node; } AVLTree::Node* AVLTree::Max(Node* node) { while (node->right) node = node->right; return node; } AVLTree::Node* AVLTree::Next(Node* node) { if (node->right) return Min(node->right); Node* parent = node->parent; while (parent && node == parent->right) { node = parent; parent = parent->parent; } return parent; } void AVLTree::UpdateHeight(Node* node) { int lh = GetHeight(node->left); int rh = GetHeight(node->right); node->height = max(lh, rh) + 1; } int AVLTree::GetHeight(Node* node) { return node ? node->height : 0; } int AVLTree::GetBalance(Node* node) { return node ? GetHeight(node->left) - GetHeight(node->right) : 0; } // [childNode] // [node] [3] // [1] [2] // [node] // [1] [childNode] // [2] [3] AVLTree::Node* AVLTree::RotateRight(Node* node) { Node* childNode = node->left; node->left = childNode->right; if (childNode->right != nullptr) childNode->right->parent = node; childNode->parent = node->parent; if (node->parent == nullptr) _root = childNode; else if (node == node->parent->right) node->parent->right = childNode; else node->parent->left = childNode; childNode->right = node; node->parent = childNode; UpdateHeight(node); UpdateHeight(childNode); return childNode; } AVLTree::Node* AVLTree::RotateLeft(Node* node) { Node* childNode = node->right; node->right = childNode->left; if (childNode->left != nullptr) childNode->left->parent = node; childNode->parent = node->parent; if (node->parent == nullptr) _root = childNode; else if (node == node->parent->left) node->parent->left = childNode; else node->parent->right = childNode; childNode->left = node; node->parent = childNode; UpdateHeight(node); UpdateHeight(childNode); return childNode; } AVLTree::Node* AVLTree::Rotate(Node* targetNode, int data) { int balance = GetBalance(targetNode); bool isRootNode = false; if (targetNode == _root) isRootNode = true; if (balance targetNode->right->key) // LL { targetNode = RotateLeft(targetNode); } else if (balance > 1 && data left->key) // RR { targetNode = RotateRight(targetNode); } else if (balance > 1 && data > targetNode->left->key) // LR { targetNode->left = RotateLeft(targetNode->left); targetNode = RotateRight(targetNode); } else if (balance right->key) // RL { targetNode->right = RotateRight(targetNode->right); targetNode = RotateLeft(targetNode); } if (isRootNode) { _root = targetNode; } return targetNode; } AVLTree::Node* AVLTree::GetUnBalanceNode(Node* node) { if (!node) return nullptr; int balance = GetBalance(node); if (balance > 1 || balance key) { node->left = Insert(node->left, key); if (node->left) node->left->parent = node; } else if (key > node->key) { node->right = Insert(node->right, key); if (node->right) node->right->parent = node; } else { return node; } UpdateHeight(node); return Rotate(node, key); } void AVLTree::Remove(int key) { _root = Remove(_root, key); } AVLTree::Node* AVLTree::Remove(Node* node, int key) { if (!node) return nullptr; if (key == 5) int a = 0; if (key key) { node->left = Remove(node->left, key); } else if (key > node->key) { node->right = Remove(node->right, key); } else { node = RemoveHelper(node); } if (!node) return nullptr; UpdateHeight(node); Node* unbalanced = GetUnBalanceNode(node); if (unbalanced) return Rotate(unbalanced, key); return node; } AVLTree::Node* AVLTree::RemoveHelper(Node* node) { if (!node->left || !node->right) // 자식 노드가 하나 이하일 경우 { Node* temp = node->left ? node->left : node->right; if (!temp) { // 자식이 아예 없는 경우 delete node; return nullptr; } else { // 자식이 하나 있는 경우 -> 그 자식으로 자신을 대체 *node = *temp; delete temp; return node; } } else { // 자식이 둘 다 있는 경우 Node* temp = Min(node->right); // 오른쪽 서브트리에서 가장 작은 값 (후계자) node->key = temp->key; node->right = Remove(node->right, temp->key); return node; } } 출력 결과int main() { AVLTree tree; cout