본문 바로가기

자바 자료구조25

[묘공단] 깊이 우선 탐색(DFS) 코테를 풀다 보면 깊이우선탐색, 너비우선탐색을 자주 볼 수 있다.해당 알고리즘은 무엇일까? DFS, BFS는 트리를 순회하는 방법이다. 1. 트리라고 하면 아래와 같은 그림을 바로 떠올릴 수 있다. 그럼 아래와 같은 구조를 바탕으로 풀어야 하는 문제 유형은 무엇이 있을까?트리 문제는 주로 트리 순회, 이진 탐색 트리(BTS) 연산, 균형 트리, 특수 트리, 그리고 트리의 경로와 거리 계산으로 나뉜다.모든 걸 다 보면 좋을 것이고, 앞으로 다 살펴볼 것이지만 이번 시간에는 트리 순회 문제에 대해서만 다룬다.트리 순회 문제는 DFS, BFS를 이용해 특정 노드를 찾거나 순서를 출력하는 식이다.기억하자. 트리를 순회해야 된다? -> DFS나 BFS로 푼다. * 참고 *이진 탐색 트리 연산 문제는 삽입, 삭제,.. 2024. 5. 19.
부록: 자바에서 자료구조랑 연관 있는 인터페이스들 나는 자바로 코테를 풀기 위해 반드시 알아야 하는 기본적인 인터페이스와 클래스만 언급했다.내가 말하지 않은 것들이 몇몇 있다.나중에 그것에 대해 또 언급할 기회가 있을지 없을지 모르기 때문에 필요하면 혼자서 더 공부하길 바라는 마음에서여기에 관련 인터페이스를 언급한다.주요 컬렉션 인터페이스Collection: 모든 컬렉션 클래스의 기본 인터페이스.List: 순서가 있는 컬렉션을 다루기 위한 인터페이스. 중복을 허용합니다.Set: 중복을 허용하지 않는 컬렉션을 다루기 위한 인터페이스.SortedSet: 정렬된 순서로 요소를 저장하는 세트.NavigableSet: SortedSet을 확장하여 탐색 가능한 기능을 제공합니다.Queue: 특정 순서로 요소를 처리하기 위한 컬렉션 인터페이스 (보통 FIFO).De.. 2024. 4. 28.
자바 자료구조 총 정리를 마치며 1. 미흡하다. 하지만 쓸모 없지 않다.설명이 부족한 부분도 있고 빼 먹은 메서드도 좀 될 거 같다.하지만 절대 정리해 놓은 게 쓸모 없다고 생각하지 않는다.왜냐면, 저 정도 알면 머릿속에 웬만큼 자바 자료구조 정리는 다 되기 때문이다. 2. 완벽은 없다.내가 개발을 자바로 시작하지 않은 이유는 자바 생태계가 너~무 방대해서 어디서부터 어떻게 시작할지를 모르겠어서였다.그랬던 게 어떻게 된 일인지 지금 이러고 있는데 중요한 건,완벽은 없다.한낱 개인의 블로그에서 글 몇 개 읽고 '자바 자료구조의 모든 것'을 알아갈 순 없다.다만, 모든 글을 읽었다면 geeksforgeeks 등지에서 필요한 부분을 쏙 쏙 빠르게 잘 써먹게는 될 것이다.자바 자료구조에서 언급된 내용 중 더 자세하고 세밀하게 알고 싶은 부분이.. 2024. 4. 28.
자바 - TreeSet으로 코테 푸는 법 마지막 문제다... TreeSet은 Java에서 SortedSet 인터페이스를 구현하는 자료구조로, 내부적으로 레드-블랙 트리를 사용하여 요소를 자동으로 정렬합니다. TreeSet의 주요 특징은 데이터가 정렬된 상태로 유지되며, 이를 통해 순서에 의존적인 다양한 문제들을 효율적으로 해결할 수 있다는 점입니다.TreeSet을 사용해야 하는 문제 유형정렬된 데이터 유지: 입력 데이터의 순서를 자동으로 정렬해야 하는 경우.집합 연산: 정렬된 상태로 빠른 집합 연산(교집합, 합집합, 차집합 등)을 수행해야 할 때.범위 탐색: 특정 범위 내의 데이터를 빠르게 조회하거나 처리해야 할 때.가장 좋은 문제와 솔루션 예제문제: 데이터 스트림의 중간값 찾기문제 설명: 연속적으로 입력되는 데이터 스트림에서 각 단계별로 중간.. 2024. 4. 28.
자바 - LinkedHashSet으로 코테 푸는 법 문제 2개만 더 풀면 끝이다, 힘내자!!!💖 LinkedHashSet은 HashSet의 순서 보장 기능을 확장한 Java 컬렉션입니다. LinkedHashSet은 요소가 추가된 순서를 유지하면서 HashSet의 모든 특성(빠른 접근 시간, 중복 허용 안 함 등)을 유지합니다. 이 특성 때문에 LinkedHashSet은 순서가 중요하거나 데이터 삽입 순서를 기록해야 할 때 유용하게 사용될 수 있습니다.LinkedHashSet을 사용해야 하는 문제 유형순서를 유지해야 하는 중복 제거: 입력 순서대로 요소를 저장하면서 중복을 허용하지 않아야 할 때.순서가 중요한 데이터 집합 연산: 집합 연산을 수행하면서 요소의 입력 순서를 유지해야 하는 경우.최근 사용 데이터 추적: 최근에 추가된 요소를 추적하면서 중복 입.. 2024. 4. 28.
자바 - HashSet으로 코테 푸는 법 코딩 테스트에서 Set과 특히 HashSet을 사용하는 경우와 대표적인 유형들을 자세히 살펴보겠습니다. Set은 중복을 허용하지 않는 자료구조이며, HashSet은 이 중에서도 해시 테이블을 기반으로 구현되어 있어 특히 조회, 추가, 삭제 작업에서 빠른 성능을 제공합니다.1. 코테에서 Set을 사용해야 하는 경우Set은 주로 다음과 같은 상황에서 유용합니다:중복 제거: 데이터 컬렉션에서 중복된 요소를 제거해야 할 때.존재 여부 확인: 특정 요소가 데이터 컬렉션 내에 존재하는지 빠르게 확인할 때.집합 연산: 다른 컬렉션과의 합집합, 교집합, 차집합을 구할 때.2. 대표적인 Set 써야 하는 유형유일한 요소 찾기: 배열이나 리스트에서 모든 중복을 제거하고 유일한 요소만을 유지해야 하는 문제.공통 요소 탐색:.. 2024. 4. 28.
자바 - Set 이야기 Set이 뭐 별 거 있나.중복 안 돼야 되면 셋 쓰는 거지... Java에서 Set은 컬렉션 프레임워크의 인터페이스 중 하나로, 중복을 허용하지 않는 데이터의 집합을 관리하는 데 사용됩니다. Set 인터페이스는 Collection 인터페이스를 확장하며, 요소의 순서를 보장하지 않는 특성이 있습니다. Set은 값의 존재 유무를 체크하거나, 중복을 제거하는 등의 작업에서 유용하게 사용됩니다.Java에서 사용할 수 있는 주요 Set 구현체HashSet가장 많이 사용되는 Set 구현체입니다.내부적으로 HashMap을 사용하여 요소를 저장합니다.요소의 추가, 삭제, 조회 작업의 시간 복잡도는 평균적으로 O(1)입니다.요소의 순서를 유지하지 않으며, null 값도 저장할 수 있습니다.LinkedHashSetHash.. 2024. 4. 28.
자바 - ArrayDeque으로 코테 푸는 법 😉 시작해볼까?! ArrayDeque는 Java의 Deque 인터페이스를 구현한 배열 기반의 더블 엔디드 큐(double-ended queue)입니다. LinkedList와 함께 자바에서 가장 일반적으로 사용되는 덱 구현체 중 하나로, 양쪽 끝에서 요소를 효율적으로 추가하거나 제거할 수 있는 구조입니다. ArrayDeque는 스택이나 큐의 기능을 모두 구현할 수 있어 매우 유연하며, 특히 메모리 사용과 성능 측면에서 많은 장점을 제공합니다.ArrayDeque의 주요 특징높은 효율성: ArrayDeque는 내부적으로 동적 배열을 사용하여 요소를 저장합니다. 배열을 사용하기 때문에 메모리 할당이 연속적이며, 요소에 대한 빠른 임의 접근이 가능합니다.용량 제한 없음: ArrayDeque는 초기 용량을 설정할.. 2024. 4. 28.
자바 - Deque의 LinkedList로 코테 푸는 법 LinkedList는 List, Queue, Deque을 다 implements 한다.다른 인터페이스로 구현된 LinkedList는 다른 글에서 볼 수 있고여기서는 Deque으로 구현된 것만 확인한다. 그 전에...Deque의 LinkedList를 사용해야 하는 문제 유형Deque의 LinkedList 구현은 특히 다음과 같은 유형의 문제 해결에 적합합니다:양방향 큐 구현: 문제가 데이터의 양 끝에서 추가 및 삭제를 자주 요구할 때, 예를 들어 스택이나 큐의 기능이 결합된 형태가 필요한 경우.양방향 순회가 필요한 경우: 데이터를 앞뒤로 자유롭게 탐색해야 할 때 유리합니다.실시간 계산 문제: 데이터의 앞부분이나 뒷부분에서 요소를 추가하거나 제거하면서 실시간으로 최대값, 최소값 등을 계산해야 하는 문제.슬라.. 2024. 4. 28.
자바 - Deque 이야기 자바에서 쓸 수 있는 자료구조 클래스에 대한 이야기가 거의 끝을 향해 가고 있다.덱하고 셋만 하면 끝이다!힘을 내어 빨리 끝을 내 보자! Java에서 Deque 인터페이스는 "double ended queue"의 약자로, 양쪽 끝에서 요소를 추가하거나 제거할 수 있는 선형 컬렉션입니다. 이는 스택(stack)과 큐(queue)의 일반화된 형태로 볼 수 있으며, FIFO(First-In-First-Out) 및 LIFO(Last-In-First-Out) 양쪽의 동작을 모두 지원합니다. 다른 포스트에서 여러 번 나왔지만 한 번 더 넣었다. 덱에 대해 더 딥하게 알아야 할 내용이 있나...?LinkedList 같은 경우는 진짜 머리 빠게지게까지 볼 수 있는데 덱에서는 그러지 말자... 호호호... 😃...De.. 2024. 4. 27.
자바 - PriorityQueue로 코테 푸는 법 두둥 😄 두둥 🥹 지나친 학습으로 인해 미쳐 가고 있다. 🤪 1. 그래서, 언제 PriorityQueue를 써야 되나요? 프라이어리티 큐(Priority Queue)는 특정 기준에 따라 우선 순위를 부여하여 가장 우선 순위가 높은 요소를 먼저 처리하는 자료구조입니다. 코딩 테스트에서 다음과 같은 유형의 문제를 해결할 때 프라이어리티 큐를 유용하게 사용할 수 있습니다:최소 또는 최대 요소 찾기: 요소들 중 최소값 또는 최대값을 빠르게 찾아내야 할 때, 특히 반복적으로 최소값 또는 최대값을 추출해야 하는 경우에 프라이어리티 큐를 사용합니다. 다익스트라 알고리즘: 최단 경로를 찾는 알고리즘 중 하나로, 각 정점까지의 최단 거리를 계산할 때 우선 순위 큐를 사용하여 현재 가장 짧은 거리를 가진 정점을 빠르.. 2024. 4. 27.
자바 - PriorityQueue 이야기 지난 글쓰기를 보니 내가 List 인터페이스에 대해서는 설명을 그다지 많이 하지 않았는데Queue에 대해서 이야기를 많이 했더니 PriorityQueue에 대해 제대로 설명하지 않았다.프라이어리티큐는 이런 느낌이다. PriorityQueue는 Java에서 제공하는 표준 라이브러리 중 하나로, 자동으로 요소들이 우선 순위에 따라 정렬되는 큐 구현체입니다. 이 구현체는 내부적으로 힙(heap) 자료구조, 특히 최소 힙(min-heap)을 사용하여 요소들을 관리합니다. 이는 각 요소가 추가될 때마다 자동으로 정렬되어, 가장 낮은(또는 가장 높은, 정렬 기준에 따라 다름) 요소가 큐의 맨 앞에 위치하게 됩니다.PriorityQueue의 주요 특징자동 정렬: 요소가 추가될 때마다 자동으로 정렬이 이루어지며, 이는.. 2024. 4. 27.

티스토리툴바