String, StringBuffer, StringBuilder의 차이에 대해 정리했습니다. 1️⃣ String 개념 문자열을 불변(Immutable) 객체로 관리 특징 한 번 생성되면 값이 변경되지 않음 불변이므로 +, concat() 등으로 수정 시 새 객체를 생성 속도 느려짐과 메모리 낭비 가능성 있음 문자열 리터럴은 ...
[알고리즘] 플로이드 워셜(Floyd-Warshall)
플로이드 워셜(Floyd-Warshall)에 대해 공부 후 정리하였습니다. 1️⃣ 개념 다이나믹 프로그래밍 기반의 최단 경로 알고리즘으로 그래프 내 모든 정점 쌍 (i, j) 사이의 최단 거리를 구함. 다익스트라가 한 정점에서 출발하는 최단 경로를 구하는 것과 달리, 플로이드-워셜은 전체 쌍을 고려한다. 음수 가중치 간선도 허용(단, 음수 사이클...
[알고리즘] 다익스트라 알고리즘 (Dijkstra)
다익스트라(Dijkstra) 알고리즘에 대해 공부 후 정리하였습니다. 다익스트라 알고리즘 1️⃣ 개념 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 BFS의 가중치 버전이라고 생각 가능 (BFS는 모든 간선 가중치가 1일 때 다익스트라와 동일) 2️⃣ 특징 Greedy + DP 성격을 ...
[알고리즘] 동적 계획법(DP: Dynamic Programming)
동적 계획법(DP) 알고리즘에 대해 공부 후 정리하였습니다. 동적 계획법(DP: Dynamic Programming) 1️⃣ DP란? 큰 문제를 작은 문제로 나누고, 중복되는 작은 문제를 한 번만 풀어서 그 결과를 저장해두고 재사용하여 전체 문제를 해결하는 기법입니다. 2️⃣ DP의 핵심 조건 (2가지) 중복 부분 문제 (Overlappi...
[Java] 기본 정렬 메소드와 객체 정렬
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 정렬되어야 함 응용 문제 : 해당 타겟이 몇 개 ...