자바 알고리즘 연습 - 자료구조 정리

Об этом предложении

Java 주요 자료구조 총정리 1. 자료구조 한눈에 비교 자료구조 핵심 특징 주요 활용 Array 고정 크기, 빠른 인덱스 접근 고정된 데이터, 인덱스 기반 처리 ArrayList 크기 변경 가능한 동적 배열 데이터 저장, 조회, 정렬 LinkedList 노드 연결 기반 리스트 양 끝 삽입·삭제 Stack LIFO (후입선출) DFS, 괄호 검사, Undo Queue FIFO (선입선출) BFS, 대기열, 작업 처리 Deque 양쪽 끝 삽입·삭제 Stack·Queue 대체, 슬라이딩 윈도우 PriorityQueue 우선순위에 따라 데이터 추출 다익스트라, 최솟값·최댓값 HashSet 중복 불허, 빠른 검색 중복 제거, 존재 여부 확인 LinkedHashSet 중복 불허, 삽입 순서 유지 순서 유지하며 중복 제거 TreeSet 중복 불허, 정렬 유지 정렬된 고유 데이터, 범위 검색 HashMap Key-Value 저장 빈도 계산, 빠른 Key 조회 LinkedHashMap Key-Value, 순서 유지 순서가 중요한 데이터 관리 TreeMap Key 기준 정렬 정렬된 Key, 범위 검색 2. 선형 자료구조 2.1 Array (배열) 특징 크기가 고정되어 있음 인덱스를 통한 접근 O(1) 중간 삽입·삭제 시 요소 이동 필요 기본형( int , double )과 참조형 모두 저장 가능 사용 시점 데이터 개수가 정해져 있을 때 인덱스 접근이 빈번할 때 메모리 효율이 중요할 때 코딩테스트에서 고정 크기의 데이터를 처리할 때 int[] arr = {10, 20, 30}; int value = arr[0]; // 10 arr[1] = 50; // 요소 수정 int length = arr.length; 2.2 ArrayList (동적 배열) 특징 크기 자동 확장 인덱스 접근 O(1) 끝에 추가 시 평균 O(1) 중간 삽입·삭제 O(n) 기본형을 직접 저장할 수 없어 Wrapper 클래스 사용 사용 시점 데이터 개수가 유동적일 때 인덱스로 자주 조회할 때 정렬이 필요할 때 일반적인 리스트 자료구조가 필요할 때 List<Integer> list = new ArrayList<>(); list.add(10); list.add(20); list.add(30); list.get(0); // 10 list.set(0, 50); // 수정 list.remove(0); // 삭제 list.size(); // 크기 Collections.sort(list); // 오름차순 정렬 2.3 LinkedList (연결 리스트) 특징 각 노드가 이전·다음 노드를 참조하는 이중 연결 리스트 인덱스 접근 O(n) 양 끝 삽입·삭제 O(1) 중간 노드를 찾는 과정은 O(n) 노드 연결 정보로 추가 메모리 사용 사용 시점 양 끝 삽입·삭제가 빈번할 때 노드 위치를 이미 알고 있는 상태에서 삽입·삭제할 때 일반적인 데이터 저장·조회는 ArrayList가 유리한 경우가 많음 LinkedList<Integer> list = new LinkedList<>(); list.addFirst(10); list.addLast(20); list.getFirst(); list.getLast(); list.removeFirst(); list.removeLast(); 3. Stack / Queue / Deque 3.1 Stack — LIFO (Last In First Out) 후입선출: 나중에 들어온 데이터가 먼저 나감 사용 시점 DFS (깊이 우선 탐색) 괄호 짝 검사 실행 취소(Undo) 뒤로 가기 재귀 호출 구조를 반복문으로 구현 오큰수, 단조 스택 문제 Java 구현 기존 Stack 클래스보다 ArrayDeque 사용을 권장합니다. Deque<Integer> stack = new ArrayDeque<>(); stack.push(10); stack.push(20); stack.push(30); stack.peek(); // 30 (조회) stack.pop(); // 30 (제거) stack.pop(); // 20 메서드 기능 시간 복잡도 push() 맨 위에 추가 평균 O(1) pop() 맨 위 제거 및 반환 O(1) peek() 맨 위 조회 O(1) 3.2 Queue — FIFO (First In First Out) 선입선출: 먼저 들어온 데이터가 먼저 나감 사용 시점 BFS (너비 우선 탐색) 미로 최단 거리 탐색 (동일 가중치) 주문·요청 대기열 작업 스케줄링 프린터 대기열 순차적인 이벤트 처리 Java 구현 Queue<Integer> queue = new ArrayDeque<>(); queue.offer(10); queue.offer(20); queue.offer(30); queue.peek(); // 10 (조회) queue.poll(); // 10 (제거) queue.poll(); // 20 메서드 기능 시간 복잡도 offer() 뒤에 추가 평균 O(1) poll() 앞에서 제거 및 반환 O(1) peek() 맨 앞 조회 O(1) 주의 poll() / peek() : 비어 있으면 null 반환 remove() / element() : 비어 있으면 예외 발생 3.3 Deque — Double Ended Queue 양방향 큐: 앞과 뒤에서 모두 삽입·삭제 가능 Stack과 Queue의 기능을 모두 수행할 수 있습니다. 사용 시점 Stack과 Queue 기능을 함께 사용 슬라이딩 윈도우 최댓값·최솟값 양쪽에서 데이터를 제거하는 문제 회전하는 큐 팰린드롬 검사 0-1 BFS Java 구현 Deque<Integer> deque = new ArrayDeque<>(); deque.offerFirst(10); // 앞에 추가 deque.offerLast(20); // 뒤에 추가 deque.offerFirst(5); deque.peekFirst(); // 5 deque.peekLast(); // 20 deque.pollFirst(); // 5 deque.pollLast(); // 20 메서드 기능 offerFirst() 앞에 추가 offerLast() 뒤에 추가 pollFirst() 앞에서 제거 pollLast() 뒤에서 제거 peekFirst() 앞의 요소 조회 peekLast() 뒤의 요소 조회 양 끝 작업은 평균 O(1)이며, ArrayDeque 는 중간 인덱스 접근용 자료구조가 아닙니다. 3.4 PriorityQueue — 우선순위 큐 삽입 순서와 관계없이 우선순위가 높은 데이터부터 제거 기본적으로 최소 힙(Min Heap) offer() , poll() O(log n) peek() O(1) 전체 데이터가 정렬된 상태는 아님 사용 시점 다익스트라 최단 경로 알고리즘 가장 작은 값 또는 큰 값 반복 추출 우선순위 기반 작업 처리 상위 K개 데이터 유지 여러 정렬된 데이터 병합 최소 힙 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.offer(30); pq.offer(10); pq.offer(20); pq.poll(); // 10 pq.poll(); // 20 pq.poll(); // 30 최대 힙 PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); pq.offer(30); pq.offer(10); pq.offer(20); pq.poll(); // 30 pq.poll(); // 20 pq.poll(); // 10 4. Set 계열 — 중복 없는 데이터 4.1 HashSet 특징 중복 허용하지 않음 순서 보장하지 않음 삽입·검색·삭제 평균 O(1) 사용 시점 중복 데이터 제거 특정 값의 존재 여부 검사 이미 방문한 노드 관리 고유한 ID 관리 Set<Integer> set = new HashSet<>(); set.add(10); set.add(20); set.add(10); // 중복 무시 set.contains(20); // true set.remove(10); 4.2 LinkedHashSet 특징 HashSet과 동일하게 중복 제거 삽입 순서 유지 주요 연산 평균 O(1) 사용 시점 원래 입력 순서를 유지하면서 중복 제거 Set<Integer> set = new LinkedHashSet<>(); set.add(30); set.add(10); set.add(20); set.add(10); // 순회 순서: 30, 10, 20 4.3 TreeSet 특징 중복 제거 정렬된 순서 유지 삽입·검색·삭제 O(log n) 기본적으로 오름차순 정렬 사용 시점 중복 제거와 정렬이 동시에 필요 특정 값 이상·이하의 값 검색 범위 기반 데이터 처리 TreeSet<Integer> set = new TreeSet<>(); set.add(30); set.add(10); set.add(20); set.first(); // 10 set.last(); // 30 set.ceiling(15); // 20 (15 이상 최소) set.floor(15); // 10 (15 이하 최대) set.higher(20); // 30 (20 초과 최소) set.lower(20); // 10 (20 미만 최대) 5. Map 계열 — Key-Value 데이터 5.1 HashMap 특징 Key-Value 형태 저장 Key 중복 불가능 (기존 값 덮어쓰기) Key를 통한 검색 평균 O(1) 순서 보장하지 않음 사용 시점 문자열·숫자 빈도 계산 ID로 객체 검색 데이터 간 매핑 Two Sum 등의 해시 기반 문제 그룹별 데이터 집계 Map<String, Integer> map = new HashMap<>(); map.put("apple", 3); map.put("banana", 5); map.get("apple"); // 3 map.getOrDefault("grape", 0); // 0 map.containsKey("apple"); // true map.remove("banana"); 빈도 계산 예시 String[] arr = {"A", "B", "A", "C", "B", "A"}; Map<String, Integer> count = new HashMap<>(); for (String s : arr) { count.put(s, count.getOrDefault(s, 0) + 1); } // A=3, B=2, C=1 5.2 LinkedHashMap 특징 Key-Value 저장 기본적으로 삽입 순서 유지 주요 연산 평균 O(1) 사용 시점 데이터 삽입 순서 유지 순서가 중요한 결과 출력 접근 순서 모드를 이용한 LRU 캐시 구현 Map<String, Integer> map = new LinkedHashMap<>(); map.put("B", 2); map.put("A", 1); map.put("C", 3); // 순회 순서: B → A → C 5.3 TreeMap 특징 Key 기준 자동 정렬 삽입·검색·삭제 O(log n) 범위 검색 지원 사용 시점 정렬된 Key 관리 특정 Key 이상·이하 검색 날짜·점수 등의 범위 검색 TreeMap<Integer, String> map = new TreeMap<>(); map.put(30, "C"); map.put(10, "A"); map.put(20, "B"); map.firstKey(); // 10 map.lastKey(); // 30 map.ceilingKey(15); // 20 map.floorKey(15); // 10 6. 주요 자료구조 시간 복잡도 자료구조 접근·조회 검색 삽입 삭제 Array O(1) O(n) O(n) O(n) ArrayList O(1) O(n) 끝 평균 O(1) 중간 O(n) LinkedList O(n) O(n) 양 끝 O(1) 양 끝 O(1) Stack (ArrayDeque) Top O(1) O(n) 평균 O(1) O(1) Queue (ArrayDeque) Front O(1) O(n) 평균 O(1) O(1) Deque (ArrayDeque) 양 끝 O(1) O(n) 양 끝 평균 O(1) 양 끝 O(1) PriorityQueue Top O(1) O(n) O(log n) Poll O(log n) HashSet — 평균 O(1) 평균 O(1) 평균 O(1) LinkedHashSet — 평균 O(1) 평균 O(1) 평균 O(1) TreeSet — O(log n) O(log n) O(log n) HashMap Key 평균 O(1) Key 평균 O(1) 평균 O(1) 평균 O(1) LinkedHashMap Key 평균 O(1) Key 평균 O(1) 평균 O(1) 평균 O(1) TreeMap Key O(log n) Key O(log n) O(log n) O(log n) ※ 배열은 중간 삽입·삭제로 인한 요소 이동 기준입니다. LinkedList는 양 끝 연산 기준이며, Hash 기반 자료구조는 충돌이 심한 경우 성능이 저하될 수 있습니다. 7. 자료구조 간 변환 Array ↔ List // int[] → List<Integer> List<Integer> list = Arrays.stream(arr).boxed().toList(); // Integer[] → List<Integer> List<Integer> list2 = Arrays.asList(integerArr); // List<Integer> → int[] int[] arr2 = list.stream().mapToInt(Integer::intValue).toArray(); // List<Integer> → Integer[] Integer[] arr3 = list.toArray(new Integer[0]); List ↔ Set // List → Set (중복 제거) Set<Integer> set = new HashSet<>(list); // List → LinkedHashSet (순서 유지) Set<Integer> ordered = new LinkedHashSet<>(list); // List → TreeSet (중복 제거 + 정렬) Set<Integer> sorted = new TreeSet<>(list); // Set → List List<Integer> result = new ArrayList<>(set); List ↔ Queue / Deque // List → Queue Queue<Integer> queue = new ArrayDeque<>(list); // List → Deque Deque<Integer> deque = new ArrayDeque<>(list); // Queue → List List<Integer> list2 = new ArrayList<>(queue); // Deque → List List<Integer> list3 = new ArrayList<>(deque); List ↔ PriorityQueue // List → PriorityQueue PriorityQueue<Integer> pq = new PriorityQueue<>(list); // PriorityQueue → 정렬된 List List<Integer> sorted = new ArrayList<>(); while (!pq.isEmpty()) { sorted.add(pq.poll()); } ※ 마지막 예시는 원본 PriorityQueue의 요소를 모두 제거합니다. 8. 상황별 자료구조 선택 기준 문제 상황 추천 자료구조 데이터 개수가 고정됨 Array 데이터 개수가 유동적임 ArrayList 인덱스로 자주 접근함 Array / ArrayList 가장 최근 데이터를 먼저 처리 Stack (ArrayDeque) 먼저 들어온 데이터를 먼저 처리 Queue (ArrayDeque) 앞뒤에서 삽입·삭제 Deque (ArrayDeque) 최솟값·최댓값을 반복해서 추출 PriorityQueue 중복 데이터 제거 HashSet 순서 유지하면서 중복 제거 LinkedHashSet 정렬하면서 중복 제거 TreeSet 데이터 존재 여부를 빠르게 검사 HashSet Key로 값을 빠르게 조회 HashMap Key를 정렬된 상태로 관리 TreeMap 문자열·숫자 빈도 계산 HashMap DFS Stack / 재귀 BFS Queue 다익스트라 알고리즘 PriorityQueue 슬라이딩 윈도우 최댓값·최솟값 Deque 방문 여부 확인 boolean[] / HashSet 상위 K개 값 관리 PriorityQueue 9. 핵심 암기 포인트 자료구조 선택 기준 Array : 크기가 고정되어 있고 인덱스 접근이 중요할 때 ArrayList : 일반적인 동적 데이터 저장·조회 LinkedList : 양 끝 삽입·삭제가 중요할 때 Stack : 최근에 들어온 데이터를 먼저 처리 (LIFO) Queue : 먼저 들어온 데이터를 먼저 처리 (FIFO) Deque : 양쪽 끝에서 데이터를 처리 PriorityQueue : 우선순위가 높은 데이터를 먼저 처리 HashSet : 중복 제거, 빠른 존재 여부 검사 TreeSet : 중복 제거 + 정렬 HashMap : Key-Value 저장, 빈도 계산 TreeMap : Key 정렬 및 범위 검색 Java에서 기억할 구현체 // 일반적인 리스트 List<Integer> list = new ArrayList<>(); // Stack Deque<Integer> stack = new ArrayDeque<>(); // Queue Queue<Integer> queue = new ArrayDeque<>(); // Deque Deque<Integer> deque = new ArrayDeque<>(); // 최소 힙 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 최대 힙 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // 중복 제거 Set<Integer> set = new HashSet<>(); // 정렬된 Set TreeSet<Integer> treeSet = new TreeSet<>(); // Key-Value Map<String, Integer> map = new HashMap<>(); // Key 정렬 TreeMap<Integer, String> treeMap = new TreeMap<>(); 결론: 자료구조를 선택할 때는 데이터의 저장 형태뿐 아니라 접근 순서, 중복 허용 여부, 정렬 필요성, 삽입·삭제 빈도, 시간 복잡도 를 함께 고려해야 합니다.