Stitchhhh

비트마스킹이번 포스트에서 정리할 주제는 비트마스킹입니다. 비트마스킹은 알고리즘 문제에서 자주 등장하는 기법 중 하나로 이진수(bit)를 활용해 여러 개의 상태를 한 개의 정수로 표현할 수 있도록 도와주며, 공간 절약과 연산 최적화 측면에서 매우 유용합니다. 예시는 다음과 같습니다.n = 5 → 101→ 0, 2번 인덱스가 켜져 있다라는 의미로 해석이 가능합니다.비트마스킹 활용 사례부분 집합을 효율적으로 순회할 때중복 방문을 피하는 DP/DFS에서 방문 여부를 저장할 때상태를 배열 대신 정수 하나로 표현하고 싶을 때메모리/성능 최적화가 필요할 때 기본 연산 정리표 연산 목적 표현식 설명 예제 입력 / 결과 예시 i번째 비트 켜기 (Set)S = S | (1 i번째 자리를 1로 설정S = 0; i = 2..

이번 포스트에서는 Character, String, StringBuilder에 대해서 정리해보겠습니다. 해당 포스트의 카테고리를 Java, 알고리즘에서 고민을 했는데 Character, String, StringBuilder의 주요 메소드와 시간복잡도를 함께 설명할 계획이기 때문에 알고리즘 카테고리로 선정하였습니다.Character, String, StringBuilderJava에서 문자열 및 문자 데이터를 처리할 때 주로 사용하는 클래스는 다음 세 가지입니다:Character: 문자(char) 하나를 다루는 클래스String: 불변(immutable) 문자열StringBuilder: 가변(mutable) 문자열, 성능 중심Characterchar 타입을 감싸는 래퍼 클래스이며, 문자 하나를 판단하거나 ..

HashMap vs TreeMap vs LinkedHashMap 항목 HashMap TreeMap LinkedHashMap 기반 자료구조Hash TableRed-Black TreeHash Table + Linked List정렬 여부❌ 없음✅ 자동 정렬 (Key 기준 오름차순)❌ 없음삽입 순서 유지❌ 없음❌ 없음 (정렬 순서로 유지됨)✅ 유지null 키 허용✅ 1개 허용❌ (NullPointerException 발생)✅ 1개 허용null 값 허용✅✅✅시간 복잡도 (삽입/삭제/조회)평균 O(1)O(log n)평균 O(1)Iterator 순회 순서예측 불가Key 정렬 순삽입 순Key 비교 방식equals() + hashCode()compareTo() 또는 Comparatorequals() + hashCode..

TreeMapTreeMap은 Java의 Map 인터페이스를 구현한 클래스 중 하나로, 키를 자동으로 정렬하며 내부적으로 **Red-Black Tree(이진 탐색 트리)**를 사용합니다.범위 검색이나 정렬 기반의 탐색에 적합합니다.주요 특징자료구조레드-블랙 트리 (Red-Black Tree)정렬 여부✅ 자동 정렬 (Key 기준 오름차순)삽입 순서 유지❌ (정렬 순서대로 유지됨)null 허용❌ Key는 허용 X, Value는 허용 O시간 복잡도O(log n)특징Key 정렬, 범위 탐색, ceiling, floor 등 사용 가능대표 메서드package structure.map.treemap;import java.util.Map;import java.util.TreeMap;public class TreeMapC..

LinkedHashMapLinkedHashMap은 HashMap의 기능을 그대로 유지하면서, 입력 순서를 기억하는 Map입니다.내부적으로 해시 테이블 + 이중 연결 리스트를 사용하여, 순서를 보장합니다.주요 특징자료구조HashMap + 이중 연결 리스트정렬 여부❌삽입 순서 유지✅null 허용✅ (Key 1개, Value 다수 허용)시간 복잡도평균 O(1)특징순서 + 빠른 접근이 필요한 경우 (ex. 캐시 구현)대표 메서드package structure.map.linkedhashmap;import java.util.LinkedHashMap;public class LinkedHashMapClass { private final LinkedHashMap linkedHashMap; public Link..

HashMap HashMap은 Java의 가장 일반적인 Map 구현체로, 키-값 쌍(Key-Value Pair)을 저장하며, 내부적으로 해시 테이블(Hash Table) 기반으로 작동합니다.정렬 순서나 삽입 순서를 유지하지 않지만, 탐색 및 삽입 속도가 매우 빠릅니다.주요 특징자료구조해시 테이블 (HashTable)정렬 여부❌ 없음 (순서 보장 X)삽입 순서 유지❌null 허용✅ (Key 1개 + Value 여러 개 허용)시간 복잡도평균 O(1) (삽입, 삭제, 조회)특징가장 빠르며, 가장 자주 사용됨. 순서가 중요하지 않을 때 사용대표 메서드package structure.map.hashmap;import java.util.Collection;import java.util.HashMap;public c..

TreeSet vs HashSet vs LinkedHashSet항목 TreeSet HashSet LinkedHashSet기반 자료구조Red-Black Tree (이진 탐색 트리)Hash TableHash Table + Linked List정렬 여부✅ 자동 정렬 (오름차순)❌ 없음❌ 없음삽입 순서 유지❌ 유지되지 않음❌ 유지되지 않음✅ 유지됨중복 허용❌❌❌null 허용❌ (예외 발생)✅ 하나 가능✅ 하나 가능시간 복잡도 (삽입/삭제/탐색)O(log n)O(1) 평균O(1) 평균부분 집합(subSet), 범위 검색✅ 지원❌❌Iterator 순회 순서정렬 순예측 불가삽입 순서 유지사용 추천 상황정렬/범위 탐색이 필요한 경우빠른 삽입/탐색이 필요한 경우순서를 기억하면서 빠른 성능이 필요한 경우상황별 추천정렬된 ..

LinkedHashSetLinkedHashSet은 Java의 Set 구현체로, HashSet의 성능에 입력 순서 유지 기능을 추가한 순서 있는 집합입니다.내부적으로 HashMap + Doubly Linked List 구조를 사용하여 요소의 순서를 기억합니다.주요 특징자료구조HashMap + 이중 연결 리스트정렬 여부✅ 입력 순서 유지중복 허용❌ (Set의 기본 특성)null 허용✅ (단 하나만 허용)시간 복잡도add, remove, contains 평균 O(1)차이점HashSet보다 약간 느리지만 순서를 기억함대표 메서드package structure.set.linkedhashset;import java.util.LinkedHashSet;public class LinkedHashSetClass { ..

HashSetHashSet은 Java에서 제공하는 Set 인터페이스의 구현체로, 중복을 허용하지 않고, 저장된 순서를 유지하지 않으며,빠른 검색/추가/삭제 성능을 갖춘 자료구조입니다. 주요 특징자료구조내부적으로 HashMap 기반정렬 여부❌ (저장 순서 보장 X)중복 허용❌ (Set의 기본 특성)null 허용✅ (단 하나의 null 값만 허용)시간 복잡도대부분의 연산은 평균 O(1)대표 메서드package structure.set.hashset;import java.util.HashSet;public class HashSetClass { private final HashSet hashSet; public HashSetClass(HashSet hashSet) { this.hashSe..

알고리즘에 자주 사용되는 자료구조를 정리를 한 지 며칠이 지나지 않았는데 벌써 Set 자료구조입니다. Set 자료구조 다음으로는 Map 자료구조로 마무리를 맺을 예정입니다. 이 후에는 번외로 자주 사용되는 메소드에 대해서 정리를 할 계획입니다.TreeSetTreeSet은 Java에서 제공하는 정렬된 집합(Set) 입니다.내부적으로 이진 탐색 트리(Red-Black Tree) 기반으로 구현되어 있으며, 자동으로 정렬된 상태를 유지하며 중복을 허용하지 않습니다. 주요 특징자료구조이진 탐색 트리 기반 (Red-Black Tree)정렬 순서기본은 오름차순, Comparator 지정 가능중복 허용❌ 중복된 값 저장 불가null 허용❌ (비교 불가능하므로 NullPointerException 발생)검색/삽입/삭제O..