미뤄뒀던 자료구조와 알고리즘을 학습하고 정리한 것을 공유하고자 합니다.
■ 강의 정보
- 강의자: 얄팍한 코딩사전
- 강의명: 얄코의 가장 쉬운 자료구조와 알고리즘
- 커리큘럼
섹션 1. 인트로
섹션 2. 배열과 리스트
섹션 3. 스택과 큐
섹션 4. 트리
섹션 5. 정렬 알고리즘
섹션 6. 해시 맵
섹션 7. 그래프
■ 강의 정리
< 섹션 1. 인트로 >
*Big-O 표기법
'이 알고리즘은 데이터를 많이 넣을수록 얼마나 느려질까'를 수학적으로 표시
- 시간복잡도: 작업에 필요한 연산횟수
- 공간복잡도: 필요한 메모리 양
< 섹션 2. 배열과 리스트 >
*1차원 정적배열 & 동적 배열 시간복잡도
조회, 수정: O(1)
제거, 추가: O(n)
- 동적배열의 추가의 경우 내부에 여유 공간이 있다면 O(1)
*2차원 배열
- 생성: 시간&공간복잡도: O(n*m)
- 조회, 수정: 시간&공간복잡도: O(1)
(행이나 열의 크기와 상관없이 일정한 횟수의 연산으로 이뤄지는 작업이라는 의미)
- 검색
시간복잡도: O(n*m)
공간복잡도: O(1)
*단일 연결 리스트
한 요소가 다음 요소를 가리키는 구조로 메모리에서 살펴보면 각 요소들이 연속되지 않은 공간에 위치
- 시간복잡도
조회, 수정, 추가, 제거, 검색: O(n)
(HEAD 추가&제거: O(1))
cf) 요소 추가&제거에 있어서 배열과 시간복잡도는 동일하지만 값들을 밀어내는 과정이 필요 없으므로 연결리스트가 더 효율적임
+ 단일 원형 연결 리스트도 존재
*이중 연결 리스트
각 요소는 이전 요소와 다음 요소의 참조값음 가짐. 헤드에서 정방향 뿐 아니라, 테일로부터 역방향 순회 가능
- 스택, 큐 등의 자료구조에서 유용하게 사용됨
*이중 원형 연결 리스트
마지막 요소의 '다음'은 첫 요소를 참조하고 첫 요소의 '이전'은 마지막 요소를 참조
< 섹션 3. 스택과 큐 >
*Stack(스택): Last In First Out
*Queue(큐): First In First Out
-> 스택과 큐는 데이터의 순차적 처리와 순서 제어를 위한 기본 자료구조로, 다양한 알고리즘의 핵심적인 빌딩 블록이 됨
*Stack (배열 기반, 연결 리스트 기반, 콜스택)
- push: 마지막에 추가 / O(1)
- pop: 마지막 제거 & 반환 / O(1)
- peek: 마지막 요소 확인 / O(1)
*배열을 사용한 Stack 구현
- 정적 배열 형태의 스택
- stack, capacity, top
public class ArrayStack {
private int[] stack;
private int capacity;
private int top;
public ArrayStack(int capacity) {
this.capacity = capacity;
this.stack = new int[capacity];
this.top = -1;
}
public void push(int item) {
if (top + 1 == capacity) {
throw new RuntimeException("Stack is full");
}
stack[++top] = item;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top--];
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
*연결 리스트를 사용한 Stack 구현
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListStack {
private Node head;
private int count;
public LinkedListStack() {
head = null;
count = 0;
}
public void push(int item) {
Node newNode = new Node(item);
newNode.next = head;
head = newNode;
count++;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
int item = head.data;
head = head.next;
count--;
return item;
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return head.data;
}
public boolean isEmpty() {
return head == null;
}
public int size() { return count; }
public static void main(String[] args) {
LinkedListStack stack = new LinkedListStack();
stack.push(5);
stack.push(2);
stack.push(8);
stack.push(7);
stack.push(4);
System.out.println(stack.pop()); // 4
System.out.println(stack.pop()); // 7
System.out.println(stack.peek()); // 8
System.out.println(stack.size()); // 3
System.out.println(stack.isEmpty()); // false
}
}
cf) 파이썬은 증감 연산자(++, --) 존재 안함. 대신 복합 대입 연산자(+=, -=) 사용
cf) 파이썬은 boolean을 표현할 때 무조건 True, False로 표현해야 됨 (첫 글자 대문자 & 나머지 소문자, 빈 객체나 0은 거짓으로 간주)
- 배열 기반 스택: 요소들의 크기가 고정되어 있고 간단한 구현 시
- 연결 기반 스택: 크기가 유동적이고 삽입, 삭제가 자주 발생하는 경우
*Call Stack (콜 스택)
함수를 사용할 때마다 그와 관련된 정보들이 쌓이는 곳
- Call Stack 상의 프레임과 스코프의 관계
- call stack을 통해 오류가 발생한 지점을 보여주는 것: stack trace
*Queue (배열 기반)
- 선형큐: 배열 크기 만큼의 요소들을 담으면 더 이 상 사용할 수 없음
- 원형큐: 배열 크기 만큼의 요소를 담아도 꺼내주기만 하면 남은 자리에 얼마든지 새 값들을 넣을 수 있음 (단, 어디에 값이 저장되든 FIFO 원칙은 지켜짐 -> 배열상의 순서와는 달리 요소들을 넣은 순서대로 값들이 출력됨)
-> 위와 같은 특징 때문에 원형큐를 주로 사용
- 코드로 구현 시 필요 요소: queue, capacity, front, rear, size, isEmpty(), isFull()
- 함수 display 주의할 점: '원형 큐'임을 감안하여 배열 내 'front'의 위치부터 'size'의 크기만큼 출력해야 됨 (int index = front; 로 초기화 필요)
public class CircularQueue {
private int[] queue;
private int capacity;
private int front;
private int rear;
private int size;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
this.front = 0;
this.rear = 0;
this.size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public void enqueue(int item) {
if (isFull()) {
System.out.println("Queue is full");
return;
}
queue[rear] = item;
rear = (rear + 1) % capacity;
size++;
}
public Integer dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return null;
}
int item = queue[front];
queue[front] = 0; // optional: clear slot
front = (front + 1) % capacity;
size--;
return item;
}
public void display() {
int index = front;
for (int i = 0; i < size; i++) {
System.out.print(queue[index] + " ");
index = (index + 1) % capacity;
}
System.out.println();
}
}
*Queue (단일 연결 리스트 기반)
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
public class LinkedListQueue {
private Node front; // 빠질 곳
private Node rear; // 넣을 곳
public boolean isEmpty() { return front == null; }
public void enqueue(int item) {
Node newNode = new Node(item);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
public Integer dequeue() {
if (front == null) {
System.out.println("Queue is empty");
return null;
}
int item = front.data;
front = front.next;
if (front == null) rear = null;
return item;
}
public void display() {
Node current = front;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
*Deque(데크): 양쪽에서 요소를 넣거나 꺼낼 수 있는 큐
- 이중 연결 리스트 기반
- 양방향 탐색, 텍스트 편집기의 커서 구현, 운영체제의 슬라이딩 윈도우나 캐시 등
class Node {
int data;
Node prev, next;
Node(int data) { this.data = data; }
}
public class LinkedListDeque {
private Node front, rear;
public void pushFront(int item) {
Node newNode = new Node(item);
if (front == null) {
front = rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
}
public void pushBack(int item) {
Node newNode = new Node(item);
if (rear == null) {
front = rear = newNode;
} else {
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
}
public Integer popFront() {
if (front == null) {
System.out.println("Deque is empty");
return null;
}
int item = front.data;
front = front.next;
if (front == null) rear = null;
else front.prev = null;
return item;
}
public Integer popBack() {
if (rear == null) {
System.out.println("Deque is empty");
return null;
}
int item = rear.data;
rear = rear.prev;
if (rear == null) front = null;
else rear.next = null;
return item;
}
public Integer peekFront() {
return (front != null) ? front.data : null;
}
public Integer peekBack() {
return (rear != null) ? rear.data : null;
}
}
< 섹션 4. 트리 >
*이진트리 (4가지 순회 방식)
[1]
/ \
[2] [3]
/ \ / \
[4] [5] [6] [7]
1) Preorder: 1 2 4 5 3 6 7
트리 구조 자체를 복제하거나 저장할 때 유용
- 방식: print - left - right
2) Inorder: 4 2 5 1 6 3 7
'이진 탐색 트리'에서 오름차순 정렬된 결과를 얻을 때 사용
- 방식: left - print - right
3) Postorder: 4 5 2 6 7 3 1
하위 노드부터 삭제가 필요한 상황 (트리 전체 삭제 등)
- 방식: left - right - print
4) Level Order: 1 2 3 4 5 6 7
트리를 깊이별로 순회할 필요가 있을 때 사용 (최단경로 탐색 등)
import java.util.*;
class Node {
int value;
Node left, right;
Node(int val) {
value = val;
left = right = null;
}
}
public class BinaryTreeTraversal {
static void preorder(Node node) {
if (node != null) {
System.out.print(node.value + " ");
preorder(node.left);
preorder(node.right);
}
}
static void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.print(node.value + " ");
inorder(node.right);
}
}
static void postorder(Node node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.print(node.value + " ");
}
}
static void levelorder(Node node) {
if (node == null) return;
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.print(current.value + " ");
// Current Node
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
}
}
**이진 탐색 트리(BST, Inorder 방식 이진 트리)
값들을 정렬된 방식으로 저장해두어, 이후 원하는 값을 빠르게 탐색할 수 있음
- 한 노드가 최대 2개의 자식 노드를 가질 수 있는 구조
- 각 노드의 값은 왼쪽 자식보다 크고 오른쪽 자식 값보다 작음
*이진 트리 시간 복잡도
- 검색, 삽입, 제거: O(log n)
cf) 'log n' 시간 복잡도란 데이터의 수에 비례하지만 데이터 수 증가에 비해 탐색 횟수는 적게 증가 (Ex> 사전에서 단어 찾기)
cf) 제거 시에는 트리가 끊기는 것을 방지하기 위해 해당 노드의 오른쪽에 있는 자손들 중 가장 작은 값으로 대체
class Node {
int value;
Node left, right;
Node(int val) {
value = val;
left = right = null;
}
}
public class BST {
Node insert(Node node, int val) {
if (node == null) return new Node(val);
if (val < node.value)
node.left = insert(node.left, val);
else if (val > node.value)
node.right = insert(node.right, val);
return node;
}
Node search(Node node, int val) {
if (node == null || node.value == val) return node;
if (val < node.value)
return search(node.left, val);
else
return search(node.right, val);
}
Node minValueNode(Node node) {
while (node.left != null)
node = node.left;
return node;
}
Node delete(Node node, int val) {
if (node == null) return node;
if (val < node.value)
node.left = delete(node.left, val);
else if (val > node.value)
node.right = delete(node.right, val);
else {
if (node.left == null) return node.right;
if (node.right == null) return node.left;
Node temp = minValueNode(node.right);
node.value = temp.value;
node.right = delete(node.right, temp.value);
}
return node;
}
void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.print(node.value + " ");
inorder(node.right);
}
}
public static void main(String[] args) {
BST tree = new BST();
Node root = null;
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int val : values)
root = tree.insert(root, val);
System.out.println("Inorder before deletion:");
tree.inorder(root);
// 20 30 40 50 60 70 80
root = tree.delete(root, 30);
System.out.println("\nInorder after deleting 50:");
tree.inorder(root);
// 20 40 50 60 70 80
System.out.println("Search 70:");
System.out.println(tree.search(root, 70).value);
// 70
}
}
*이진 탐색 트리 단점 (극단적으로 치우칠 경우)
어떤 순서로 값들이 삽입되느냐에 따라 검색 성능이 크게 달라짐 (Ex> 오름차순, 내림차순 정렬의 경우 시간 복잡도가 사실상 O(n)이 되어버림)
**AVL 트리 (Adelson-Velsky and Landis tree)
트리에 불균형이 발생할 때마다 노드의 배치를 조정(회전)하여 균형을 유지해주는 트리
- 노드마다 '높이(level 값)'과 '균형 인자' 값이 존재
- 균형 인자 값: '왼쪽 자식의 높이' - '오른쪽 자식의 높이')
- 트리에 값을 넣거나 빼는 과정에서 한 쪽이 다른 쪽보다 '2 레벨' 이상 크거나 작으면 노드들을 옮겨붙여 균형을 맞춰줌 (균형 인자 값으로 -1, 0, 1 만 허용됨)
- LL 회전: 왼쪽이 2레벨 더 깊을 경우 오른쪽으로 회전
- RR 회전: 오른쪽의 오른쪽 자식 때문에 하는 왼쪽으로의 회전
- LR 회전: 왼쪽 자식의 오른쪽 자식때문에 발생하는 회전으로 총 2번 회전 발생(최하위 노드가 왼쪽으로 회전 후 오른쪽으로 회전)
- RL 회전: 오른쪽의 왼쪽 자식에 의해 발생하는 불균형으로 총 2번 회전 발생(오른쪽으로 회전 후 왼쪽으로 회전)
- 값의 추가 및 삭제 시에 높이를 구하는 로직과 균형 작업이 이뤄짐
**Red-Black 트리
*Red-Black 트리 특징 6가지
1) 모든 노드들은 검정 혹은 빨강
2) 루트는 검정
3) 리프들의 자식들인 빈노드들도 모두 검정
4) 새 노드들은 빨강으로 추가
5) 빨강의 자식은 검정
6) 어떤 노드에서 리프까지 가능 경로는 모두 같은 개수의 검정 노드를 지남
- Red-Black 트리는 위 규칙들을기준으로 하여, 이에 어긋날 대마다 회전 및 색 바꿈을 통해 적당히 느슨한 균형을 유지
*레드 블랙 트리는 원리가 복잡하므로 이를 완전히 이해하려고 하기보다는 이런 식의 흐름이구나 정도로만 이해하는게 바람직
*레드 블랙 트리의 구현 중 간결한 편인 LLRB Tree(Left-Leaning Red-Black Tree)를 기준으로 이해함
**Heap(우선순위 큐)
1) Min Heap: 부모가 자식들보다 작은 값을 갖는 트리
2) Max Heap: 부모가 자식들보다 큰 값을 갖는 트리
*힙의 특징
- 완전 이진 트리 구조
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워짐
- 같은 레벨의 노드끼리는 크고 작음이 상관 없음
- 순서가 아닌 값의 크기를 기준으로 요소들을 꺼낼 수 있는 '우선순위 큐'의 구현에 사용됨
- 힙 구현에는 'ArrayList'가 사용됨
*구현 예시
import java.util.ArrayList;
import java.util.List;
public class MinHeap {
private List<Integer> heap;
public MinHeap() {
heap = new ArrayList<>();
}
private void heapifyUp(int index) {
int parent = (index - 1) / 2;
if (index > 0 &&
heap.get(index) < heap.get(parent)) {
swap(index, parent);
heapifyUp(parent);
}
}
private void swap(int i, int j) {
int tmp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, tmp);
}
private void heapifyDown(int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
int size = heap.size();
if (left < size &&
heap.get(left) < heap.get(smallest)) {
smallest = left;
}
if (right < size &&
heap.get(right) < heap.get(smallest)) {
smallest = right;
}
if (smallest != index) {
swap(index, smallest);
heapifyDown(smallest);
}
}
public void buildHeap(List<Integer> arr) {
heap = new ArrayList<>(arr);
for (int i = (heap.size() / 2) - 1; i >= 0; i--) {
heapifyDown(i);
}
}
public void insert(int val) {
heap.add(val);
heapifyUp(heap.size() - 1);
}
public Integer removeMin() {
if (heap.isEmpty()) return null;
int min = heap.get(0);
int last = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, last);
heapifyDown(0);
}
return min;
}
public Integer getMin() {
if (heap.isEmpty()) return null;
return heap.get(0);
}
public static void main(String[] args) {
MinHeap heap = new MinHeap();
List<Integer> arr = List.of(5, 3, 8, 4, 1, 2);
heap.buildHeap(arr);
System.out.println(heap.heap);
// [1, 3, 2, 4, 5, 8]
heap.insert(6);
System.out.println(heap.heap);
// [1, 3, 2, 4, 5, 8, 6]
System.out.println(heap.getMin()); // 1
System.out.println(heap.removeMin()); // 1
System.out.println(heap.heap);
// [2, 3, 6, 4, 5, 8]
}
}
< 섹션 5. 정렬 알고리즘 >
1) 버블 정렬(Bubble Sort): 시간 복잡도 O(n2) / 공간 복잡도 O(1)
첫번째 요소부터 다음 인덱스의 요소와 비교하여 더 크면 스왑하는 정렬 방식
- 구현은 쉽지만 효율이 떨어져 실무에서 사용 X
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] data = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
} // Sorted array: 11 12 22 25 34 64 90
}
}
2) 선택 정렬(Selection Sort): O(n2) / O(1)
첫번째 요소부터 순서대로 순회하며 최소값을 찾고 스왑하는 정렬 방식
- 배열의 상태와 상관없이 배열의 크기마다 같은 수의 연산을 소모
- 구현은 쉽지만 효율이 떨어져 실무에서 사용 X
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] data = {29, 10, 14, 37, 13};
selectionSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
} // Sorted array: 10 13 14 29 37
}
}
3) 삽입 정렬(Insertion Sort): O(n2) / O(1)
첫번째 요소부터 요소를 하나씩 추가해가며 정렬된 부분을 늘려가는 정렬 방식
- 탐색을 제외한 오버헤드가 적고, 배열의 크기가 작을수록 효율적
- 거의 정렬된 데이터에 효율적이지만 일반적인 경우에는 느려 대규모 정렬에는 부적합
public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] data = {5, 3, 4, 1, 2};
insertionSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 1 2 3 4 5
}
}
4) 합병 정렬(Merge Sort): O(n log n) / O(n)
배열을 쪼갤 수 없을 때까지 재귀적으로 반으로 나누고 다시 합치는 과정에서 정렬
- 분할 정복 기법을 사용한 효율적인 정렬 알고리즘
- 값이 같은 원소의 순서를 유지하는 '안전 정렬'
- 항상 'n lon n'의 안정적인 시간 복잡도를 가지며 데이터가 정렬되어 있지 않아도 성능이 일관적이므로, 큰데이터를 안정적으로 정렬해야 하거나 외부 저장장치와 함께 작업할 때 사용
*구현 예시
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int t = 0; t < temp.length; t++) {
arr[left + t] = temp[t];
}
}
public static void main(String[] args) {
int[] data = {38, 27, 43, 3, 9, 82, 10};
mergeSort(data, 0, data.length - 1);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 3 9 10 27 38 43 82
}
}
5) 퀵 정렬(Quick Sort): O(n log n) / O(log n)
피벗 요소를 기준으로 작은 값들의 그룹과 큰 값들의 그룹으로 나눈 다음 피벗을 그 가운데로 넣어준 뒤 두 그룹에 대해 재귀적으로 이를 반복하는 방식의 정렬 방법
- 재귀를 통한 분할 정복 전략을 사용하며 평균적으로 빠른 정렬 속도를 가지며 추가적인 메모리 사용이 적은 고성능 정렬
- 정렬 단계 시작 시 선택한 '피벗'이 요소들의 크기 중 가운데에 가까울수록 성능이 잘 나옴
- 최악의 경우를 피하기 위한 피벗 선택 전략이 중요 (중간값을 먼저 찾아 피벗으로 삼는 변형도 존재)
- 대용량 데이터에서 빠른 정렬이 필요하고 추가 메모리 사용을 최소화해야 할 때 사용
*구현 예시
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] data = {10, 7, 8, 9, 1, 5};
quickSort(data, 0, data.length - 1);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 1 5 7 8 9 10
}
}
6) 힙 정렬(Heap Sort): O(n log n) / O(1)
힙의 조건에 맞게 배열을 구성한 다음 루트 값을 차례대로 추출하는 방식의 정렬 방법
- 최대힙: 오름차순 정렬 & 최소힙: 내림차순 정렬
- 원소 접근이 불규칙하고 메모리 지역성이 낮아 캐시 효율성이 떨어지므로 실무에서 퀵 정렬보다 적게 사용됨
*구현 예시
public class HeapSort {
public static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] data = {12, 11, 13, 5, 6, 7};
heapSort(data);
System.out.print("Sorted array: ");
for (int num : data) {
System.out.print(num + " ");
}
// Sorted array: 5 6 7 11 12 13
}
}
7) 이진 탐색(Binary Search): O(log n) / O(1)
정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘으로 탐색 범위를 반으로 쪼개나가며 값을 찾는 방식
*구현 예시
public class BinarySearchIterative {
public static int binarySearchIter(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10, 12};
int target = 10;
System.out.println(binarySearchIter(arr, target)); // 4
}
}
< 섹션 6. Hash Map >
*해시 맵 (Hash Map)
데이터를 '키'와 '값'의 쌍으로 저장하는 자료구조
- 데이터를 빠르게 검색하거나 저장할 때 사용
- 내부적으로 해시 함수를 이용해 데이터를 저장할 인덱스 계산
- 같은 인덱스에 값이 중복되어 저장되는 것을 방지하기 위해 2가지 방식이 존재: Chaining, Open Addressing
1. Chaining 방식 해시 맵
동일한 인덱스 값을 가지는 여러 값이 있을 경우 '연결 리스트 방식'으로 복수의 값들을 같은 자리에 저장
*장/단점
- 장점: 충돌이 많아도 각 슬롯에 여러 항목을 저장할 수 있어 해시맵 전체가 가득 차는 문제가 발생하지 않음
- 단점: 충돌이 많으면 슬롯 내 리스트 탐색이 필요하므로 검색 성능이 저하됨
*구현 예시
public class HashMapChaining {
private static class Entry {
String key;
int value;
Entry(String key, int value) {
this.key = key;
this.value = value;
}
}
private List<Entry>[] table;
private int size;
@SuppressWarnings("unchecked")
public HashMapChaining(int size) {
this.size = size;
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>();
}
}
private int hash(String key) {
return Math.abs(key.hashCode()) % size;
}
public void put(String key, int value) {
int index = hash(key);
for (Entry e : table[index]) {
if (e.key.equals(key)) {
e.value = value; // Update
return;
}
}
table[index].add(new Entry(key, value)); // Insert
}
public Integer get(String key) {
int index = hash(key);
for (Entry e : table[index]) {
if (e.key.equals(key)) {
return e.value;
}
}
return null;
}
public void remove(String key) {
int index = hash(key);
Iterator<Entry> it = table[index].iterator();
while (it.hasNext()) {
if (it.next().key.equals(key)) {
it.remove();
return;
}
}
}
public static void main(String[] args) {
HashMapChaining hm = new HashMapChaining(5);
hm.put("apple", 10);
hm.put("banana", 20);
hm.put("apple", 30);
System.out.println(hm.get("apple")); // 30
hm.remove("banana");
System.out.println(hm.get("banana")); // null
}
}
2. Open Addressing 방식 해시 맵
동일한 인덱스 값을 가지는 여러 값이 있을 경우 다른 빈 자리를 찾아 엔트리를 삽입하는 방식 사용
- 다음으로 오는 자리들 중 첫 빈 자리를 찾아 엔트리 삽입
*장/단점
- 장점: 모든 데이터가 배열 내에 저장되어 메모리 접근 및 캐시 효율이 높음
- 단점: 테이블이 가득 차면 삽입이 불가능하고 삭제 처리와 재해싱 관리가 복잡해짐
*구현 예시
public class HashMapOpenAddressing {
private static class Entry {
String key;
int value;
Entry(String key, int value) {
this.key = key;
this.value = value;
}
}
private Entry[] table;
private int size;
private final Entry DELETED = new Entry("<deleted>", 0);
public HashMapOpenAddressing(int size) {
this.size = size;
table = new Entry[size];
}
private int hash(String key) {
return Math.abs(key.hashCode()) % size;
}
public void put(String key, int value) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null || entry == DELETED) {
table[idx] = new Entry(key, value);
return;
}
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
}
public Integer get(String key) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null) return null;
if (entry != DELETED && entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
public void remove(String key) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null) return;
if (entry != DELETED && entry.key.equals(key)) {
table[idx] = DELETED;
return;
}
}
}
public static void main(String[] args) {
HashMapOpenAddressing hm = new HashMapOpenAddressing(8);
hm.put("apple", 10);
hm.put("banana", 20);
hm.put("apple", 30);
System.out.println(hm.get("apple")); // 30
hm.remove("banana");
System.out.println(hm.get("banana")); // null
}
}
< 섹션 7. Graph >
*그래프 (Graph)
'vertex'와 'edge'로 구성된 비선형 자료구조로 다야한 현실 세계의 문제를 모델링하는 데 사용
*그래프 관련 용어 정리
- vertex: 노드
- edge: 두 노드 간의 연결, 리스트 또는 행렬 방식으로 나타낼 수 있음
- edge weight: 노드 간 거리, 이동을 위한 비용이나 소요시간 등 엣지 자체에 부여되는 어떤 값
- Adjacency List(인접 리스트): 그래프의 각 정점(Vertex)에 인접한 정점들을 연결 리스트나 배열벡터 등으로 목록화하여 연결 관계를 표현하는 방식
cf) 인접 리스트는 실제 연결된 간선만 저장하여 희소 그래프(sparse graph)에서 메모리를 절약하기 때문에 인접 행렬보다 공간 효율성이 좋음
*인접 리스트 방식의 그래프 구현 예시
class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
public class Graph {
private boolean directed;
private Map<Integer, List<Edge>> adjList;
public Graph(boolean directed) {
this.directed = directed;
adjList = new HashMap<>();
}
public void addEdge(int src, int dest, int weight) {
adjList.putIfAbsent(src, new ArrayList<>());
adjList.get(src).add(new Edge(dest, weight));
if (!directed) {
adjList.putIfAbsent(dest, new ArrayList<>());
adjList.get(dest).add(new Edge(src, weight));
}
}
public void printGraph() {
for (int node : adjList.keySet()) {
System.out.print(node + " -> ");
for (Edge edge : adjList.get(node)) {
System.out.print("(" + edge.dest + ", " + edge.weight + ") ");
}
System.out.println();
}
}
public static void main(String[] args) {
System.out.println("Undirected, unweighted:");
Graph g1 = new Graph(false);
g1.addEdge(0, 1, 1);
g1.addEdge(0, 2, 1);
g1.printGraph();
// 0 -> (1, 1) (2, 1)
// 1 -> (0, 1)
// 2 -> (0, 1)
System.out.println("\nDirected, weighted:");
Graph g2 = new Graph(true);
g2.addEdge(0, 1, 4);
g2.addEdge(1, 2, 5);
g2.printGraph();
// 0 -> (1, 4)
// 1 -> (2, 5)
}
}
*인접 행렬 방식의 그래프 구현 예시
public class Graph {
private boolean directed;
private int[][] matrix;
private int V;
public Graph(int numVertices, boolean directed) {
this.directed = directed;
this.V = numVertices;
matrix = new int[V][V];
}
public void addEdge(int src, int dest, int weight) {
matrix[src][dest] = weight;
if (!directed) {
matrix[dest][src] = weight;
}
}
public void printGraph() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
System.out.println("Undirected, unweighted:");
Graph g1 = new Graph(3, false);
g1.addEdge(0, 1, 1);
g1.addEdge(0, 2, 1);
g1.printGraph();
// 0 1 1
// 1 0 0
// 1 0 0
System.out.println("\nDirected, weighted:");
Graph g2 = new Graph(3, true);
g2.addEdge(0, 1, 4);
g2.addEdge(1, 2, 5);
g2.printGraph();
// 0 4 0
// 0 0 5
// 0 0 0
}
}
**DFS(Depth-First Search, 깊이 우선 탐색)
한 방향으로 깊게 탐색하다가 더 이상 갈 수 없을 때 다시 돌아가 다른 경로를 탐색하는 방식
- 시간 복잡도 / 공간 복잡도: O(V+E) / O(V)
- V = Vertex: 노드, E = Edge: 엣지
- 경로 탐색에 유리: 트리 구조 순회, 사이클 탐지, 백트래킹 문제
*탐색 방법
Stack(스택) 또는 재귀 방식을 사용
- 첫 방문 노드를 목적지 스택에 넣은 뒤 바로 제거하면서 탐색
*DFS 구현 방법
직접적으로 스택이 사용되지는 않지만 함수가 함수를 호출하는 과정에서 스택이 사용이 되므로 재귀를 사용함으로써 큰 그림에서 스택을 적용하여 구현
**BFS(Breadth-First Search, 너비 우선 탐색)
시작 노드로부터 가까운 노드부터 차례로 탐색하는 방식
- 시간 복잡도 / 공간 복잡도: O(V+E) / O(V)
- 가중치가 없는 그래프에서 최단 경로를 탐색하는데 유리: 최단 거리, 미로 문제, 네트워크 전파 문제
*탐색 방법
Queue(큐)를 사용
- 첫 방문노드를 목저지 큐에 넣은 뒤 바로 제거하면서 탐색
*DFS / BFS 구현 방법
import java.util.*;
public class Graph {
private int V;
private List<List<Integer>> adj;
public Graph(int vertices) {
V = vertices;
adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
}
public void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u);
}
public void dfs(int start) {
boolean[] visited = new boolean[V];
dfsVisit(start, visited);
System.out.println();
}
private void dfsVisit(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int neighbor : adj.get(v)) {
if (!visited[neighbor])
dfsVisit(neighbor, visited);
}
}
public void bfs(int start) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int neighbor : adj.get(v)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
public static void main(String[] args) {
Graph g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
System.out.println("DFS:");
g.dfs(0); // 0 1 3 4 2
System.out.println("BFS:");
g.bfs(0); // 0 1 2 3 4
}
}
**그래프의 최단 경로 알고리즘
그래프에서 한 정점에서 다른 정점까지 이동할 때 가장 짧은 경로를 찾는 알고리즘
1. Dijkstra (다익스트라)
2. Floyd-Warshall (플로이드 워셜)
3. Bellman-Ford (벨만 포드)
< Dijkstra (다익스트라) 알고리즘 >
가능한 모든 길을 다 가본 뒤 각각 가장 짧았던 거리를 기록
- 기존에 찾았던 경로보다 더 짧은 경로를 발견할 때마다 업데이트해 주는 방식
- 시간 복잡도 / 공간 복잡도: O(V^2) / O(V)
- 가중치가 음수가 아닌 그래프에서, 하나의 시작점에서 모든 정점까지 최단 거리를 찾는데 유용하게 사용
*구현 예시
public class DijkstraArray {
static int[] dijkstra(int[][][] graph, int start) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
// '거리'가 짧은 쌍부터 빠져나오는 우선순위 큐
// int[]: {거리, 도착노드}
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue;
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}}}
return dist;
}
public static void main(String[] args) {
int[][][] graph = new int[6][][];
graph[0] = new int[][]{{1, 2}, {2, 5}};
graph[1] = new int[][]{{0, 2}, {2, 4}, {3, 6}};
graph[2] = new int[][]{{0, 5}, {1, 4}, {3, 2}, {4, 1}};
graph[3] = new int[][]{{1, 6}, {2, 2}, {5, 3}};
graph[4] = new int[][]{{2, 1}, {5, 1}};
graph[5] = new int[][]{{3, 3}, {4, 1}};
int[] dist = dijkstra(graph, 0);
System.out.println(Arrays.toString(dist));
// [0, 2, 5, 7, 6, 7]
}
}
< Floyd-Warshall (플로이드 워셜) 알고리즘 >
그래프의 모든 노드 쌍에 제 3의 노드를 더해봄으로써 모든 정점 간 최단 거리를 구함
- 시간 복잡도 / 공간 복잡도: O(V^3) / O(V^2)
- 시간 복잡도가 높게 나오지만 시작점 하나가 아닌 그래프 전체의 최단 거리 정보를 모두 구하는 것이므로 정적 그래프 분석에는 효율적
- 음수 가중치를 허용하지만 음수 사이클은 감지 못함
*구현 예시
public class FloydWarshall {
static final int INF = 100000;
static int[][] floydWarshall(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++)
dist[i] = Arrays.copyOf(graph[i], n);
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
return dist;
}
public static void main(String[] args) {
int INF = 100000;
int[][] graph = {
{0, 3, INF, 7},
{8, 0, 2, INF},
{5, INF, 0, 1},
{2, INF, INF, 0}
};
int[][] result = floydWarshall(graph);
for (int[] row : result)
System.out.println(Arrays.toString(row));
// [0, 3, 5, 6]
// [5, 0, 2, 3]
// [3, 6, 0, 1]
// [2, 5, 7, 0]
}
}
< Bellman-Ford (벨만 포드) 알고리즘 >
한 지점에서 시작하여 매번 모든 간선을 확인하며 거리를 갱신하는 알고리즘
- 시간 복잡도 / 공간 복잡도: O(VXE) / O(V)
- 사이클(Iteration)의 최대 횟수는 노드 수보다 하나 적은 값
- 다익스트라에 비해 속도는 느리지만 음수 사이클을 탐지할 수 있어 더 범용적인 알고리즘
- '음수 사이클(음수 가중치들의 크기의 합이 양수 가중치들의 크기의 합보다 큰 경우)'은 실제 응용에서 무한 이득이나 무한 손실 등으로 이어질 수 있는 비정상적인 상황
*구현 예시
class BellmanFord {
static int[] bellmanFord(int n, int[][] edges, int start) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 0; i < n - 1; i++)
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE &&
dist[e[0]] + e[2] < dist[e[1]])
dist[e[1]] = dist[e[0]] + e[2];
// 음수 사이클 탐지
for (int[] e : edges)
if (dist[e[0]] != Integer.MAX_VALUE &&
dist[e[0]] + e[2] < dist[e[1]])
return null; // Negative cycle
return dist;
}
public static void main(String[] args) {
int[][] edges = {
{0, 1, 6}, {0, 2, 7},
{1, 2, 8}, {1, 3, 5},
{1, 4, -4}, {2, 3, -3},
{4, 3, 9}
};
int[] dist = bellmanFord(5, edges, 0);
System.out.println(Arrays.toString(dist));
// [0, 6, 7, 4, 2]
}
}
*최소 신장 트리(Minimum Spanning Trees)
그래프에서 모든 노드를 최소한의 간선 비용으로 연결하는 트리
(Ex> 통신망, 도로망 최적화, 네트워크 구축, 전력망 설계)
- 현존하는 엣지들을 활용하여 모든 정점을 연결하면서 사이클이 없고 간선의 가중치 합이 가장 작은 서브 그래프를 만드는데 사용되는 자료구조
- 사이클이 없는 그래프는 트리의 형태로 펼칠 수 있음
*최소 신장 트리를 구하는 알고리즘
- Kruskal 알고리즘
- Prim 알고리즘
1. Kruskal 알고리즘
매 단계에서 가장 비용이 적은 선택을 반복하면서 전체 최적 해답을 향해 나아가는 알고리즘
- 가중치가 낮은 엣지부터 사이클이 만들어지지 않도록 확인하며 트리에 추가하는 방식
- 간선 수가 적고, 전체 그래프가 흩어져 있거나 간선 중심적일 때 효율적
- 시간 복잡도 / 공간 복잡도: O(E log E) / O(V)
*구현 예시
public class KruskalExample {
static int N = 4; // number of vertices
// 출발지, 도착지, 가중치
static int[][] edges = {
{0, 1, 1},
{0, 2, 4},
{1, 2, 2},
{1, 3, 6},
{2, 3, 3}
};
static int[] parent = new int[N];
static int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int x, int y) {
int xRoot = find(x), yRoot = find(y);
if (xRoot != yRoot) {
parent[yRoot] = xRoot;
return true;
}
return false;
}
public static void main(String[] args) {
for (int i = 0; i < N; i++)
parent[i] = i;
// 엣지들의 배열을 가중치 기준으로 오름차순 정렬
Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
int mstWeight = 0;
for (int[] edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
if (union(u, v))
mstWeight += w;
}
System.out.println("MST Weight: " + mstWeight);
// MST Weight: 6
}
}
2. Prim 알고리즘
뻗어나갈 수 있는 길들 중 가장 짧은 곳부터 가는 알고리즘
- 연결되어 있는 엣지들 중 가장 작은 가중치를 가진 것을 택하여 이동하는 것을 반복 (우선순위 큐 사용)
- 정점 수가 적고, 간선이 촘촘한 밀집 그래프에서 유리
- 시간 복잡도 / 공간 복잡도: O(E log V) / O(V)
*구현예시
public class PrimExample {
static int N = 4; // number of vertices
static List<int[]>[] graph = new ArrayList[N];
public static void main(String[] args) {
for (int i = 0; i < N; i++)
graph[i] = new ArrayList<>();
// 출발지, 도착지, 가중치
int[][] edges = {
{0, 1, 1},
{0, 2, 4},
{1, 2, 2},
{1, 3, 6},
{2, 3, 3}
};
for (int[] e : edges) {
// 방향성이 없으므로 쌍방으로 엣지들을 추가 {가중치, 목적지}
graph[e[0]].add(new int[]{e[2], e[1]});
graph[e[1]].add(new int[]{e[2], e[0]});
}
boolean[] visited = new boolean[N];
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
pq.offer(new int[]{0, 0}); // (weight, vertex)
int mstWeight = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int w = curr[0], u = curr[1];
if (visited[u]) continue;
visited[u] = true;
mstWeight += w;
for (int[] next : graph[u]) {
if (!visited[next[1]])
pq.offer(next);
}
}
System.out.println("MST Weight: " + mstWeight);
// MST Weight: 6
}
}
'Programming Languages' 카테고리의 다른 글
| React 문법 정리 (0) | 2026.05.02 |
|---|---|
| Typescript 문법 정리 (0) | 2026.04.26 |
| Kotlin 백엔드 실무 문법 정리 (0) | 2026.04.18 |
댓글