https://www.acmicpc.net/problem/1427 알고리즘 분류 : 문자열, 정렬 ❓문제🔅해석정렬 알고리즘에는 비교 기반 정렬 알고리즘과 비교하지 않는 정렬 알고리즘이 있다. 해당 문제는 비교 기반 정렬 알고리즘 중 '선택 정렬' 알고리즘을 사용하여 풀이했다. 선택 정렬 알고리즘 순서는 아래와 같다. 1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다. 3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소한다. 4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.⭕정답 코드import java.io.BufferedReader;import ..
https://www.acmicpc.net/problem/23968알고리즘 분류 : 구현, 정렬, 시뮬레이션 ❓문제🔅해석비교 기반 정렬 알고리즘인 버블 정렬을 활용하는 문제이다.버블 정렬은 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬한다. 그 동안은 전역변수, 지역변수 신경 쓰지않고 작성했지만 이제부터 ChatGPT-4o에게 코드리뷰를 받고 코딩 습관을 고치려고 한다. 코드리뷰 전 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;//백준 23968번public class Main { static int N, K; stati..
코딩테스트에서 시간복잡도의 중요성은 매우 크다.많은 코딩테스트 문제집을 살펴보면 목차의 앞부분에 항상 시간복잡도에 대한 설명이 포함되어 있다. 이는 문제를 해결할 때 시간복잡도를 고려하는 것이 필수적임을 보여준다. 시간복잡도시간복잡도란 주어진 문제를 해결하기 위해 필요한 연산 횟수를 나타낸다.알고리즘이 얼마나 효율적인지를 평가하는 기준이 된다.코딩테스트에서는 시간복잡도를 기반으로 알고리즘의 성능을 평가하고, 제한된 시간 안에 문제를 풀 수 있는지를 가늠한다. 왜 시간복잡도가 중요한가?일반적으로 코딩테스트에서는 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. 사이클 검증사이클이 형성되는지 확인하기 위해서 유니온-..
