Types

Rope Rope는 대규모 문자열을 효율적으로 저장하고 조작하기 위해 설계된 트리 기반의 데이터 구조로, 각 리프 노드(끝 노드)는 문자열과 길이(“weight"라고도 함)를 저장하고, 트리의 상위 노드들은 왼쪽 서브트리의 모든 리프 노드 길이의 합을 저장한다. https://www.geeksforgeeks.org/ropes-data-structure-fast-string-concatenation/ 특징 트리 구조: Rope는 이진 트리 형태를 가진다. 분할 저장: 큰 문자열을 작은 조각으로 나누어 저장한다. 가중치: 각 노드는 왼쪽 서브트리의 문자열 길이를 저장한다. 불변성: 일반적으로 Rope의 노드들은 불변(immutable) 객체로 취급된다. 장점 효율적인 연산: 문자열 연결, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있다. 메모리 효율성: 대규모 문자열 조작 시 추가 메모리 사용이 적다. 지속성: 비파괴적 연산을 사용하면 여러 단계의 실행 취소를 쉽게 지원할 수 있다. 단점 복잡성: 구조가 복잡하여 구현과 관리가 어려울 수 있다. 오버헤드: 작은 문자열에 대해서는 일반 문자열보다 성능이 떨어질 수 있다. 메모리 사용: 부모 노드 저장을 위해 추가 메모리가 필요하다. 응용 텍스트 에디터: Sublime Text 등의 텍스트 에디터에서 대용량 텍스트 처리에 사용된다. 이메일 시스템: Gmail과 같은 이메일 시스템에서 메시지 처리에 활용된다. 프로그래밍 환경: Cedar 프로그래밍 환경에서 사용된다. 동작 원리 문자열 분할: 큰 문자열을 작은 조각으로 나누어 트리의 리프 노드에 저장한다. 트리 구성: 리프 노드들을 이진 트리 형태로 구성한다. 가중치 계산: 각 내부 노드는 왼쪽 서브트리의 문자열 길이 합을 저장한다. 연산 수행: 트리 구조를 활용하여 효율적인 문자열 연산을 수행한다. 구성 요소 리프 노드: 실제 문자열 조각과 그 길이를 저장한다. 내부 노드: 왼쪽 서브트리의 길이(가중치)를 저장한다. 루트 노드: 전체 Rope의 시작점이다. 링크: 노드 간의 연결을 나타낸다. 구현 방식 Rope의 기본적인 구현은 이진 트리를 기반으로 한다. 다음은 Python을 사용한 간단한 Rope 구현 예시: ...

Suffix Tree Suffix Tree는 주어진 문자열의 모든 접미사(suffix)를 압축된 트라이(trie) 형태로 표현한 트리 구조로, 각 간선은 문자열의 부분 문자열을 나타내며, 리프 노드는 접미사의 시작 위치를 나타낸다. https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/ 특징 모든 접미사를 트리 형태로 표현한다. 공통 접두사를 공유하여 압축된 형태로 저장한다. 트리의 높이는 항상 O(n)을 유지한다. 장점 패턴 매칭, 최장 공통 부분 문자열 찾기 등의 연산을 효율적으로 수행한다. 검색 시간이 O(m)으로 매우 빠릅니다(m은 찾는 패턴의 길이). 다양한 문자열 관련 문제를 해결하는 데 활용될 수 있다. 단점 구현이 복잡하고 메모리 사용량이 많다. 구축 비용이 높다. 응용 문자열 검색 및 패턴 매칭 DNA 시퀀싱 및 생물정보학 분석 데이터 압축 알고리즘 텍스트 인덱싱 및 전체 텍스트 검색 동작 원리 문자열의 모든 접미사를 트리에 삽입한다. 공통 접두사를 공유하는 노드를 압축한다. 각 리프 노드에 접미사의 시작 위치를 저장한다. 구성 요소 루트 노드: 트리의 시작점 내부 노드: 공통 접두사를 나타내는 노드 리프 노드: 접미사의 끝을 나타내는 노드 간선: 노드 사이를 연결하며 부분 문자열을 나타냄 구현 방식 Suffix Tree는 일반적으로 Ukkonen’s 알고리즘을 사용하여 선형 시간에 구축할 수 있다. ...

디스조인트 셋 (Disjoint-Set) 디스조인트 셋은 서로 겹치지 않는(disjoint) 부분 집합들로 나누어진 요소들의 집합을 표현하고 조작하는 데이터 구조이다. 각 부분 집합은 대표 요소(representative)를 가지며, 이를 통해 집합을 식별한다. 특징 동적 집합 관리: 요소들을 동적으로 그룹화하고 관리할 수 있다. 빠른 연산: Union과 Find 연산을 매우 효율적으로 수행한다. 경로 압축과 랭크 최적화: 트리 구조를 최적화하여 성능을 향상시킨다. 장점 효율성: 거의 상수 시간에 가까운 연산 복잡도를 제공한다. 간단한 구현: 기본 개념이 직관적이고 구현이 비교적 간단하다. 메모리 효율성: 추가적인 데이터 구조 없이 요소들의 관계를 표현한다. 단점 제한된 기능: 주로 Union과 Find 연산에 특화되어 있어 다른 복잡한 연산은 지원하지 않는다. 초기 설정 비용: 모든 요소에 대해 초기 집합을 생성해야 한다. 응용 Kruskal의 최소 신장 트리 알고리즘 사이클 검출 알고리즘 네트워크의 연결성 확인 이미지 세그멘테이션 동작 원리 디스조인트 셋은 트리 구조를 사용하여 집합을 표현한다. 각 트리의 루트 노드가 해당 집합의 대표 요소가 된다. ...

Harvard Architecture 하버드 아키텍처(Harvard Architecture)는 프로세서 설계에서 중요한 구조로, 명령어와 데이터를 위한 별도의 메모리 및 버스 시스템을 사용하는 컴퓨터 아키텍처이다. 하버드 아키텍처는 다음과 같은 주요 특징을 가지고 있다: 메모리 분리: 프로그램(명령어) 메모리와 데이터 메모리가 물리적으로 분리되어 있다. 독립적 접근: CPU가 명령어와 데이터에 동시에 접근할 수 있어, 병렬 처리가 가능하다. 버스 구조: 명령어용 버스와 데이터용 버스가 별도로 존재한다. 성능 향상: 메모리 접근의 병렬화로 인해 처리 속도가 향상된다. 기본 구조: 1 2 3 4 5 [프로그램 메모리] [데이터 메모리] ↓ ↓ [CPU] ←→ [제어 유닛] ↓ ↓ [프로그램 버스] [데이터 버스] https://www.researchgate.net/figure/Harvard-architecture-scheme_fig6_356598013 ...

Von Neumann Architecture Von Neumann architecture는 1945년 John von Neumann이 제안한 컴퓨터 아키텍처로, 현대 대부분의 컴퓨터 시스템의 기본이 되는 설계이다. Source: https://www.geeksforgeeks.org/computer-organization-von-neumann-architecture/ 특징 순차적 실행: 명령어를 메모리에서 한 번에 하나씩 순차적으로 가져와 실행 레지스터: 프로그램 카운터 (PC): 다음 실행할 명령어의 주소 저장 명령어 레지스터 (CIR): 현재 실행 중인 명령어 저장 메모리 주소 레지스터 (MAR): 접근할 메모리 주소 저장 메모리 데이터 레지스터 (MDR): 메모리와 주고받는 데이터 저장 누산기 (Accumulator): 연산 결과 임시 저장 버스 시스템: ...