알고리즘/이론

int[] copy = arr 는 배열 값을 복사하는 것이 아니라, 주소값을 복사하는 것이기 때문에 둘 중 하나를 변경하게 되면 → 다른 값 또한 변경 됨 이렇게 주소 값만 복사하는 것을 Shallow Clone 값을 복사하여 다른 객체를 만드는 것을 Deep Clone 여기서 ✅ System.arraycopy() → Shallow Clone clone() → Deep Clone

Prim's Algorithm 이란 Prim's Algorithm은 무향 연결 그래프가 주어질 때, 최소 비용 신장 트리 을 찾는 알고리즘 Prim's Algorithm 동작 1️⃣ 임의의 node ( 시작 정점 )을 선택하여 MST ( 최소 비용 신장 트리 ) 집합에 추가 2️⃣ 인접 node 중 최소 비용의 edge로 연결된 node 선택 👉 이 과정을 모든 node를 선택할 때 까지 반복 ‼️ Prim's Algorithm 시간 복잡도 주 반복문이 node의 수 n번 반복 ❌ 내부 반복문이 n번 반복 👉 시간 복잡도는 O(n^2)

TreeMap 이란 ? TreeMap 은 이진트리를 기반으로 한 Map 컬렉션이다. 정렬 순서는 기본적으로 부모 키 값과 비교해서 작은 것은 왼쪽 자식 노드에, 큰 것은 오른쪽 자식 노드에 객체를 저장한다. Map으로써의 성능이 HashMap보다 떨어지지만, 정렬된 상태로 Map유지해야 하거나 정렬된 테이터를 조회해야하는 범위 검색이 필요한 경우에는 효율성이 좋다. 레드 - 블랙 트리 (Red - Black Tree) TreeMap은 레드 - 블랙 트리로 이루어져 있다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요하다. 만약 데이터가 입력될 때, 값이 한쪽으로 편향되게 들어올 경우 크게 치우쳐진 트리가 되어서 굉장히 비효율적이다. 이러한 문제를 보완하기 위한 것이 Red - Black Tree

Parametric Search 란? 최적화 문제 (문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제 ( decision problem )으로 바꾸어 푸는 것 파라메트릭 서치는 문제를 풀어나가는 과정이 바이너리 서치 ( 이분 탐색 ) 과 매우 흡사하다. ➡️ 의외의 문제들에 적용되어서 최적화 문제들을 조금 더 쉽게 풀 수 있게 해준다. 핵심은 결정 문제 👉 해당값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야 최적화 문제를 파라메트릭 서치로 풀 수 있다. 👉 정답이 될 수 있는 값들이 연속적이여야 파라메트릭 서치를 이용할 수 있다. 정답이 a일 때, a 이상의 값들은 모두 조건을 만족한다는 의미시간 복잡도 시간 복잡도 알고리즘 자체보다 조건 함수가 얼마나 빠른..

Floyd-Warshall 알고리즘이란 ? Floyd-Warshall 알고리즘이란, 변의 가중치가 음이거나 양인 ( 음수 사이클은 없는 ) 가중 그래프에서 모든 최단 경로를 구하는 방법 이다. 다익스트라와 벨만포드 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 방법 이다. Dijkstra 알고리즘 정해진 출발지 vertex 에서 부터 다른 모든 vertex으로의 최단 경로를 구한다. 가장 작은 가중치를 하나씩 선택해나간다. ( 우선순위 큐 이용 ) Floyd-Warshall 알고리즘 모든 vertex 에서 모든 vertex 로의 최단 경로를 한번에 구한다. 즉, 모든 vertex 쌍의 최단 경로를 구한다. 모든 쌍을 표현하는 이차원 배열 을 선언하고, Dynamic Programmi..