List

리스트는 배열처럼 인덱스를 통해 접근할 수 있으며, 중복된 요소를 허용합니다. 크기가 동적으로 조정된다는 점에서 배열보다 유연한 특징을 가지고 있습니다.

List 인터페이스의 구현 클래스

  • ArrayList: 배열 기반으로 동작하는 List 구현체입니다. 요소에 빠르게 접근할 수 있으나, 요소를 삽입하거나 삭제하는 경우 배열을 재조정해야 하므로 성능에 영향을 미칠 수 있습니다. 많은 양의 읽기 작업이 있을 때 효율적입니다.
  • LinkedList: 이중 연결 리스트로 구현된 List입니다. 요소를 삽입하거나 삭제할 때 빠른 성능을 보장하지만, 인덱스를 기반으로 접근할 때는 ArrayList에 비해 성능이 떨어질 수 있습니다. 양쪽 끝에서 삽입/삭제 작업이 자주 발생하는 경우에 유리합니다.
  • Vector: Vector는 ArrayList와 비슷하지만, 모든 메서드가 동기화되어 있어 다중 스레드 환경에서 안전합니다. 그러나 이로 인해 일반적인 상황에서는 성능이 떨어질 수 있습니다. 과거에 많이 사용되었으나, 현재는 동기화가 필요한 경우 ArrayList를 구현으로 List를 감싸는 래퍼인 Collections.synchronizedList()을 사용합니다.
  • Stack: Vector를 상속받은 클래스로, LIFO(Last In First Out) 방식으로 동작하는 스택 구조를 구현합니다. push(), pop(), peek() 등의 메서드를 제공하여 스택 자료 구조를 쉽게 구현할 수 있습니다. Stack은 Vector를 상속받았기 때문에 기본적으로 동기화된 메서드를 사용하며, 이로 인해 성능이 저하될 수 있습니다. 또한, 구조적으로 다른 자료구조 클래스들과 일관성이 부족하고 설계가 다소 구식입니다. Stack 대신 Deque(double-ended queue)를 사용하는 것이 더 권장됩니다.

List의 기본 메서드

  • add(E e): 리스트의 끝에 요소를 추가.
  • add(int index, E e): 리스트의 특정 위치에 요소를 추가.
  • get(int index): 리스트의 특정 인덱스에 있는 요소를 반환.
  • remove(int index): 리스트에서 특정 인덱스의 요소를 제거.
  • set(int index, E e): 리스트의 특정 위치의 요소를 새로운 값으로 갱신.
  • size(): 리스트에 있는 요소의 개수를 반환.
  • contains(Object o): 리스트에 특정 요소가 있는지 확인.
  • clear(): 리스트의 모든 요소를 제거.
  • isEmpty(): 리스트가 비어 있는지 확인.

List의 조건부 삽입 및 갱신 메서드

  • replaceAll(UnaryOperator<E> operator): 리스트의 모든 요소를 주어진 조건에 맞게 갱신.
  • removeIf(Predicate<? super E> filter): 주어진 조건에 맞는 요소를 리스트에서 제거.

Map

맵은 키와 값 쌍으로 데이터를 저장하며, 각 키는 중복되지 않지만 값은 중복될 수 있습니다. 맵은 특정 키로 빠르게 값을 찾을 수 있는 자료구조입니다.

Map 인터페이스의 구현 클래스

  • HashMap: 키와 값의 쌍을 해시 테이블 기반으로 저장하며, 삽입 순서를 보장하지 않습니다. 가장 많이 사용되는 Map 구현 클래스입니다.
  • TreeMap: 키에 대해 정렬된 순서로 키-값 쌍을 저장합니다. 내부적으로 레드-블랙 트리를 사용하여 키를 정렬합니다.
  • LinkedHashMap: 삽입 순서(또는 액세스 순서)에 따라 키-값 쌍을 저장합니다. HashMap의 기능을 기반으로 하면서도 순서를 유지합니다.

Map의 기본 메서드

  • put(K key, V value): 키-값 쌍을 삽입 또는 업데이트.
  • get(Object key): 특정 키에 해당하는 값 반환.
  • remove(Object key): 특정 키에 해당하는 항목 삭제.
  • containsKey(Object key): 특정 키가 맵에 존재하는지 확인.
  • containsValue(Object value): 특정 값이 맵에 존재하는지 확인.
  • size(): 맵에 저장된 항목의 개수 반환.
  • isEmpty(): 맵이 비어있는지 여부 확인.
  • clear(): 맵에 저장된 모든 항목 삭제.
  • keySet(): 맵의 모든 키를 반환.
  • values(): 맵의 모든 값을 반환.
  • entrySet(): 맵의 모든 키-값 쌍을 반환.

Map의 조건부 삽입 및 갱신 메서드

  • putIfAbsent(K key, V value): 이미 해당 키가 존재하면, 기존 값을 유지하고 아무 것도 하지 않음.
  • getOrDefault(Object key, V defaultValue): 키가 존재하지 않으면 기본값을 반환.
  • remove(Object key, Object value): 키와 값이 모두 일치할 때만 안전하게 삭제.
  • replace(K key, V oldValue, V newValue): 키와 기존 값이 일치하는 경우에만 값을 새로운 값으로 교체.
  • computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction): 키가 없을 때 동적으로 값을 생성하여 삽입.
  • computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction): 키가 있을 때만 값을 계산하여 갱신.
LinkedHashMap

LinkedHashMap은 요소들이 삽입된 순서를 유지하며, 필요에 따라 액세스된 순서를 유지할 수도 있습니다. 이는 순차적으로 데이터를 처리하거나, 순서가 중요한 데이터의 경우 유용합니다.

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
32
33
import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // LinkedHashMap 생성 (삽입 순서 유지)
        LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();

        // 요소 추가
        linkedHashMap.put("banana", 2);
        linkedHashMap.put("apple", 3);
        linkedHashMap.put("orange", 1);

        // LinkedHashMap 출력 (삽입된 순서 유지)
        System.out.println("LinkedHashMap 출력 (삽입 순서):");
        for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 특정 키에 접근 (액세스 순서로 변경)
        linkedHashMap.get("banana");

        // 액세스 순서로 정렬되도록 새로운 LinkedHashMap 생성
        LinkedHashMap<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.putAll(linkedHashMap);

        // 액세스 순서로 재정렬된 LinkedHashMap 출력
        System.out.println("\nLinkedHashMap 출력 (액세스 순서):");
        for (Map.Entry<String, Integer> entry : accessOrderMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}
1
2
3
4
5
6
7
8
9
LinkedHashMap 출력 (삽입 순서):
banana: 2
apple: 3
orange: 1

LinkedHashMap 출력 (액세스 순서):
apple: 3
orange: 1
banana: 2

new LinkedHashMap<>(16, 0.75f, true);

  • initialCapacity (16): 맵의 초기 용량을 지정합니다. inkedHashMap이 처음 생성될 때 내부적으로 몇 개의 버킷을 할당할지를 결정합니다.
  • loadFactor (0.75f): 해시 테이블의 “적재율”을 나타내는 값입니다. 0.75f는 기본 값으로, 해시 테이블이 75% 차게 되면 버킷의 수가 두 배로 증가하게 됩니다. 이는 해시 충돌을 줄이기 위해 사용됩니다.
  • accessOrder (true): 이 매개변수는 LinkedHashMap이 요소를 유지하는 순서를 결정합니다. false로 설정하면 삽입 순서에 따라 요소를 유지합니다. 즉, 요소들이 삽입된 순서대로 유지됩니다. true로 설정하면 접근 순서에 따라 요소를 유지합니다. 즉, 요소에 접근(읽기 또는 쓰기)할 때마다 해당 요소가 맵의 끝으로 이동하여 가장 최근에 접근한 요소가 마지막에 위치하게 됩니다. accessOrder가 true로 설정되면, LinkedHashMap은 LRU (Least Recently Used) 캐시 처럼 동작할 수 있습니다. 이는 최근에 접근된 요소를 맵의 끝으로 이동시키며, 가장 오래된 요소가 맨 앞에 위치하게 됩니다.

Set

Java에서 Set은 중복을 허용하지 않는 데이터 컬렉션을 관리하는 자료구조입니다. Set은 수학에서의 집합과 유사한 개념으로, 각 요소가 고유해야 하며 순서는 중요하지 않습니다.

Java의 Set 인터페이스는 다음과 같은 주요 구현 클래스로 제공됩니다:

a. HashSet

  • 특징: HashSet은 가장 일반적으로 사용되는 Set 구현체로, 요소들을 해시 테이블을 사용하여 저장합니다. 저장된 순서가 유지되지 않으며, 요소의 삽입, 삭제, 검색이 빠릅니다.
  • 용도: 빠른 조회가 필요하고, 순서가 중요하지 않으며 중복을 허용하지 않아야 할 때 사용됩니다.

b. LinkedHashSet

  • 특징: LinkedHashSet은 HashSet과 비슷하지만, 요소의 삽입 순서를 유지합니다. 내부적으로 이중 연결 리스트(doubly-linked list)를 사용하여 요소를 저장하며, 삽입된 순서대로 요소를 순회할 수 있습니다.
  • 용도: 요소가 삽입된 순서대로 순회해야 할 때 사용됩니다.

c. TreeSet

  • 특징: TreeSet은 요소들을 정렬된 순서로 저장합니다. 내부적으로 레드-블랙 트리(Red-Black Tree)를 사용하여 요소를 관리하며, 요소들이 자연스러운 순서(또는 지정된 Comparator에 따른 순서)로 정렬됩니다.
  • 용도: 정렬된 순서가 필요할 때 사용됩니다.

4. Set 사용 예제

아래는 HashSet을 사용하여 기본적인 Set 연산을 수행하는 예제입니다.

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
32
33
34
35
36
37
38
import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        // HashSet 생성
        Set<String> set = new HashSet<>();

        // 요소 추가
        set.add("apple");
        set.add("banana");
        set.add("orange");

        // 중복된 요소 추가 (무시됨)
        set.add("apple");

        // Set의 요소 출력
        System.out.println("Set의 요소:");
        for (String fruit : set) {
            System.out.println(fruit);
        }

        // 특정 요소가 포함되어 있는지 확인
        if (set.contains("banana")) {
            System.out.println("banana가 포함되어 있습니다.");
        }

        // 요소 제거
        set.remove("banana");

        // Set의 크기 확인
        System.out.println("Set의 크기: " + set.size());  // 출력: Set의 크기: 2

        // Set 비우기
        set.clear();
        System.out.println("Set이 비어 있는가? " + set.isEmpty());  // 출력: Set이 비어 있는가? true
    }
}

5. 특징 요약

  • 중복 불허: Set은 중복된 요소를 허용하지 않으며, 모든 요소가 고유해야 합니다.
  • 순서 없음: Set에 저장된 요소들은 특정한 순서 없이 저장됩니다. 단, LinkedHashSet은 삽입 순서를 유지하고, TreeSet은 정렬된 순서를 유지합니다.
  • 효율적인 조회: 특히 HashSet은 매우 빠른 조회 성능을 제공합니다.

6. Set의 활용

Set은 중복을 허용하지 않는 고유한 데이터 집합을 관리하는 데 매우 유용합니다. 예를 들어, 학생 명단, 유일한 ID 관리, 중복을 제거해야 하는 데이터 집합 등의 상황에서 사용할 수 있습니다.

Stack

Java에서 ArrayDeque와 LinkedList를 사용하여 스택(Stack)을 구현하는 방법을 보여드리겠습니다. 두 클래스 모두 Deque 인터페이스를 구현하며, 이를 통해 스택과 큐의 기능을 모두 사용할 수 있습니다.

1. ArrayDeque로 스택 사용

ArrayDeque는 스택으로 사용할 때 매우 효율적입니다. 스택에서 사용되는 기본적인 연산인 push(요소 추가), pop(요소 제거), peek(요소 확인)을 쉽게 구현할 수 있습니다.

ArrayDeque 예제

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
import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeStackExample {
    public static void main(String[] args) {
        // ArrayDeque 생성
        Deque<String> stack = new ArrayDeque<>();

        // 요소 추가 (스택의 push와 동일)
        stack.add("apple");
        stack.add("banana");
        stack.add("cherry");

        // 스택의 맨 위 요소 확인 (peek)
        System.out.println("Top element: " + stack.peek());

        // 스택에서 요소 제거 (pop)
        System.out.println("Popped element: " + stack.pop());

        // 스택 출력
        System.out.println("Stack after pop: " + stack);

        // 요소 추가 (push 동작을 명확히 하기 위해)
        stack.push("date");
        System.out.println("Stack after push: " + stack);
    }
}

출력 결과

1
2
3
4
Top element: cherry
Popped element: cherry
Stack after pop: [apple, banana]
Stack after push: [date, apple, banana]

2. LinkedList로 스택 사용

LinkedList는 Deque 인터페이스를 구현하므로, 스택으로 사용될 수 있습니다. 기본적인 스택 연산을 동일하게 구현할 수 있습니다.

LinkedList 예제

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
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListStackExample {
    public static void main(String[] args) {
        // LinkedList 생성
        Deque<String> stack = new LinkedList<>();

        // 요소 추가 (스택의 push와 동일)
        stack.add("apple");
        stack.add("banana");
        stack.add("cherry");

        // 스택의 맨 위 요소 확인 (peek)
        System.out.println("Top element: " + stack.peek());

        // 스택에서 요소 제거 (pop)
        System.out.println("Popped element: " + stack.pop());

        // 스택 출력
        System.out.println("Stack after pop: " + stack);

        // 요소 추가 (push 동작을 명확히 하기 위해)
        stack.push("date");
        System.out.println("Stack after push: " + stack);
    }
}

출력 결과

1
2
3
4
Top element: cherry
Popped element: cherry
Stack after pop: [apple, banana]
Stack after push: [date, apple, banana]

3. 요약 및 비교

  • ArrayDeque:

    • 빠르고 효율적인 스택 구현이 가능합니다.
    • ArrayDeque는 동기화되지 않은 환경에서 성능이 뛰어나고, ArrayList보다 스택 연산에 더 적합합니다.
    • 스택 연산은 add, push, pop, peek 메서드로 구현할 수 있습니다.

  • LinkedList:

    • 요소 추가 및 제거가 빈번히 발생하는 경우에 적합합니다.
    • LinkedList는 메모리 오버헤드가 있지만, 요소의 삽입과 삭제가 빠릅니다.
    • 스택 연산은 add, push, pop, peek 메서드로 구현할 수 있습니다.

두 컬렉션 모두 스택 기능을 쉽게 구현할 수 있으며, 상황에 맞게 선택할 수 있습니다. 일반적으로, 스택으로 사용하기 위해서는 ArrayDeque를 사용하는 것이 성능 면에서 더 유리합니다.

4. 메모리 오버헤드

메모리 오버헤드는 데이터를 저장하는 데 필요한 추가적인 메모리 소비를 의미합니다. LinkedList에서 메모리 오버헤드가 발생하는 이유는 LinkedList의 내부 구조가 **이중 연결 리스트(Doubly Linked List)**로 구현되어 있기 때문입니다.

LinkedList의 구조:

  • 노드(Node): LinkedList는 각 요소를 노드로 저장합니다. 각 노드는 다음과 같은 세 가지 필드를 가집니다:
    • 데이터 필드: 실제 데이터(요소)가 저장되는 부분입니다.
    • 다음 노드에 대한 참조(Next): 리스트에서 다음 요소를 가리키는 참조(포인터)입니다.
    • 이전 노드에 대한 참조(Previous): 리스트에서 이전 요소를 가리키는 참조(포인터)입니다.

이렇게 각 노드가 데이터 외에도 두 개의 추가적인 참조(이전 노드와 다음 노드에 대한 참조)를 가지고 있기 때문에, LinkedList는 단순히 데이터만 저장하는 배열(Array)이나 ArrayDeque와 비교했을 때 더 많은 메모리를 사용하게 됩니다. 이 추가적인 참조가 바로 메모리 오버헤드의 원인입니다.

5. add()와 push()의 차이점

  • add():

    • add(E e) 메서드는 List 인터페이스와 Deque 인터페이스에 공통으로 정의되어 있으며, 요소를 리스트의 끝에 추가하는 역할을 합니다.
    • Deque 인터페이스에서 addFirst(E e)와 addLast(E e) 메서드를 사용하여 요소를 앞이나 뒤에 추가할 수 있습니다. 기본적으로 add(E e)는 addLast(E e)와 동일하게 작동합니다.

  • push():

    • push(E e) 메서드는 주로 스택의 개념에서 사용됩니다. Deque 인터페이스에서 push(E e)는 요소를 스택의 맨 위(즉, 리스트의 첫 번째 위치)에 추가합니다.
    • 이는 addFirst(E e)와 동일한 동작을 수행합니다.

우선순위 큐

최소 힙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // 최소힙을 구현하기 위해 PriorityQueue를 사용
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 힙에 값 추가
        minHeap.add(10);
        minHeap.add(4);
        minHeap.add(15);
        minHeap.add(20);
        minHeap.add(0);

        // 힙에서 값을 하나씩 제거하며 출력 (오름차순)
        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // poll() 메서드는 힙에서 최소값을 제거하고 반환
        }
    }
}

1
2
3
4
5
0
4
10
15
20

최대 힙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 최대힙을 구현하기 위해 PriorityQueue를 사용, Collections.reverseOrder()를 사용하여 역순 정렬
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 힙에 값 추가
        maxHeap.add(10);
        maxHeap.add(4);
        maxHeap.add(15);
        maxHeap.add(20);
        maxHeap.add(0);

        // 힙에서 값을 하나씩 제거하며 출력 (내림차순)
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // poll() 메서드는 힙에서 최대값을 제거하고 반환
        }
    }
}
1
2
3
4
5
20
15
10
4
0

메서드

PriorityQueue 메서드

  • add(E e): 우선순위 큐에 요소를 추가합니다. 만약 힙의 용량이 초과되면 IllegalStateException이 발생할 수 있습니다.
  • offer(E e): 우선순위 큐에 요소를 추가합니다. 힙의 용량이 초과되어도 add()와 달리 false를 반환합니다.
  • peek(): 힙의 루트 요소(최소 또는 최대값)를 반환합니다. 힙에서 제거하지는 않습니다.
  • poll(): 힙의 루트 요소를 반환하고 제거합니다. 큐가 비어 있으면 null을 반환합니다。
  • remove(Object o): 특정 요소를 제거합니다.
  • contains(Object o): 큐에 특정 요소가 포함되어 있는지 확인합니다。
  • clear(): 큐의 모든 요소를 제거합니다。
  • size(): 큐의 크기를 반환합니다。
  • isEmpty(): 큐가 비어 있는지 확인합니다。

각종 변환 방법

String -> Array

1
2
3
4
5
6
7
8
// String을 char 배열로 변환
char[] charArray = str.toCharArray();

// 쉼표를 기준으로 문자열을 배열로 변환
String[] strArray = str.split(",");

// String을 한 글자씩 잘라서 배열로 변환
String[] strArray = str.split("");

Array -> String

1
2
3
4
5
6
7
8
9
10
11
12
public class StringArrayToStringExample {
    public static void main(String[] args) {
        String[] stringArray = {"Hello", "World", "Java"};

        // String[] 배열을 하나의 String으로 변환 (구분자 사용)
        String result = String.join(" ", stringArray);

        // 출력
        System.out.println(result);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class StringArrayToStringExample {
    public static void main(String[] args) {
        String[] stringArray = {"Hello", "World", "Java"};

        // StringBuilder를 사용해 String[] 배열을 String으로 변환
        StringBuilder sb = new StringBuilder();
        for (String str : stringArray) {
            sb.append(str).append(" ");
        }

        // 마지막 공백 제거
        String result = sb.toString().trim();

        // 출력
        System.out.println(result);
    }
}
1
2
3
4
5
6
7
8
9
10
11
public class CharArrayToStringExample {
    public static void main(String[] args) {
        char[] charArray = {'H', 'e', 'l', 'l', 'o'};

        // char[] 배열을 String으로 변환
        String result = new String(charArray);

        // 출력
        System.out.println(result);
    }
}

List<String> -> String[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;
import java.util.List;

public class ListToStringArrayExample {
    public static void main(String[] args) {
        // List<String> 생성
        List<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");

        // List<String>을 String[]로 변환
        String[] stringArray = list.toArray(new String[0]);

        // String[] 출력
        for (String str : stringArray) {
            System.out.println(str);
        }
    }
}

List<Character> -> char[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
import java.util.List;

public class ListToCharArrayExample {
    public static void main(String[] args) {
        // List<Character> 생성
        List<Character> list = new ArrayList<>();
        list.add('A');
        list.add('B');
        list.add('C');

        // List<Character>를 char[]로 변환
        char[] charArray = new char[list.size()];
        for (int i = 0; i < list.size(); i++) {
            charArray[i] = list.get(i);
        }

        // char[] 출력
        for (char c : charArray) {
            System.out.println(c);
        }
    }
}

List<Integer> -> int[]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.ArrayList;
import java.util.List;

public class ListToIntArrayExample {
    public static void main(String[] args) {
        // List<Integer> 생성
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // List<Integer>를 int[]로 변환
        int[] array = list.stream().mapToInt(Integer::intValue).toArray();

        // 배열 출력
        for (int num : array) {
            System.out.println(num);
        }
    }
}

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
import java.util.ArrayList;
import java.util.List;

public class ListToIntArrayExample {
    public static void main(String[] args) {
        // List<Integer> 생성
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // List<Integer>의 크기에 맞는 int[] 배열 생성
        int[] array = new int[list.size()];

        // List<Integer>를 int[]로 변환
        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i); // Unboxing Integer to int
        }

        // 배열 출력
        for (int num : array) {
            System.out.println(num);
        }
    }
}

정렬

  • Arrays.sort(): 배열을 정렬할 때 사용. 기본적으로 오름차순으로 정렬하며, Comparator를 사용하여 내림차순 정렬 가능.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    import java.util.Arrays;

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

            // 배열 오름차순 정렬
            Arrays.sort(numbers);

            // 정렬된 배열 출력
            System.out.println(Arrays.toString(numbers));
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Arrays;
import java.util.Collections;

public class ReverseSortExample {
    public static void main(String[] args) {
        String[] fruits = {"Banana", "Apple", "Orange", "Grape"};

        // 문자열 배열 내림차순 정렬
        Arrays.sort(fruits, Collections.reverseOrder());

        // 정렬된 배열 출력
        System.out.println(Arrays.toString(fruits));
    }
}

  • Collections.sort(): List를 정렬할 때 사용. 기본적으로 오름차순으로 정렬하며, Comparator를 사용하여 내림차순 정렬 가능.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;

    public class ListSortExample {
        public static void main(String[] args) {
            List<String> fruits = new ArrayList<>();
            fruits.add("Banana");
            fruits.add("Apple");
            fruits.add("Orange");
            fruits.add("Grape");

            // 리스트 오름차순 정렬
            Collections.sort(fruits);

            // 정렬된 리스트 출력
            System.out.println(fruits);
        }
    }

  • Java 8 Stream: 스트림을 이용한 정렬도 가능.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    import java.util.Arrays;
    import java.util.List;
    import java.util.stream.Collectors;

    public class StreamSortExample {
        public static void main(String[] args) {
            List<String> fruits = Arrays.asList("Banana", "Apple", "Orange", "Grape");

            // 스트림을 사용한 정렬
            List<String> sortedFruits = fruits.stream()
                                              .sorted()
                                            //.sorted(Comparator.reverseOrder())
                                              .collect(Collectors.toList());

            // 정렬된 리스트 출력
            System.out.println(sortedFruits);
        }
    }

  • 2차원 배열 정렬

    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
    import java.util.Arrays;
    import java.util.Comparator;

    public class Sort2DArrayExample {
        public static void main(String[] args) {
            int[][] array = {
                {2, 1},
                {1, 3},
                {4, 5}
            };

            // 첫 번째 요소를 기준으로 2차원 배열을 정렬
            Arrays.sort(array, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return Integer.compare(a[0], b[0]); // 첫 번째 요소(a[0], b[0])를 기준으로 비교
                }
            });

            // 정렬된 배열 출력
            for (int[] row : array) {
                System.out.println(Arrays.toString(row));
            }
        }
    }
    1
    2
    3
    [1, 3]
    [2, 1]
    [4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

public class LambdaSortExample {
    public static void main(String[] args) {
        int[][] jobs = {
            {2, 1},
            {1, 3},
            {4, 5}
        };

        // 람다 표현식을 사용하여 첫 번째 요소를 기준으로 오름차순 정렬
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);

        // 정렬된 배열 출력
        for (int[] job : jobs) {
            System.out.println(Arrays.toString(job));
        }
    }
}
1
2
3
[1, 3]
[2, 1]
[4, 5]

Java에서 그래프를 나타내는 방법에는 여러 가지가 있으며, 각 방법은 그래프의 특성, 메모리 효율성, 접근 및 수정 용이성에 따라 선택할 수 있습니다. 주요한 그래프 표현 방법은 다음과 같습니다:

1. 인접 리스트 (Adjacency List)

  • 설명: 그래프의 각 정점마다 연결된 정점들의 리스트를 유지합니다.
  • 구현: 주로 ArrayList 또는 LinkedList를 사용하여 구현합니다.
  • 장점:
    • 메모리 효율적(특히 희소 그래프에서).
    • 특정 정점의 이웃 정점들을 쉽게 순회할 수 있습니다.
  • 단점:
    • 간선 존재 여부를 확인하는데 O(V) 시간이 소요될 수 있습니다(특히 리스트 기반의 경우).

예제 코드:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.ArrayList;

public class Graph {
    private ArrayList<Integer>[] adjList;

    public Graph(int n) {
        adjList = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adjList[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        adjList[u].add(v);
        adjList[v].add(u); // 무방향 그래프일 경우
    }

    public ArrayList<Integer> getNeighbors(int u) {
        return adjList[u];
    }
}

2. 인접 행렬 (Adjacency Matrix)

  • 설명: 그래프를 2차원 배열(행렬)로 표현합니다. 행렬의 요소 matrix[i][j]는 정점 i에서 정점 j로의 간선이 존재하는지 나타냅니다.
  • 구현: int[][] 또는 boolean[][] 배열을 사용하여 구현합니다.
  • 장점:
    • 간선 존재 여부를 O(1) 시간에 확인할 수 있습니다.
    • 특정 정점의 이웃 정점들을 쉽게 순회할 수 있습니다.
  • 단점:
    • 메모리 낭비가 큽니다(특히 희소 그래프에서). 모든 간선 정보를 저장해야 하므로, 그래프가 커질수록 메모리 사용이 급증합니다.

예제 코드:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Graph {
    private int[][] adjMatrix;

    public Graph(int n) {
        adjMatrix = new int[n + 1][n + 1];
    }

    public void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; // 무방향 그래프일 경우
    }

    public boolean hasEdge(int u, int v) {
        return adjMatrix[u][v] == 1;
    }

    public int[] getNeighbors(int u) {
        return adjMatrix[u];
    }
}

3. 간선 리스트 (Edge List)

  • 설명: 모든 간선을 리스트로 유지합니다. 각 간선은 연결된 두 정점과 가중치(가중치가 있는 그래프의 경우)를 나타냅니다.
  • 구현: List<Edge> 또는 ArrayList<int[]>로 구현할 수 있습니다.
  • 장점:
    • 메모리 효율적(특히 희소 그래프에서).
    • 간선 중심의 그래프 알고리즘(예: 크루스칼의 최소 신장 트리 알고리즘)에 적합합니다.
  • 단점:
    • 간선 존재 여부를 확인하는데 O(E) 시간이 소요될 수 있습니다.
    • 특정 정점의 이웃 정점들을 찾기가 다소 비효율적일 수 있습니다.

예제 코드:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.ArrayList;
import java.util.List;

public class Graph {
    private List<int[]> edgeList;

    public Graph() {
        edgeList = new ArrayList<>();
    }

    public void addEdge(int u, int v, int weight) {
        edgeList.add(new int[]{u, v, weight});
    }

    public List<int[]> getEdges() {
        return edgeList;
    }
}

4. 인접 집합 (Adjacency Set)

  • 설명: 각 정점마다 연결된 정점들을 HashSet으로 유지합니다. 이는 인접 리스트의 변형으로, 특정 간선의 존재 여부를 더 빠르게 확인할 수 있습니다.
  • 구현: HashSet<Integer>[] 배열로 구현합니다.
  • 장점:
    • 간선 존재 여부를 O(1) 시간에 확인할 수 있습니다.
    • 인접 리스트보다 간선 존재 여부 확인이 더 빠릅니다.
  • 단점:
    • 메모리 사용량이 더 많을 수 있습니다(HashSet의 오버헤드).

예제 코드:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.HashSet;

public class Graph {
    private HashSet<Integer>[] adjSet;

    public Graph(int n) {
        adjSet = new HashSet[n + 1];
        for (int i = 0; i <= n; i++) {
            adjSet[i] = new HashSet<>();
        }
    }

    public void addEdge(int u, int v) {
        adjSet[u].add(v);
        adjSet[v].add(u); // 무방향 그래프일 경우
    }

    public boolean hasEdge(int u, int v) {
        return adjSet[u].contains(v);
    }
}

5. 트리 (Tree)

  • 설명: 트리는 사이클이 없는 그래프의 특수한 형태입니다. 트리는 부모와 자식 노드의 관계를 기반으로 계층 구조를 유지합니다.
  • 구현: 트리 구조는 주로 Node 클래스를 통해 구현되며, 각 노드는 자식 노드를 가리키는 리스트 또는 배열을 가집니다.
  • 장점:
    • 재귀적으로 정의되며, 노드 기반 알고리즘에 적합합니다.
    • 특정 노드의 자식 또는 부모를 찾기가 쉽습니다.
  • 단점:
    • 간선 중심의 그래프 알고리즘에 적합하지 않을 수 있습니다.

예제 코드:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int value;
    List<TreeNode> children;

    public TreeNode(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode child) {
        children.add(child);
    }
}

6. 이차원 리스트

  • 설명: 간선 리스트의 2차원 배열 버전입니다. 간선을 나타내기 위해 모든 정점 쌍을 저장합니다. 일반적으로 트리 또는 네트워크 흐름 문제에 사용됩니다.
  • 구현: List<int[]> 또는 int[][]로 구현할 수 있습니다.
  • 장점:
    • 특정 노드 간의 간선을 빠르게 검색할 수 있습니다.
  • 단점:
    • 모든 간선을 저장해야 하므로, 메모리 사용량이 많습니다.

요약

  • 인접 리스트: 메모리 효율성이 중요하고, 정점의 이웃 탐색이 필요한 경우.
  • 인접 행렬: 정점 사이의 간선 존재 여부를 빠르게 확인해야 하는 경우.
  • 간선 리스트: 간선 중심의 알고리즘에 적합하거나 희소 그래프에서 사용.
  • 인접 집합: 빠른 간선 존재 확인이 필요하면서도 인접 리스트의 변형을 원하는 경우.
  • 트리: 계층적 데이터 구조를 표현하고자 하는 경우.

각 방법은 특정 상황에 따라 더 적합할 수 있습니다. 데이터의 특성과 알고리즘의 요구사항에 따라 적절한 그래프 표현 방법을 선택하는 것이 중요합니다.

https://earthteacher.tistory.com/169#gsc.tab=0

1
2
3
4
5
6
static ArrayList<Integer>[] arr;
arr = new ArrayList[N + 1];

for (int i = 0; i < arr.length; i++) {
    arr[i] = new ArrayList<>();
}