Arrays.sort, Collections.sort, 커스텀 Comparator, 객체 정렬까지 정렬의 모든 것을 정리했습니다. 1️⃣ 기본 정렬 🔹 1-1. 기본 배열 정렬 (Arrays.sort) 기본형 배열은 Dual-Pivot Quicksort 사용 (평균 O(N log N)) 참조형 배열은 TimSort 사용 (O(N log N)...
[알고리즘] 최소 신장 트리(MST) : 크루스칼 알고리즘, 프림 알고리즘
최소 신장 트리(MST)의 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘에 대해 공부 후 정리하였습니다. 1. 최소 신장 트리 (MST: Minimum Spanning Tree) 1️⃣ 개념 신장 트리(Spanning Tree) 그래프의 모든 정점을 포함 간선 수 = 정점 수 - 1 사...
[알고리즘] 유니온 파인드 (Union-Find)
유니온 파인드(Union-Find) 알고리즘에 대해 공부 후 정리하였습니다. 유니온 파인드 (Union Find) 1️⃣ 개념 서로소 집합(Disjoint Set) 을 관리하는 자료구조 두 노드가 같은 집합에 속하는지 판별하거나, 두 집합을 합치는 연산을 효율적으로 수행 주로 그래프의 연결 관계 관리에 사용 (예: 크루스칼 MST) 2️⃣ 주요...
[알고리즘] 위상 정렬(Topological Sort)
위상 정렬(Topological Sort)에 대해 공부 후 정리하였습니다. 위상 정렬 (Topological Sort) 1️⃣ 개념 방향 그래프에서 사이클이 없는 경우(DAG), 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 알고리즘 간선 (u → v)가 있으면 정렬 결과에서 u가 반드시 v보다 앞에 나와야 함 주로 선행 조건...
[알고리즘] 투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window)
투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 대해 공부 후 정리하였습니다. 1. 투 포인터 (Two Pointers) 1️⃣ 개념 두 개의 포인터(인덱스)를 이용해 배열이나 리스트를 한 번에 탐색하는 방식입니다. 이분 탐색으로 투 포인터 문제를 풀 수 있는 경우가 많고, 투 포인터로 이분 탐색 문제를 풀 수...
[알고리즘] 이분 탐색(Binary Search), 매개변수 탐색(Parametric Search)
이분 탐색(Binary Search)과 매개변수 탐색(Parametric Search)에 대해 공부 후 정리하였습니다. 1. 이분 탐색 (Binary Search) 추가할 내용 주의 사항 : 무한루프 주의 - start와 end가 1차이날 때 주의깊게 확인 (start+end+1)/2 정렬되어야 함 응용 문제 : 해당 타겟이 몇 개 ...
[알고리즘] 백트래킹(Backtracking)
백트래킹(Backtracking)에 대해 공부 후 정리하였습니다. Summary 백트래킹은 완전탐색을 효율적으로 줄이는 기법 DFS + Pruning 구조로 구현 시간복잡도는 최악은 지수적이지만, 가지치기로 충분히 줄어듦 코딩테스트에서 순열, 조합, 스도쿠, N-Queens, 경로 탐색 등에 많이 등장 ...
[알고리즘] 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)
너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)에 대해 공부 후 정리하였습니다. Summary - BFS 그래프나 트리에서 가까운 정점부터 너비를 우선으로 탐색하는 알고리즘 큐(Queue)를 사용하여 구현 문제에 따라 다르지만 그래프의 경우 O(V + E), 2차원 배열의 경우 O(NM) 최단 거리 탐색,...
[알고리즘] 재귀 (Recursion)
재귀에 대해 공부 후 정리하였습니다. Summary 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법 종료 조건(기저 조건)이 반드시 필요하며, 함수 호출 스택을 사용 문제에 따라 다르지만 보통 O(분기^깊이) 분할정복, 백트래킹, DFS/BFS, 수학적 정의(팩토리얼, 피보나치 등) 등에 많이 사용 ...
[알고리즘] 순열, 조합, 부분 집합
순열, 조합, 부분 집합에 대해 공부 후 정리하였습니다. 1. 순열 (Permutation) 설명: 서로 다른 n개 중에서 r개를 순서 있게 뽑는 경우 시간 복잡도: O(n!) public class Permutation { static int n = 3; static int r = 3; static int[] a...