Computer Science27 [DataStructure/Tree] 우선순위 큐, 힙, 이진 탐색 트리의 개념과 차이점 정리 트리 자료구조를 공부하다 보니 이진 트리(Binary Tree), 힙(Heap), 이진 탐색 트리(BST), 우선순위 큐(Priority Queue) 등의 개념이 서로 얽혀 있어 혼란스러웠습니다.각 개념의 관계를 정리하면 트리를 더 잘 이해하는 데 도움이 될 것 같아, 이번 기회에 깔끔하게 정리해 보았습니다.1. 이진 트리 (Binary Tree)개념각 노드는 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다.이진 트리는 단순한 자료구조이며, 정렬 방식이나 데이터 접근 규칙이 따로 정해져 있지 않습니다.노드 개수는 최대 2^h - 1 개입니다. (h는 트리의 높이)특징탐색 규칙이 없는 단순한 구조적 개념입니다.왼쪽, 오른쪽 자식을 가지는 트리 형태일 뿐입니다.예시 A / \.. 2025. 2. 12. [DataStructure/Map, Set, List] Map vs Set vs List: 순서 보장과 중복 허용 차이 정리 Map, Set, List는 대부분의 프로그래밍 언어에서 자주 사용되는 대표적인 자료구조입니다.어렴풋이 알고 있다고 생각했지만, 막상 설명해보려니 정확하게 이해하지 못하고 있다는 느낌이 들었습니다.그래서 이번 글에서는 Map, Set, List의 동작 방식과 구현체별 차이점을 정리하면서, 순서 보장 여부와 중복 허용 여부를 명확하게 정리해두려고 합니다.1. Map, Set, List의 기본적인 차이점특징Map (Key-Value 저장)Set (중복 없는 값 저장)List (중복 허용, 순서 유지)데이터 저장 방식Key-Value 쌍으로 저장중복 없는 단일 값(Value) 저장중복을 허용하며 순서대로 값 저장중복 허용 여부Key 중복 ❌, Value는 중복 가능중복 ❌중복 ⭕순서 보장 여부구현체에 따라 다.. 2025. 2. 12. [DataStructure/Set] Set의 contains() 시간 복잡도 정리: HashSet, TreeSet, LinkedHashSet 비교 Set을 공부하던 중, Set.contains() 메서드의 시간 복잡도가 궁금했는데, Set의 자료구조 종류에 따라 contains()의 성능이 달라진다는 것을 알게 되었습니다.특히, HashSet, TreeSet, LinkedHashSet과 같이 구현 방식이 다른 Set은 각각 다른 자료구조를 사용하기 때문에 contains()의 시간 복잡도도 다르게 동작합니다.이번 글에서는 Set의 종류별 contains() 성능 차이와 시간 복잡도를 정리해 보겠습니다.1. Set.contains()의 시간 복잡도는 언제 달라질까?Set.contains(element) 메서드는 Set에 특정 요소가 존재하는지 여부를 확인하는 메서드입니다.하지만 Set의 내부 자료구조에 따라 검색 속도가 다르게 동작합니다.HashSe.. 2025. 2. 11. [DataStructure/LinkedHashMap] LRU 캐시와 LinkedHashMap 기반 Glide Bitmap 최적화 최근에 LinkedList 사용 예제를 공부하던 중, LRU 캐시(Least Recently Used Cache)라는 개념을 알게 되었습니다.LRU 캐시는 오래 사용되지 않은 데이터를 자동으로 삭제하는 캐싱 기법으로, 메모리 관리에서 중요한 역할을 합니다.그런데, LRU 캐시는 단순한 LinkedList가 아니라, "해시 테이블과 이중 연결 리스트가 결합된 LinkedHashMap을 활용하여 구현되는 경우가 많다"는 것을 알게 되었습니다.또한, 안드로이드에서 Glide 라이브러리도 LinkedHashMap을 기반으로 한 LRU 캐시를 활용하여 Bitmap(이미지) 데이터를 캐싱하고 있었습니다.따라서 이번 글에서는 LRU 캐시의 개념과 함께, Glide가 이를 활용하여 어떻게 성능을 최적화하는지 정리해 두.. 2025. 2. 11. [Algorithm/Kotlin] 백준 1003번 피보나치 함수: DP를 활용한 풀이법 문제 설명주어진 문제는 재귀적으로 정의된 피보나치 함수에서 0과 1이 출력되는 횟수를 구하는 것입니다.C++의 재귀 구현을 보면, fibonacci(n)을 호출할 때 fibonacci(n-1)과 fibonacci(n-2)를 호출하는 방식으로 동작합니다. 이 과정에서 동일한 fibonacci 함수가 여러 번 호출되며 중복 계산이 발생합니다.예를 들어, fibonacci(3)을 호출하면 아래와 같은 과정이 발생합니다:fibonacci(3) -> fibonacci(2) + fibonacci(1)을 호출합니다.fibonacci(2) -> fibonacci(1) + fibonacci(0)을 호출합니다.fibonacci(1)이 1을 출력하고 반환합니다.fibonacci(0)이 0을 출력하고 반환합니다.fibonac.. 2025. 2. 7. [Algorithm/Kotlin] 백준 11723번 집합: 집합 연산 최적화 MutableSet vs. 비트마스크(Bitmask) 이번 글에서는 MutableSet과 비트마스크(Bitmask) 두 가지 방식을 비교하며, 새롭게 알게 된 비트마스크를 활용한 집합 연산 최적화 방법을 정리해보겠습니다.1. 문제 설명비어있는 공집합 S가 주어졌을 때, 다음 연산을 수행하는 프로그램을 작성하세요.add x : S에 x를 추가 (1 ≤ x ≤ 20)remove x : S에서 x를 제거check x : S에 x가 있으면 1, 없으면 0 출력toggle x : S에 x가 있으면 제거, 없으면 추가all : S를 {1, 2, ..., 20}으로 변경empty : S를 공집합 {}으로 변경입력M (1 ≤ M ≤ 3,000,000): 연산 개수이후 M개의 연산이 주어짐출력check 연산이 수행될 때마다 결과를 출력2. 문제 해결 아이디어이 문제를 해결.. 2025. 2. 3. 프로세스와 스레드 운영체제를 공부하면서 프로세스(Process)와 스레드(Thread)는 개념을 자주 접하게 되었습니다.이 둘은 프로그램이 어떻게 실행되고 동작하는지 설명하는 기본적인 단위인데요, 헷갈리기 쉬운 이 개념을 간단히 정리해보겠습니다.프로세스란 무엇인가?프로세스는 실행 중인 프로그램을 의미합니다.프로그램은 단순히 저장된 코드일 뿐이고, 프로세스는 메모리에서 실행되는 프로그램의 실체입니다.프로세스는 독립적인 실행 단위로, 운영체제는 프로세스마다 고유한 메모리 공간과 자원을 할당합니다.프로세스의 특징:독립적인 메모리 공간: 프로세스마다 Code, Data, Heap, Stack 영역이 독립적으로 존재합니다. 한 프로세스는 다른 프로세스의 메모리에 직접 접근할 수 없습니다.운영체제의 스케줄링 대상: CPU.. 2025. 1. 24. 프로세스 상태 전이 다이어그램(Process State Transition Diagram) 운영체제에서 프로세스(Process)는 실행 중인 프로그램을 의미합니다. 하지만 하나의 프로그램이 항상 실행 상태에 있는 것은 아닙니다. 프로세스는 실행을 준비하거나, 대기하거나, 종료되는 등 다양한 상태를 거칩니다. 이러한 상태를 시각적으로 나타낸 것이 Process State Transition Diagram입니다. 이번 글에서는 프로세스의 상태와 전이 과정을 쉽게 이해할 수 있도록 정리해 보겠습니다.프로세스의 주요 상태Created (생성 상태) 프로세스가 막 생성된 초기 상태입니다. 아직 CPU를 할당받지 않았으며 실행 준비 중입니다. 다음 상태: Ready 상태로 전환.Ready (준비 상태) 프로세스가 실행 준비를 마친 상태로, CPU를 할당받기 위해 대기합니다. CPU 스케.. 2025. 1. 24. 운영체제란 무엇인가? 운영체제(Operating System, OS)는 컴퓨터 시스템의 핵심 소프트웨어로, 하드웨어와 소프트웨어를 관리하며 사용자와 컴퓨터 간의 인터페이스 역할을 합니다. 운영체제는 컴퓨터의 다양한 리소스를 효율적으로 관리하고, 응용 프로그램이 하드웨어를 사용할 수 있도록 지원합니다.이번 글에서는 운영체제가 무엇인지와 운영체제가 관리하는 주요 리소스에 대해 정리해보겠습니다.운영체제의 정의운영체제는 다음과 같은 역할을 수행합니다:하드웨어 리소스 관리: CPU, 메모리, 디스크 등 하드웨어 자원을 효율적으로 관리.소프트웨어 리소스 관리: 파일 시스템, 프로세스, 네트워크 등 소프트웨어 자원의 동작을 조율.사용자와 컴퓨터 간의 인터페이스 제공: 사용자 명령을 하드웨어가 이해할 수 있는 형태로 변환.운영체제는 컴퓨터.. 2025. 1. 24. 이전 1 2 3 다음 반응형
