코딩테스트에서 시간복잡도의 중요성은 매우 크다.많은 코딩테스트 문제집을 살펴보면 목차의 앞부분에 항상 시간복잡도에 대한 설명이 포함되어 있다. 이는 문제를 해결할 때 시간복잡도를 고려하는 것이 필수적임을 보여준다. 시간복잡도시간복잡도란 주어진 문제를 해결하기 위해 필요한 연산 횟수를 나타낸다.알고리즘이 얼마나 효율적인지를 평가하는 기준이 된다.코딩테스트에서는 시간복잡도를 기반으로 알고리즘의 성능을 평가하고, 제한된 시간 안에 문제를 풀 수 있는지를 가늠한다. 왜 시간복잡도가 중요한가?일반적으로 코딩테스트에서는 1억 번의 연산을 1초에 처리할 수 있는 기준을 사용하여 수행 시간을 예측한다.따라서 문제를 풀 때는 주어진 입력 크기에 맞는 최적화된 알고리즘을 선택해야 한다. 만약 시간복잡도가 높은 알고리즘을 ..
다익스트라 알고리즘 (Dijkstra's Algorithm)음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제시작점이 있고, 모든 노드로 최단 거리를 구할 때인접 리스트 사용PQ로 최소 cost 뽑으면서 정점을 방문하여 최단 거리 갱신음의 간선이 없으므로 각 노드에 최초 방문 시 최단 거리를 확정한다. (방문 체크 필요) 동작 원리시작 정점 설정시작 정점을 선택하고, 이 정점에서 다른 모든 정점으로의 최단 거리를 저장할 배열을 초기화한다. 시작 정점의 거리는 0으로 설정하고, 나머지 정점의 거리는 무한대로 설정한다.방문하지 않은 정점 중 최단 거리 정점 선택한다.인접한 정점들의 거리 갱신선택한 정점의 인접한 정점들에 대해, 현재 정점을 거쳐 가는 것이 더 짧은 경로라면, 그 ..
https://www.acmicpc.net/problem/2458알고리즘 분류 : 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최단 경로, 플로이드–워셜❓문제🔅해석모든 학생의 키를 비교한 횟수를 알아야하기 때문에 전체 쌍의 계산이 필요한 "플로이드-워셜" 알고리즘을 사용한다. 1. 거리 초기화 만약 두 정점 간에 직접 연결된 간선이 있다면 그 가중치로 초기화하고, 연결되어 있지 않다면 무한대(또는 매우 큰 값)로 설정한다. 자신에게 가는 거리는 0으로 설정한다.for (int n = 1; n 2. 동적 프로그래밍(DP) 적용 각 정점을 중간 정점으로 고려하여, 다른 모든 정점 쌍에 대해 최단 경로를 갱신한다. 즉, 정점 k를 중간 정점으로 사용하는 경우, i에서 j로 가는 경로가 i -> k ->..
https://www.acmicpc.net/problem/11657알고리즘 분류 : 그래프 이론, 최단 경로, 벨만–포드❓문제 🔅해석 1. 거리 초기화 시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정한다. 2. 거리 갱신 모든 간선에 대해 V-1번 반복해서 간선의 시작 정점에서 도착 정점으로 가는 경로가 현재 알려진 경로보다 짧다면, 그 경로를 갱신한다.dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] > dist[to] + edge.cost 이므로 dist 업데이트를 한다. dist[from] == dist[to] + edge.cost 이므로 dist 업데이트 되지 않는다. dist[from] 이렇게 (..
https://www.acmicpc.net/problem/1753알고리즘 분류 : 그래프 이론, 데이크스트라, 최단 경로❓문제🔅해석음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제에서는 다익스트라 알고리즘이 사용된다.다익스트라 알고리즘은 인접리스트 형태로 그래프를 저장하고, Priority Queue를 사용하여 최소 비용의 정점이 먼저 나오도록 한다. // input5 615 1 11 2 21 3 32 3 42 4 53 4 6 1. 인접 리스트 생성ArrayList[] adjList = new ArrayList[V + 1]; 2. start로 부터 각 노드까지 최단거리를 담는 dist 배열과 노드를 방문했음을 체크하는 visited 배열을 생성한다. 3. Priority ..
MST (최소 신장 트리)Minimum Spanning Tree가중치가 있는 연결 그래프에서 모든 정점을 포함하면서, 간선의 가중치 합이 최소가 되는 트리이를 찾기 위한 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal's Algorithm)그래프의 모든 간선을 가중치 순으로 정렬한 후, 가중치가 가장 작은 간선부터 선택하여 트리를 구성하는 방법이다.이 과정에서 사이클을 형성하는 간선은 선택하지 않는다.간선 위주, union-find 사용 순서간선 정렬: 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.간선 선택: 정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다..
https://www.acmicpc.net/problem/11438알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열❓문제🔅해석순서input된 값을 adjacent list(양방향 간선)에 넣는다.BFS로 트리 탐색bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 희소 테이블(Sparse Table) 구성각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.Find LCA항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swapa, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)2에서 depth를 맞추었는데 a와 b가 같다면 lca를 ..
https://www.acmicpc.net/problem/1922알고리즘 분류 : 그래프 이론, 최소 스패닝 트리❓문제🔅해석컴퓨터 == 정점선 == 간선 모든 컴퓨터(정점)를 연결하여 최소의 비용(가중치)을 얻기 위해 MST를 구현한다.MST를 구하기 위한 알고리즘에는 크루스칼, 프림이 있는데 크루스칼로 풀이해본다. // input691 2 51 3 42 3 22 4 73 4 63 5 114 5 34 6 85 6 8 1. 간선 정렬그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. 2. 간선 선택정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다. 3. 사이클 검증사이클이 형성되는지 확인하기 위해서 유니온-..
그래프 (Graph)현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것 그래프 표현1. 간선 리스트(Edge List)정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 E x 2 (or E x 3) 이차원 배열(A)에 간선 정보를 저장어떤 두 정점 vi, vj를 연결하는 간선 ek = (vi, vj) 에 대해서 A[k][0] = vi, A[k][1] = vi가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장벨만-포드 알고리즘에서 사용한다.코드 구현간선 정보 classstatic class Edge{ int from; int to; int cost; public Edge(int from, int to, int cost){ th..
https://www.acmicpc.net/problem/2252알고리즘 분류 : 그래프 이론, 위상 정렬, 방향 비순환 그래프❓문제🔅해석위상정렬을 이용하여 풀이한다. 위상정렬은 비순회 방향 그래프에서 정점을 정렬하는 방식이며, 동일한 우선순위를 가진 작업들이 여러 가지 방법으로 나열될 수 있기 때문에 여러 개의 정렬 결과가 나올 수 있다. // input4 24 23 1 1. indegree 계산 및 indegree 배열 중에서 0인 노드를 Queue에 담는다. 2. Queue에서 pop를 하고, 3(pop 한 값)과 연결된 노드에 indegree를 하나 감소시킨다. 3. Queue에서 pop를 하고, 4(pop 한 값)와 연결된 노드에 indegree를 하나 감소시킨다. 4. Queue가 빌 ..
