Computer Science/Data Structure8 [DataStructure/Graph] 완전 탐색 문제를 해결하는 두 가지 방법: 인접 행렬 vs 인접 리스트 완전 탐색 문제를 풀면서 완전 탐색을 구현하는 방식에는 두 가지 방법(인접 행렬과 인접 리스트)이 있다는 것을 알게 되었습니다.각 방식이 어떤 경우에 유리하게 활용되는지 문제를 통해 정리해 두면 좋을 것 같아 이번 글을 작성하게 되었습니다.이번 글에서는 완전 탐색을 인접 행렬과 인접 리스트를 사용하여 해결할 때의 차이점과 각각의 장단점을 두 가지 문제를 예제로 설명하겠습니다.1. 인접 행렬을 사용하는 경우1.1 인접 행렬(Adjacency Matrix) 개념배열(Array) 기반이며, BooleanArray를 사용하여 간선 유무를 표현합니다.graph[i][j] = true이면 i번 노드와 j번 노드가 연결된 것입니다.graph[i][j] = false이면 연결되지 않은 상태입니다.공간 복잡도: O(N^.. 2025. 2. 27. [DataStructure/Kotlin] Kotlin에서 Array, List, MutableList, ArrayList의 차이 정리 Kotlin에서는 Array, List, MutableList, ArrayList 등 다양한 컬렉션 타입을 사용할 수 있습니다.이들은 모두 여러 개의 값을 저장하는 자료구조이지만, 동작 방식과 활용법이 서로 다릅니다.이번 글에서는 각 자료구조의 특징과 차이점, 그리고 언제 어떤 것을 사용해야 하는지 정리하겠습니다.1. Array vs List → 수정 가능 여부 차이Array는 값 변경 가능하지만 크기 변경은 불가능val arr = arrayOf(1, 2, 3)arr[0] = 10 // 값 변경 가능println(arr.joinToString()) // 10, 2, 3// arr.add(4) // 컴파일 오류 (크기 변경 불가능)Array는 배열 크기가 고정되어 있지만, 인덱스를 통해 값 변경이 가.. 2025. 2. 13. [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. [DataStructure/Kotlin] pop과 peak의 차이점: 스택의 두 가지 주요 기능 스택(Stack)은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 저장하는 자료 구조입니다. 스택에서 자주 사용되는 두 가지 주요 연산은 pop과 peak입니다. 이 두 연산은 비슷하게 보이지만, 의미와 사용 목적에서 분명한 차이가 있습니다.이를 이해하기 쉽게 정리 해 보겠습니다. 1. pop과 peak의 정의pop:스택의 가장 위에 있는 요소를 제거하면서 반환합니다.스택의 상태를 변경하며, 크기가 줄어듭니다.peak:스택의 가장 위에 있는 요소를 그대로 반환합니다.스택의 상태를 변경하지 않습니다. 단순히 데이터를 확인하는 용도로 사용됩니다. 2. 코틀린 구현 예제val stack = mutableListOf()fun push(data: Int) { stack.add(dat.. 2025. 1. 17. [DataStructure/Kotlin] 스택 구현: MutableList vs Array의 차이점과 구현 방법 스택(Stack)은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 저장하는 자료 구조입니다.코틀린에서 스택을 구현할 때 주로 사용하는 두 가지 주요 데이터 구조는 MutableList와 Array입니다.이번 글에서는 두 가지 방법으로 스택을 구현하는 코드와 함께, 각 방식의 차이점과 특징을 비교해보겠습니다.1. MutableList를 사용한 스택 구현MutableList는 코틀린의 동적 리스트로, 크기를 필요에 따라 자동으로 확장하거나 축소할 수 있습니다.이를 사용하면 스택을 간단하고 유연하게 구현할 수 있습니다.코드 예제:val stack = mutableListOf()fun push(data: Int) { stack.add(data) // 스택의 끝에 데이터 추가}fun.. 2025. 1. 17. 이전 1 다음 반응형
