Little bIT awesome

위상 정렬정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 진입차수와 진출차수진입 차수 : 특정한 노드로 들어오는 간선의 개수진출 차수 : 특정한 노드에서 나가는 간선의 개수  위상 정렬 알고리즘 동작 과정진입차수가 0인 노드를 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.① 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거② 새롭게 진입차수가 0이 된 노드를 큐에 삽입  위상 정렬의 특징사이클이 없는 방향 그래프(DAG)에 대해서만 수행할 수 있다. ※ DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래프위상 ..

- 1초 제한시간에서 일반적으로: * O(N): ~1억 * O(N²): ~1만 * O(N³): ~500 * O(N⁴): ~50  입력 크기로 판단N이 50 이하면:- O(N⁴)도 괜찮음- O(N³)은 거의 항상 가능- O(N²)은 매우 여유로움N이 1000 이하면:- O(N²)까지는 괜찮음- O(N³)은 위험N이 100,000 이하면:- O(N) 또는 O(NlogN) 정도만 가능 문제 유형으로 판단완전탐색이 필요해 보이고:- 입력크기가 매우 작으면(N≤50) → 브루트포스 가능성 높음- 특별한 제약조건이나 패턴이 없으면 → 브루트포스 가능성 높음 최단 경로- N ≤ 400: 플로이드-워셜 (O(N³))- N ≤ 20,000, E ≤ 300,000: 다익스트라 (O(ElogV))- 가중치가 1이거나..

PriorityQueue(PQ)는 내부적으로 힙 정렬을 사용 vs Collections.sort()는 내부적으로 TimeSort 사용  시간 복잡도:힙 정렬: 항상 O(n log n)Timsort: 최선 O(n), 평균 및 최악 O(n log n)공간 복잡도:힙 정렬: O(1) (제자리 정렬 가능)Timsort: O(n) (병합 과정에서 추가 공간 필요)안정성:힙 정렬: 불안정 정렬Timsort: 안정 정렬실제 성능:힙 정렬: 이론적으로는 빠르지만, 캐시 지역성이 좋지 않아 실제 성능이 떨어질 수 있음Timsort: 실제 데이터에서 자주 발견되는 패턴을 잘 활용하여 평균적으로 더 빠른 성능을 보임  Java에서 Timsort를 사용하는 이유: 적응성- Timsort는 이미 정렬된 데이터나 부분적으로 정렬..

세그먼트 트리란?세그먼트 트리는 배열과 같이 연속된 구간의 정보를 효율적으로 관리하고 쿼리를 처리하는 데 사용되는 자료구조입니다. 일반적으로 구간 합, 최솟값, 최댓값 등의 쿼리를 빠르게 처리할 수 있습니다.세그먼트 트리의 특징구간 쿼리의 빠른 처리: 세그먼트 트리는 구간 쿼리를 O(log N) 시간에 처리할 수 있습니다.동적 배열 업데이트: 배열의 특정 원소를 업데이트하는 데 O(log N) 시간이 소요됩니다.메모리 사용: 일반적으로 4N 크기의 메모리를 사용합니다(N은 배열의 크기).세그먼트 트리의 기본 구조세그먼트 트리는 트리 구조를 가지며, 각 노드는 특정 구간에 대한 정보를 저장합니다. 루트 노드는 전체 구간을 나타내고, 각 자식 노드는 구간을 절반으로 나눈 서브 구간을 나타냅니다.세그먼트 트리..

MST (Minimum Spanning Tree)그래프 이론에서 사용되며, 주어진 가중치 그래프에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 전력 배선, 클러스터링 등 다양한 분야에서 활용된다.  여러가지 MST 알고리즘이 있지만, 그 중에서도 가장 널리 사용되는 두 가지 알고리즘1. Kruskal's Algorithm (크루스칼 알고리즘)2. Prim's Algorithm (프림 알고리즘)https://littlebitawesome.tistory.com/entry/Week10-MSTMinimum-Spanning-Tree-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 [Week10] MST 알고리즘(1) - Kruskal's AlgorithmMST (Mi..

MST (Minimum Spanning Tree)그래프 이론에서 사용되며, 주어진 가중치 그래프에서 최소 비용으로 모든 정점을 연결하는 트리를 찾는 알고리즘네트워크 설계, 전력 배선, 클러스터링 등 다양한 분야에서 활용된다.  여러가지 MST 알고리즘이 있지만, 그 중에서도 가장 널리 사용되는 두 가지 알고리즘1. Kruskal's Algorithm (크루스칼 알고리즘)2. Prim's Algorithm (프림 알고리즘) Kruskal's Algorithm (크루스칼 알고리즘)기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다. 크루스칼 알고리즘을 수행하고 완성된 그래프는 최소 신장 트리이다.  크루스칼 알고리즘의 과정1. 간선 가중치 기준 정렬모든 간선을 가중치의 오름차순으로 정렬한다. 2. 최소 ..

Union-Find 알고리즘이란?서로소 집합(Disjoint-Set) 알고리즘이라고도 불리는 알고리즘여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 Disjoint-Set (서로소 집합)?서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조즉, 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조 Union-Find 알고리즘의 과정초기화 (makeSet) - 합치기 (union) - 찾기 (find) 연산 과정을 거친다 1. 초기화 (makeSet)union과 find 연산을 하기전, 각 노드를 하나의 집합으로 초기화하는 과정자기 자신이 가리키는 대상 = 자신이 속한 집합이 되기 때문에, 자..

시작 노드 고정하고 반복 돌면서 최단 거리 갱신전체 노드 수 - 1 만큼 반복하면서 최단 거리 수정(전체 노드 수 - 1) 만큼 반복하는 이유- 노드와 노드 사이의 최대 간선의 수는 최대 (전체 노드 수 - 1) 개임- 일단 반복을 돌았을 때, 거리가 갱신됐다는 것은 경로에 간선의 개수가 하나 늘었다는 것을 의미-> 최단 거리의 간선의 수가 전체 노드 수 - 1보다 높으면 음의 사이클을 돌고 있다는 것- 음의 사이클을 돌면 그냥 그 노드까지이 최단 거리를 구할 수 없음 (무한대로 수렴하기 때문에)  코드 해석 간선 edge가 있을 때edge.v = 간선의 시작edge.w = 간선의 목적지edge.cost = 간선의 가중치 dist[x] = 시작점부터 x까지의 거리  // 전체 노드 수 - 1 만큼 반복f..

1. 다익스트라 알고리즘 (Dijkstra Algorithm)다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다).  일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※ 음의 가중치를 가지면 안되는 이유는1. 최소 비용의 음의 무한대 발산 2. 그리디 알고리즘 적용 불가능 : 최적의 해를 보장할 수 없음   ※ 연결 그래프 : 모든 두 꼭..

그래프 그래프의 구성 요소 정점 간선 그래프의 방향성 방향 그래프 (Directed Graph) 무방향 그래프 (Undirected Graph, 양방향 그래프) 방향성이 없다는 것은 어느 쪽으로든 갈 수 있다는 의미이다. 그래프의 순환성 그래프 내 어떤 부분이라도 순환하는 부분이 있다면 순환 그래프, 한 군데도 없다면 비순환 그래프이다. 순환 그래프 (Cyclic Graph) 비순환 그래프 (ACyclic Graph) 그래프의 연결 요소 (Connected Component) 서로 완전히 분리된 요소들이 여럿 주어지는 그래프도 있다. 각각을 연결 요소라고 한다. 위의 그림은 두 개의 연결 요소를 가진 그래프이다. 트리 (Tree) 그래프의 일종으로 순환성이 없는 무방향 그래프이다. 트리(tree) 구조는..