Notice

Recent Posts

Recent Comments

Link

« 2025/12 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

whdudev

코딩테스트를 위한 자료구조 본문

코딩테스트

코딩테스트를 위한 자료구조

whdudev 2025. 11. 16. 22:42

본격적으로 코딩테스트 준비하기 앞서 간단하게 필수 자료구조의 개념에 대해 정리하고자 한다.

필요시에 추후에 내용을 보완 할 것이다.

1. 배열 (Array)

https://velog.io/@3rd-big/JAVA-%EB%B0%B0%EC%97%B4Array

1.1 배열의 특징

배열은 하나의 연속된 메모리 공간에 여러 개의 데이터를 같은 타입으로 저장할 수 있는 자료구조이다.

인덱스를 통해 데이터에 빠르게 접근 가능

1.2 배열 선언과 초기화 (Java) 및 사용

배열 선언을 해도 따로 초기화 해줘야한다.

int[] arr = new int[5];   // 기본값: 0
String[] names = new String[3]; // 기본값: null

배열 사용하기

배열을 다루는 API Arrays를 궁금하면 더 찾아보자~!

// 정렬 

import java.util.Arrays;

public class ArraySortExample {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 1, 2};

        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8]
    }
}

1.3 시간 복잡도

배열은 인덱스 기반 접근 덕분에 시간 복잡도 측면에서 매우 효율적이다.

단점은 삽입/삭제가 느리다.

	연산시간	복잡도설명
접근 (Access)	O(1)	인덱스로 바로 접근 가능
검색 (Search)	O(n)	전체 탐색 필요
삽입 (Insert)	O(n)	중간 삽입 시 요소 이동 필요
삭제 (Delete)	O(n)	중간 삭제 시 요소 이동 필요

1.4 배열의 한계

배열의 한계를 알아보자.

1. 크기 변경 불가능

한 번 정하면 크기 변경 불가능.

2. 삽입/ 삭제가 비효율적

중간에 데이터를 넣거나 빼려면 다른 요소들을 이동해야함.

3. 비어있는 공간 관리 필요

미리 크게 잡으면 메모리 낭비 발생

1.5 ArrayList 비교

🔹 ArrayList와의 비교

크기 변경가능한게 ArrayList의 큰 특징으로 기억하자.

항목	배열(Array)	ArrayList (동적 배열)
크기 변경	불가능	가능 (자동 확장)
삽입/삭제	느림 (O(n))	상대적으로 편함 (내부적으로 O(n))
접근 속도	O(1)	O(1)
타입 제한	같은 타입만 가능	제네릭 사용 가능
메모리	고정 크기	필요 시 자동 증가
사용 편의성	낮음	높음

2. 리스트(List) 구조

순서 O 중복 O

리스트(List)는 데이터를 순서 있게 저장하는 자료구조로 , 배열의 단점을 보완하거나 특정 상황에서 더 효율적인 접근을 제공한다.

자바에서는 대표적으로 ArrayList와 LinkedList가 있다.

https://velog.io/@adam2/Array%EC%99%80-List%EA%B7%B8%EB%A6%AC%EA%B3%A0-Java-List

2.1 ArrayList

내부 구조 (동적 배열)
ArrayList는 내부적으로 동적 배열(dynamic array) 을 사용한다.
일반 배열과 달리, 저장 공간이 부족해지면 자동으로 더 큰 배열을 새로 만들고 기존 데이터를 옮겨 담는다.
add/remove/get 시간 복잡도 (접근은 빠르고, 삽입·삭제는 느리다.)

연산	시간 복잡도	설명
get(index)	O(1)	배열 기반이라 즉시 접근
add(element)	평균 O(1)	확장 발생 시 O(n)
add(index, element)	O(n)	중간 삽입 → 요소 이동
remove(index)	O(n)	중간 삭제 → 요소 이동
contains(element)	O(n)	전체 탐색 필요

2.2 LinkedList

노드 구조
LinkedList는 배열 대신 노드(Node) 들이 서로 연결된 형태이다.
노드 구조 : data(실제 데이터), next(다음 노드 주소), prev(이전 노드주소)
삽입/삭제 강점
ArrayList와 달리 LinkedList 요소를 옮길 필요가 없고 next prev 가르키는 주소 값만 바꿔주면 되니까 삽입 삭제가 빠름~!
A <-> B
A <-> new <-> B
(참고 마지막 데이터 삭제, 삽입는 ArrayList도 빠르다. 이유 위치바꿔주는 작업이 필요 없으니까.)

2.3 ArrayList vs LinkedList 비교

인덱스로 저장된 데이터에 자주 접근할 때, 요소 수 안 바뀔 때, 정렬이나 순차 탐색이 많을 때 -> ArrayList 사용

중간에 데이터 삽입/ 삭제가 빈번할 때 -> LinkedList 사용 (사실 대부분 ArrayList + 필요시 Deque(ArrayDeque)를 사용한다.)

항목	ArrayList	LinkedList
저장 구조	동적 배열	이중 연결 리스트
접근 속도	O(1)	O(n)
중간 삽입/삭제	O(n)	O(1)
메모리 사용량	적음	많음(노드 + 포인터 필요)
데이터 연속성	연속된 메모리	불연속 메모리
일반적 사용 빈도	매우 높음	비교적 낮음
장점 요약	빠른 접근	빠른 삽입/삭제(특정 위치)
단점 요약	삽입/삭제 느림	접근 속도 느림

2.3 ArrayList, LinkedList 사용 예시

// ArrayList
List<String> products = new ArrayList<>();
products.add("Keyboard");
products.add("Mouse");

// 조회
String item = products.get(1); // 매우 빠름 (O(1))

// 정렬 
List<Integer> nums = new ArrayList<>(List.of(5,3,1,4,2));
Collections.sort(nums);

// Queue구현을 LinkedList가함 
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.poll(); // 첫 노드 삭제 → O(1)

// Deque도 구현함 
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(10);
deque.addLast(20);
deque.removeFirst(); // O(1)

// 중간 삽입 용이 
List<String> list = new LinkedList<>();
list.add("A");
list.add("C");
list.add(1, "B"); // 중간 삽입 → O(1) (노드만 알면)

3. 스택(Stack)

물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조, 꼴등부터 나간다.

3.1 LIFO 원리

마지막에 들어온 데이터가 가장 먼저 나감. (1,2,3,4 순서로 데이터가 들어오면 4부터 나간다. 꼴등부터 나간다.)

3.2 Stack 구현 (ArrayDeque 권장)

자바는 원래 Stack 클래스를 제공하지만,

오래된 Vector 기반 (synchronized, 느림)
사용 비추천
때문에 ArrayDeque로 스택을 구현하는 것이 표준적인 방식이다.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(10);    // push
stack.push(20);
stack.push(30);

int top = stack.pop();     // 30 (가장 마지막에 넣은 값)
int peek = stack.peek();   // top 조회 (삭제 X)

3.3 스택의 활용 사례 (괄호 검사, 브라우저 등)

괄호 검사

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {

        // 여는 괄호면 push
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        }
        // 닫는 괄호일 때만 검사
        else if (c == ')' || c == '}' || c == ']') {

            if (stack.isEmpty()) return false;
            char top = stack.pop();

            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
        // 그 외 문자는 무시
        else {
            continue;
        }
    }

    return stack.isEmpty();
}

웹 브라우저 뒤로가기/ 앞으로 가기

Deque<String> back = new ArrayDeque<>();
Deque<String> forward = new ArrayDeque<>();

back.push("page1");
back.push("page2");

String cur = back.pop(); // page2
forward.push(cur);       // 앞으로가기 스택에 저장

4. 큐(Queue) & 덱(Deque)

큐와 덱은 데이터를 순서대로 관리하는 자료구조로, 스택과 달리 먼저 들어온 데이터가 먼저 나가는 구조를 기본으로 한다.

1,2,3,4 들어오면 1부터 나간다. 1등이 1등으로 나간다.

4.1 큐의 FIFO

큐는 선입선출(FIFO) 구조를 따른다.

먼저 들어온 데이터가 가장 먼저 나감
push / pop과 달리, enqueue / dequeue로 표현되기도 함
스택과 비교하면: LIFO vs FIFO

4.2 Queue 구현 (LinkedList)

자바에서는 Queue 인터페이스를 구현하는 여러 클래스가 있지만,
LinkedList를 보통 사용하는 듯 하다.

import java.util.*;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // 데이터 추가
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println(queue); // [A, B, C]

        // 데이터 제거
        String first = queue.poll(); // A
        System.out.println(first);
        System.out.println(queue); // [B, C]

        // peek: 첫 요소 확인만
        System.out.println(queue.peek()); // B
    }
}

삽입: offer(E e) / add(E e)
삭제: poll() / remove()
조회: peek() / element()
중간 요소 접근 불가 → O(n)
FIFO 구조에 최적화

4.3 덱(Deque)

Deque(Double-Ended Queue)는 양쪽 끝에서 삽입/삭제가 가능한 큐이다.

Deque<Integer> deque = new ArrayDeque<>();

deque.addFirst(10);  // 앞에 추가
deque.addLast(20);   // 뒤에 추가

System.out.println(deque); // [10, 20]

deque.removeFirst(); // 10 삭제
deque.removeLast();  // 20 삭제

Stack처럼 사용 가능 → push() / pop()
Queue처럼 사용 가능 → offer() / poll()
양방향 모두 O(1)

4.4 ArrayDeque vs LinkedList

항목	ArrayDeque	LinkedList
내부 구조	배열 기반	이중 연결 리스트
접근 속도	빠름	느림 (노드 순차 탐색 필요)
삽입/삭제	O(1) 앞/뒤	O(1) 앞/뒤
메모리 사용	적음	많음 (노드 객체 + 포인터)
null 허용	X	O
동기화	없음	없음
추천 상황	일반적인 큐/덱	특별히 연결 구조 필요할 때

💡 결론:

대부분 실무에서는 ArrayDeque가 성능과 메모리 측면에서 더 좋음
LinkedList는 특수한 경우만 사용

4.5 BFS에서의 활용

import java.util.*;

public class BFSExample2 {

    public static void bfs(String start, Map<String, List<String>> graph) {
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> distance = new HashMap<>(); // 시작점으로부터 거리 저장

        queue.offer(start);
        distance.put(start, 0); // 시작점 거리 0

        while (!queue.isEmpty()) {
            String node = queue.poll();
            int dist = distance.get(node);

            System.out.println("Node: " + node + ", Distance from " + start + ": " + dist);

            for (String neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!distance.containsKey(neighbor)) { // 방문 체크
                    queue.offer(neighbor);
                    distance.put(neighbor, dist + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();

        // 그래프 생성
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));

        bfs("A", graph);
    }
}

5. 해시(Hash) 구조

해시는 데이터를 Key를 기반으로 빠르게 접근할 수 있게 만드는 자료구조이다.

https://velog.io/@adam2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

5.1 해시 함수의 개념

Key → 해시 함수 → 해시 값(index)
데이터를 배열처럼 O(1) 접근 가능하게 매핑
해시 충돌: 서로 다른 Key가 같은 해시 값 → 충돌 처리 필요
Key를 통해 바로 값을 찾아올 수 있음 → 검색, 삽입, 삭제 O(1) 평균
충돌이 발생하면 Linked List, Tree 등으로 처리

5.2 HashMap

Key-Value 저장 구조
key - value 쌍으로 저장, key는 유일, value 중복 가능
충돌 처리 방식
자바 HashMap은 체이닝(Linked List + JDK8부터는 Tree로 변환) 방식
충돌 발생 시 동일 해시 버킷에 노드 연결 → 평균 O(1), 최악 O(n)(해시값 같은 경우 )
활용 예시

// 중복체크 
int[] nums = {1,2,3,2,1};
Map<Integer, Boolean> map = new HashMap<>();

for(int num : nums) {
    if(map.containsKey(num)) {
        System.out.println("중복: " + num);
    } else {
        map.put(num, true);
    }
}

//빈도 계산 
String str = "aabbccaa";
Map<Character, Integer> count = new HashMap<>();
for(char c : str.toCharArray()) {
    count.put(c, count.getOrDefault(c, 0) + 1);
}
System.out.println(count); // {a=4, b=2, c=2}

5.3 HashSet

중복 없는 데이터 저장
내부적으로 HashMap을 기반으로 Key만 저장

// 중복이 없음 
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(2); // 중복 무시

System.out.println(set); // [1, 2]

System.out.println(set.contains(1)); // true
set.remove(1);

Set<Integer> a = new HashSet<>(Arrays.asList(1,2,3));
Set<Integer> b = new HashSet<>(Arrays.asList(2,3,4));
a.retainAll(b); // 교집합
System.out.println(a); // [2,3]

5.4 해시의 장점 (O(1) 평균)

연산	해시	배열/ 리스트
삽입	O(1)	O(1)
검색	O(1)	O(n)
삭제	O(1)	O(n)

Map과 Set을 활용하면 대부분의 중복/빈도/조회 문제를 O(n)으로 해결 가능
문자열, 숫자, 객체 Key 모두 가능 → hashCode()와 equals() 중요
JDK8 이후 충돌이 많으면 LinkedList → Tree로 변환되어 최악 상황 대비

6. 우선순위 큐(PriorityQueue) & 힙(Heap)

우선순위 큐(PriorityQueue) = 힙을 활용해서 만든 추상 자료구조

힙 = 정렬되지 않은 완전 이진 트리지만, 루트가 항상 최소/최대인 구조

힙은 완전이진트리를 기반으로 한 자료구조로, 항상 최대값 혹은 최소값을 빠르게 접근할 수 있도록 설계되어 있다.

6.1 힙의 개념 (완전이진트리)

완전 이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든 레벨이 꽉 차 있음
마지막 레벨은 왼쪽부터 채움
최대 힙(Max Heap) → 부모 노드 ≥ 자식 노드
최소 힙(Min Heap) → 부모 노드 ≤ 자식 노드

6.2 최소/최대 힙

최소 힙: PriorityQueue 기본값 → 가장 작은 값이 top
최대 힙: Comparator를 사용하여 구현 → 가장 큰 값이 top

// 최소 힙
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
minHeap.add(3);
System.out.println(minHeap.poll()); // 1

// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(3);
System.out.println(maxHeap.poll()); // 5

6.3 PriorityQueue 사용법

메서드	설명
add(E e) / offer(E e)	요소 삽입
poll()	최우선 요소 제거 후 반환
peek()	최우선 요소 확인 (삭제 X)
size()	요소 개수
isEmpty()	비었는지 확인

힙을 이용한 정렬

PriorityQueue<Integer> heap = new PriorityQueue<>();
int[] nums = {5,3,8,1};
for(int n : nums) heap.offer(n);

while(!heap.isEmpty()) {
    System.out.print(heap.poll() + " "); // 1 3 5 8
}

//아이디어: 최소 힙 크기를 K로 유지 → K번째 큰 수가 루트에 남음

int[] nums = {3,2,1,5,6,4};
int k = 2;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) {
        minHeap.poll();
    }
}

System.out.println(minHeap.peek()); // 5

6.4 힙의 시간 복잡도

연산	시간 복잡도
삽입 (add/offer)	O(log n)
삭제 (poll)	O(log n)
최상위 요소 조회 (peek)	O(1)
heapify (배열 → 힙)	O(n)

ArrayList로 구현하는 PriorityQueue는 완전이진트리 + 배열 기반 → log n 유지

6.5 다익스트라에서의 활용

최단 경로 알고리즘 → 항상 현재 최단 거리 노드 선택이 핵심
PriorityQueue(최소 힙)를 사용하면 O(E log V)로 최적화 가능

다익스트라 알고리즘 코드

// Node 클래스: 그래프의 정점(vertex)와 가중치(weight)를 저장
// Comparable 구현: PriorityQueue에서 가중치를 기준으로 우선순위 결정
class Node implements Comparable<Node> {
    int vertex; // 정점 번호
    int weight; // 현재까지의 누적 거리

    Node(int v, int w) {
        vertex = v;
        weight = w;
    }

    // Comparable 구현: 가중치 오름차순으로 정렬 (최소 힙 기준)
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight; // 작은 값이 먼저 나가도록
    }
}

// 다익스트라 알고리즘
public void dijkstra(List<List<Node>> graph, int start) {
    int n = graph.size(); 
    int[] dist = new int[n]; // 시작점부터 각 정점까지 최단 거리 저장
    Arrays.fill(dist, Integer.MAX_VALUE); // 초기화: 최단 거리 무한대로 설정
    dist[start] = 0; // 시작점은 거리 0

    // 최소 힙 기반 우선순위 큐 사용
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0)); // 시작점을 큐에 넣음

    while (!pq.isEmpty()) {
        Node curr = pq.poll(); // 현재 가장 최단 거리가 짧은 노드 꺼내기

        // 이미 저장된 거리보다 길면 스킵
        if (curr.weight > dist[curr.vertex]) continue;

        // 현재 노드의 인접 노드 탐색
        for (Node next : graph.get(curr.vertex)) {
            // 더 짧은 경로 발견 시
            if (dist[next.vertex] > dist[curr.vertex] + next.weight) {
                dist[next.vertex] = dist[curr.vertex] + next.weight; // 거리 갱신
                pq.offer(new Node(next.vertex, dist[next.vertex])); // 큐에 넣어 다음 탐색
            }
        }
    }

    // 최종적으로 시작점에서 각 정점까지 최단 거리 출력
    System.out.println(Arrays.toString(dist));
}

7. 트리(Tree) 구조

트리는 노드와 노드 간의 계층 구조를 표현하는 자료구조로, 코딩테스트에서 탐색, 정렬, 최단 경로, 계층 구조 표현 등 다양한 문제에 쓰인다.

7.1 트리 기본 용어(루트·노드·자식·깊이)

트리는 노드와 노드 간의 계층 구조를 표현하는 자료구조로, 코딩테스트에서 탐색, 정렬, 최단 경로, 계층 구조 표현 등 다양한 문제에 쓰인다.
부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)

자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)

루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다.

단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.

내부 노드(internal node) : 단말 노드가 아닌 노드

형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)

깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)

레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)

차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} )

7.2 이진 트리(Binary Tree)

각 노드가 최대 2개의 자식을 가질 수 있는 트리
자식 노드: 왼쪽(left) / 오른쪽(right)
특징
- 최대 2개의 자식
- 깊이/레벨 개념 사용
- 코딩테스트에서 탐색, 순회, 재귀 문제에 자주 등장

7.3 이진 탐색 트리(BST)

왼쪽 서브트리: 루트보다 작은 값
오른쪽 서브트리: 루트보다 큰 값
검색/삽입/삭제 효율적 → 평균 O(log n)

class BSTNode {
    int val;
    BSTNode left, right;

    BSTNode(int val) { this.val = val; }

    // 삽입
    public void insert(int value) {
        if (value < this.val) {
            if (left == null) left = new BSTNode(value);
            else left.insert(value);
        } else {
            if (right == null) right = new BSTNode(value);
            else right.insert(value);
        }
    }
}

활용

검색, 정렬, 범위 쿼리
코딩테스트에서 삽입/삭제/최소값/최대값 문제

7.4 트리 순회(pre/in/post-order)

1.전위순회
순서 : 루트 -> 왼쪽 -> 오른쪽

void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

2.중위 순회

순서: 왼쪽 -> 루트 -> 오른쪽

void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);
    System.out.print(root.val + " ");
    inOrder(root.right);
}

3.후위 순회

순서: 왼쪽 -> 오른쪽 -> 루트

void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val + " ");
}

7.5 힙과 트리의 차이

항목	힙	일반 트리/ BST
구조	완전 이진트리	자유로운 계층 구조, 이진 트리는 최대 2자식
목적	최대값/최소값 접근 최적화	데이터 검색, 삽입, 삭제 등 일반 탐색
정렬 규칙	부모 ≥ / ≤ 자식 (최대/최소 힙)	BST: 왼쪽 < 루트 < 오른쪽
순회 방식	필요시 우선순위 기반	전위/중위/후위 순회
코딩테스트 활용	우선순위 큐, 다익스트라, K번째 수	탐색, 정렬, 계층 구조 문제

정리:
- 힙 = 우선순위 접근용 트리, 완전 이진 트리 기반
- BST = 검색 최적화 트리, 이진 탐색 규칙 적용
- 일반 이진 트리 = 구조 표현용 / 순회 연습용

7.6 TreeMap/TreeSet

BST 생성 + 오름차순 출력 (TreeSet 사용)

import java.util.*;

public class BSTWithTreeSet {
    public static void main(String[] args) {
        int[] nums = {5, 3, 7, 2, 4, 6, 8};

        // TreeSet 사용 → 자동 BST, 중복 제거, 오름차순 정렬
        TreeSet<Integer> bst = new TreeSet<>();
        for (int num : nums) {
            bst.add(num); // 삽입 O(log n)
        }

        // 중위 순회 대신 TreeSet 순회 → 오름차순 출력
        for (int val : bst) {
            System.out.print(val + " ");
        }
    }
}

키-값 저장 + 범위 검색 (TreeMap 사용)

import java.util.*;

public class BSTWithTreeMap {
    public static void main(String[] args) {
        int[] nums = {5, 3, 7, 2, 4, 6, 8};

        // TreeMap: Key 기준 정렬 + Value 저장 가능
        TreeMap<Integer, String> map = new TreeMap<>();
        for (int num : nums) {
            map.put(num, "Value" + num); // Key = num, Value = "Value<num>"
        }

        // 범위 검색: 3~6 사이의 key만 출력
        for (Map.Entry<Integer, String> entry : map.subMap(3, true, 6, true).entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

8. 그래프(Graph)

그래프는 정점(Vertex)와 간선(Edge)으로 구성된 자료구조로,
네트워크, 관계, 경로 문제 등 다양한 코딩테스트 문제에 등장한다.

8.1 정점(vertex)과 간선(edge)

용어	의미
정점(Vertex)	그래프의 노드, 객체, 지점 등
간선(Edge)	정점 간의 연결, 방향이 있을 수도 있음
가중치(Weight)	간선의 값, 거리나 비용을 나타냄

8.2 방향 그래프 / 무방향 그래프

구분	설명
무방향 그래프	간선이 양쪽으로 연결됨 (A ↔ B)
방향 그래프	간선이 한쪽 방향만 연결됨 (A → B)

코딩테스트에서 문제마다 방향 여부 확인 필수
예: 네트워크 전송, 위상 정렬, 최단 경로

8.3 인접 리스트 vs 인접 행렬

항목	인접 리스트	인접 행렬
구현	List<List<Integer>>	2D 배열 int[][]
메모리	O(V + E)	O(V²)
특정 정점 간 연결 확인	O(degree)	O(1)
모든 간선 탐색	O(V + E)	O(V²)
특징	sparse 그래프에 유리	dense 그래프에 유리

8.4 BFS / DFS
BFS

boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;

while (!queue.isEmpty()) {
    int node = queue.poll();
    System.out.print(node + " ");

    for (int next : graph.get(node)) {
        if (!visited[next]) {
            queue.offer(next);
            visited[next] = true;
        }
    }
}

특징

최단 경로 탐색 가능 (간선 가중치 1일 때)
큐 사용 → FIFO

DFS

void dfs(int node, boolean[] visited, List<List<Integer>> graph) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int next : graph.get(node)) {
        if (!visited[next]) dfs(next, visited, graph);
    }
}

특징

경로 탐색, 사이클 탐지, 백트래킹 활용
재귀 또는 스택 사용 → LIFO

8.5 최단거리 (Dijkstra 기본 개념 소개)

목적: 단일 시작점 → 모든 정점까지 최단 거리 계산
조건: 가중치가 0 이상일 때 사용 가능
핵심 아이디어
1. 시작점 거리 0, 나머지 무한대로 초기화
2. 우선순위 큐(PriorityQueue)로 현재 최단 거리 정점 선택
3. 선택된 정점을 기준으로 인접 정점 거리 갱신
4. 모든 정점 방문 완료
시간 복잡도
- 인접 리스트 + PQ → O(E log V)
- 인접 행렬 → O(V²)
자바 예제는 이전에 올린 Node + PriorityQueue를 활용한 Dijkstra 예제 참고 가능

💡 정리

정점/간선 → 그래프의 기본 요소
방향/무방향 → 문제 조건 확인 필수
인접 리스트 → sparse 그래프, 메모리 효율적
인접 행렬 → dense 그래프, 연결 확인 빠름
BFS/DFS → 탐색 기본, 최단 거리/사이클/백트래킹 문제 활용
Dijkstra → 가중치 있는 최단 경로, 우선순위 큐와 결합

9. 집합(Union-Find, Disjoint Set)

Union-Find는 서로소 집합(Disjoint Set)을 관리하는 자료구조로,서로 다른 집합에 속한 원소를 합치거나(Union)

특정 원소가 속한 집합을 확인(find)할 때 사용

그래프에서 사이클 검출, 최소 신장 트리(MST) 등에서 자주 등장

9.1 Disjoint Set 개념

서로소 집합(Disjoint Set): 원소들이 겹치지 않는 집합
Union-Find의 역할:
1. 원소가 어떤 집합에 속하는지 확인 → find
2. 두 집합을 합치기 → union
코딩테스트 활용:
- Kruskal MST
- 네트워크 연결 문제
- 친구 그룹 / 연결 요소 문제

9.2 find / union 연산

1) find

원소가 속한 **집합의 대표자(root)**를 반환
대표자를 통해 두 원소가 같은 집합에 속하는지 확인 가능

2) union

두 집합을 하나로 합침
합치면서 대표자(root)를 지정

int[] parent;

// 초기화: 자기 자신을 부모로
void makeSet(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
}

// find 연산
int find(int x) {
    if (parent[x] == x) return x;
    return find(parent[x]); // 재귀로 루트 탐색
}

// union 연산
void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        parent[rootB] = rootA; // rootB를 rootA에 연결
    }
}

9.3 경로 압축 (Path Compression)

find 연산 시 모든 노드를 루트로 직접 연결
다음 find 연산 시 O(1) 가까이 동작

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]); // 경로 압축
}

9.4 Union by Rank

Union 시 트리의 높이를 고려하여 루트를 결정
트리가 한쪽으로 치우치지 않게 균형 유지
rank 배열 사용: 트리 높이 또는 크기 저장

int[] rank;

void makeSet(int n) {
    parent = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
}

void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA == rootB) return;

    // rank가 작은 트리를 큰 트리에 붙임
    if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
    else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
    else {
        parent[rootB] = rootA;
        rank[rootA]++;
    }
}

'코딩테스트' 카테고리의 다른 글

시간복잡도 (0)	2025.10.03

'코딩테스트' Related Articles

시간복잡도 2025.10.03