Data Structures

논리값 (Boolean) Boolean은 컴퓨터 과학에서 가장 기본적인 데이터 타입 중 하나로, 단 두 가지 값만을 가질 수 있는 논리 데이터 타입이다. Boolean 데이터 타입은 참(true)과 거짓(false)의 두 가지 값만을 가질 수 있는 데이터 타입으로, 수학자 George Boole의 이름을 따서 명명되었으며, 논리 연산과 조건문에서 주로 사용된다. 특징 오직 두 가지 값만 가짐: true 또는 false 조건문과 논리 연산에서 주로 사용됨 메모리 사용이 효율적 (일반적으로 1비트만으로도 표현이 가능하다(true = 1, false = 0). 하지만 실제 프로그래밍 언어에서는 메모리 정렬(alignment) 때문에 보통 1바이트를 사용) 특성 비교 연산의 결과로 자주 생성됨 제어 흐름을 결정하는 데 중요한 역할을 함 다른 데이터 타입으로부터 변환 가능 (예: 숫자 0은 false, 나머지는 true) 연산 종류 및 설명 논리 연산 AND (&&): 두 피연산자가 모두 true일 때만 true 반환 OR (||): 두 피연산자 중 하나라도 true이면 true 반환 NOT (!): 피연산자의 값을 반전 비교 연산 동등 비교 (==, ===) 부등 비교 (!=,!==) 대소 비교 (<, >, <=, >=) 실제 활용 사례 및 설명 조건문에서의 사용 플래그 변수로 사용 (예: 상태 체크) 데이터 유효성 검사 각 언어별 예시와 특징 각 언어의 특징적인 부분을 살펴보면: ...

문자 (Character) 단일 문자를 표현하는 데이터 타입이다. 각 프로그래밍 언어별로 character의 구현과 사용 방식이 다소 다르다. Character는 단일 문자를 나타내는 데이터 타입으로, 일반적으로 문자, 숫자, 특수 문자, 공백 등을 포함할 수 있다. 특징 고정 크기: 대부분의 언어에서 character는 고정된 메모리 크기를 가진다. 유니코드 지원: 많은 현대 프로그래밍 언어에서 유니코드 문자를 지원한다. 정수형과의 호환성: 대부분의 언어에서 character는 정수형으로 변환 가능하다. 특성 불변성: 많은 언어에서 character는 불변(immutable) 타입이다. 순서성: ASCII 또는 유니코드 값을 기반으로 순서를 가진다. 단일 값: 하나의 문자만을 저장할 수 있다. 연산 종류 및 설명 비교 연산: 문자 간 대소 비교가 가능하다. 산술 연산: 정수형으로 변환하여 산술 연산이 가능하다. 형변환: 정수형이나 문자열로의 변환이 가능하다. 실제 활용 사례 및 설명 Java Java에서는 ‘char’ 키워드를 사용하여 character를 선언한다. ...

정수 (Integer) 정수(Integer)는 소수점이 없는 양수, 음수, 0을 표현하는 데이터 타입으로, 컴퓨터에서는 이진수로 표현되며, 일정 범위의 정수를 표현할 수 있다. 특징과 특성 고정된 크기의 메모리 사용 빠른 연산 속도 범위의 제한 (오버플로우 가능성) 직접적인 산술 연산 지원 종류 byte 범위: -128 ~ 127 8비트 비트 구성: 1비트 부호 + 7비트 값 특징: 가장 작은 정수 타입 메모리 효율적이지만 표현 범위가 제한적 주로 작은 범위의 데이터나 문자 표현에 사용 short 범위: -32,768 ~ 32,767 16비트 비트 구성: 1비트 부호 + 15비트 값 특징: 8비트보다 넓은 범위 표현 가능 메모리 사용량과 표현 범위의 균형이 좋음 작은 정수 값을 다룰 때 효율적 int ...

부동 소수점 (Float) 부동 소수점은 실수를 (부호) × (가수) × (밑수)^(지수) 형태로 표현하는 방식이다. ‘부동’은 소수점이 움직인다는 의미로, 넓은 범위의 실수를 표현할 수 있다. 특징 IEEE 754 표준을 따름 부호, 지수, 가수 부분으로 구성 IEEE 754 표준에 따른 부동 소수점 종류 Half Precision 이 형식은 가장 작은 부동 소수점 표현 방식. 16비트를 사용한다. 1비트는 부호, 5비트는 지수부, 10비트는 가수부로 구성된다. 주로 그래픽스나 머신러닝에서 메모리를 절약하기 위해 사용된다. 약 3자리의 십진 정밀도를 제공하며, ±6.1 × 10⁻⁵에서 ±6.5 × 10⁴까지의 범위를 표현할 수 있다. 예시: Python: 1 2 3 import numpy as np x = np.float16(3.14) print(x) # 3.14 JavaScript: JavaScript는 기본적으로 Half Precision을 지원하지 않는다. 외부 라이브러리를 사용해야 한다. ...

Non-Primitive Linear Data Structure vs. Non-Linear Data Structure 데이터 구조는 크게 Linear Data Structure와 Non-Linear Data Structure로 나눌 수 있다. 측면 Linear Data Structure Non-Linear Data Structure 정의 데이터 요소가 순차적 또는 선형적으로 배열된 구조 데이터 요소가 순차적이거나 선형적으로 배열되지 않은 구조 구조 단일 레벨 구조 다중 레벨 구조 데이터 관계 요소 간 1:1 관계 요소 간 1:N 또는 N:N 관계 순회 단일 실행으로 모든 요소 순회 가능 단일 실행으로 모든 요소 순회 불가능 구현 복잡성 구현이 상대적으로 간단 구현이 상대적으로 복잡 메모리 사용 메모리 사용이 덜 효율적 메모리 사용이 더 효율적 시간 복잡도 입력 크기에 따라 증가 특정 작업에서 더 효율적 데이터 접근 순차적 접근 계층적 또는 네트워크 기반 접근 삽입/삭제 상대적으로 간단 더 복잡하지만 유연함 응용 분야 간단한 데이터 저장 및 처리 복잡한 관계 표현, AI, 이미지 처리 등 예시 배열, 연결 리스트, 스택, 큐 트리, 그래프, 해시 테이블, 힙 공통점: ...

Primitive Data Structure vs. Non-Primitive Data Structure Primitive Data Structure Primitive data structure는 프로그래밍 언어에 내장된 가장 단순하고 기본적인 데이터 타입이다. 이들은 단일 값을 표현하며, 더 이상 분해할 수 없는 가장 작은 단위의 데이터 구조이다. 주요 특징 단순성: 가장 기본적이고 이해하기 쉬운 데이터 타입이다. 고정 크기: 일반적으로 고정된 메모리 크기를 가진다. 효율성: 메모리 사용과 접근 시간 측면에서 매우 효율적이다. 직접 표현: 컴퓨터 하드웨어에서 직접 지원되는 데이터 타입이다. 값 의미론: 변수에 실제 값이 직접 저장된다. 스택 할당: 주로 스택 메모리에 할당되어 빠른 접근이 가능하다. 주요 primitive data structure들을 비교 분석하여 정리한 표: ...

Suffix Array vs. Suffix Tree vs. Trie Suffix Array, Suffix Tree, 그리고 Trie는 모두 문자열 처리와 패턴 매칭을 위한 데이터 구조로, 각각 고유한 특성과 용도를 가지고 있다. 특성 Suffix Array Suffix Tree Trie 기본 구조 모든 접미사를 정렬하여 저장하는 1차원 배열 모든 접미사를 트리 형태로 저장하는 압축된 트리 구조 문자열을 문자 단위로 저장하는 트리 구조 메모리 효율성 O(n), 매우 효율적 O(n), 하지만 실제로는 4n 정도로 큼 O(ALPHABET_SIZE key_length n), 매우 큼 구축 시간 O(n log n) O(n) (Ukkonen’s Algorithm 사용 시) O(n * key_length) 검색 시간 O(m log n + occ), m은 패턴 길이 O(m + occ), m은 패턴 길이 O(m), m은 검색할 문자열 길이 구현 난이도 비교적 간단 매우 복잡 비교적 간단 LCP 계산 추가 배열 필요 트리 구조에서 직접 계산 가능 해당 없음 패턴 매칭 이진 검색 이용 트리 순회로 직접 검색 트리 순회로 직접 검색 공간 지역성 매우 좋음 (연속된 메모리) 보통 (포인터로 인한 흩어짐) 나쁨 (노드가 메모리에 흩어짐) 주요 응용 텍스트 검색, DNA 분석 문자열 처리, 바이오인포매틱스 사전 구현, 자동 완성 동적 업데이트 어려움 가능하나 복잡 쉬움 접두사 검색 어려움 가능하나 비효율적 매우 효율적 최장 공통 접두사 추가 작업 필요 직접 계산 가능 직접 계산 가능 최장 공통 부분 문자열 LCP 배열 필요 직접 계산 가능 부적합 압축 가능성 제한적 매우 좋음 있음 (압축 트라이) 캐시 성능 매우 좋음 보통 나쁨 실제 사용 사례 대용량 문자열 검색 시스템 생물정보학, 문자열 처리 자동 완성, 사전 검색 추가적인 중요 고려사항: ...

스패닝 트리(Spanning Tree) 스패닝 트리(Spanning Tree) 는 무방향 그래프(Undirected Graph)의 모든 정점을 포함하면서, 사이클 없이 연결된 부분 그래프이다. 다시 말해, 원래 그래프의 모든 정점을 최소한의 간선으로 연결한 트리 구조이다. 신장 트리는 그래프 이론의 핵심 개념으로, 다양한 실제 문제 해결에 활용된다. 최소 신장 트리 알고리즘인 크루스칼, 프림, 보로프카는 각각 다른 상황에서 최적의 성능을 보이며, 알고리즘 선택은 그래프의 특성과 문제 요구사항에 따라 달라진다. 신장 트리의 응용은 네트워크 설계, 클러스터링, 이미지 처리 등 다양한 분야에 걸쳐 있으며, 그 변형과 확장은 더 복잡한 문제를 해결하는 데 도움이 된다. 최적화 기법과 효율적인 자료구조를 활용하면 대규모 그래프에서도 신장 트리를 효과적으로 계산할 수 있다. ...

무방향 그래프(Undirected Graph) 무방향 그래프(Undirected Graph) 는 각 간선(Edge)에 방향성이 없는 그래프이다. 즉, 정점 A와 정점 B가 간선으로 연결되어 있으면, A에서 B로 가는 것과 B에서 A로 가는 것이 동일하다. 무방향 그래프 특징 간선이 양방향(↔)으로 연결됨 정점 간 이동에 방향성이 없음 정점의 차수(Degree)는 해당 정점과 연결된 간선의 개수 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 알고리즘이 적용 가능 연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph) 개념 적용 가능 무방향 그래프의 표현 방법 1 2 3 A — B | | C — D A - B (A와 B는 서로 연결됨) A - C (A와 C는 서로 연결됨) B - D (B와 D는 서로 연결됨) C - D (C와 D는 서로 연결됨) 무방향 그래프의 인접 행렬(Adjacency Matrix) 표현 A B C D A 0 1 1 0 B 1 0 0 1 C 1 0 0 1 D 0 1 1 0 설명 ...

방향 그래프(Directed Graph) 방향 그래프(Directed Graph, Digraph) 는 각 간선(Edge)에 방향성이 부여된 그래프이다. 즉, 간선이 단방향이므로 A → B 는 이동할 수 있지만 B → A 로는 이동할 수 없다. 방향 그래프는 일방향 관계가 있는 다양한 시스템을 모델링할 수 있다. 웹, 사회 연결망, 컴퓨터 시스템, 생물학적 네트워크 등 다양한 분야에서 방향 그래프를 활용한 알고리즘과 모델이 개발되고 있다. 방향 그래프 특징 간선이 한 방향(→)으로만 연결됨 단방향 관계를 표현할 때 사용 (예: 팔로우 관계, 웹 페이지 링크) 진입 차수(In-degree)와 진출 차수(Out-degree) 개념이 존재 진입 차수(In-degree): 해당 정점으로 들어오는 간선의 개수 진출 차수(Out-degree): 해당 정점에서 나가는 간선의 개수 방향 그래프의 표현 방법 방향 그래프 예시 ...