짧은코딩

위상 정렬 위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져 있는 작업을 차례대로 수정할 때 사용하는 알고리즘이다. 예시로는 선수 과목을 고려한 학습 순서 설정이 있다. 예를 들어 자료구조, 알고리즘, 고급 알고리즘이 있다. 그리고 (알고리즘의 선수 과목은 자료구조), (고급 알고리즘의 선수 과목은 알고리즘)이면 자료구조 -> 알고리즘 -> 고급 알고리즘으로 수업을 들어야한다. 위상 정렬은 먼저 진입차수를 알아야 하는데, 진입차수느 특정 노드로 들어오는 간선의 개수를 의미한다. 잔입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지, 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 위 과정을 거치다가 모든 원소를 방문하기 전에 큐..

신장 트리 신장 트리는 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 크루스칼 알고리즘 -크루스칼 알고리즘 원리 https://shortcoding.tistory.com/141?category=1009070 그래프(1) 완전 그래프 각 정점에서 다른 모든 정점을 연결해 최대로 많은 간선 수를 가진 그래프 무방향 그래프 최대 간선 수: n(n-1)/2개 방향 그래프 최대 간선 수: n(n-1)개 그래프 구현 -인접 행렬 무방향 shortcoding.tistory.com 원리는 이전에 알고리즘 수업을 정리했던 글을 참고하면 될 것이다. 특징으로는 최종적으로 신장 트리에 포함되는 간선의 개수가 (노드의 개수 - 1)이다. -예시 코드 # 특정 원소가 속한 집합을 찾..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결법 이 문제는 다익스트라 알고리즘을 활용해서 푸는 문제다. graph에 연결된 노드를 저장할 때는 플로이드 알고리즘과 다르게 저장한다는 점을 다시 기억하면 좋을 것 같다. 다익스트라 알고리즘에서 graph에 연결된 노드를 저장하는 법은 시작 노드 a, 연결된 노드 b, 가중치 c를 graph[a].append(b, c)이다. 이 점을 유의하고 푼다면 좀 더..

그래프 구현 방법 그래프 구현 방법은 2가지 방식이 존재한다. 하나는 2차원 배열을 사용하는 방식인 인접 행렬(Adjacency Matrix)이 있고 다른 하나는 리스트를 사용하는 방식인 인접 리스트(Adjacency List) 방식이 있다. 노드의 개수가 V개, 간선의 개수가 E인 그래프가 있다고 하고 두 방식을 비교한다. 1. 인접 행렬 메모리 공간: 간선의 정보를 저장하기 위해 O(v^2)의 메모리 공간 필요 다른 노드까지의 가중치를 알아내는 시간: O(1)의 시간으로 즉시 알아낼 수 있음 2. 인접 리스트 메모리 공간: 간선의 개수만큼인 O(E)의 메모리 공간이 필요 다른 노드까지의 가중치를 알아내는 시간: O(V)만큼의 시간이 요소 앞에서 배운 다익스트라 알고리즘은 인접 리스트를 이용하는 방식이..

해결법 내 풀이는 플로이드 알고리즘을 활용해서 먼저 그래프를 만들었다. 그리고 출발 노드인 지점에서 몇 개의 노드가 연결되어 있는지 확인하고 가중치가 가장 긴 시간의 노드의 값을 구하면된다. 내 풀이 INF = int(1e9) n, m, c = map(int, input().split()) graph = [[INF] * (n+1) for i in range(n+1)] for i in range(1, n+1): graph[i][i] = 0 for i in range(m): x, y, z = map(int, input().split()) graph[x][y] = z for k in range(1, n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a]..

풀이법 이 문제는 최소 이동 경로를 찾아야해서 플로이드 알고리즘으로 풀어야 한다. 모든 회사 사이의 가중치는 1이며 양방향 연결로 구성되어 있다. graph 이중 리스트를 만들고 이 안에 자기 자신으로 향하는 방향은 0을 넣어줬다. 그리고 삼중 배열로 최단 거리를 구해주면 된다. 코드 INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n+1) for i in range(n+1)] for i in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 for i in range(1, n+1): graph[i][i] = 0 x, k = map(int, input(..

플로이드 워셜 알고리즘 -다익스트라 vs 플로이드 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로는 구하는 경우에 사용한다. 반면에 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용한다. 또한 다익스트라 알고리즘은 그리디 알고리즘, 플로이드 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다. -플로이드의 시간 복잡도 노드의 개수가 N개일 때, 알고리즘상으로 N번의 단계를 수행하고 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 시간 복잡도는 O(N^3)이다. 그리고 플로이드 알고리즘은 2차원 리스트에 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 한..

가장 빠른 길 찾기 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이라서 길 찾기 문제라고도 불린다. 컴퓨터공학과 수준에서는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘, 이렇게 3가지이다. 이 중 다익스트라 최단 경로 알고리즘, 플로이드 워셜이 코딩 테스트에서 가장 많이 등장하는 유형이다. 다익스트라 최단 경로 알고리즘 다익스트라 알고리즘은 그래프에서 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 경로에 음수가 없을 때 정상적으로 동작한다. 다익스트라 알고리즘은 가장 비용이 적은 노드를 선택해 과정을 반복하여 그리디 알고리즘으로 분류된다. -알고리즘 원리 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중 최..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 해결법 이 문제는 회의 종료 시간을 기준으로 정렬을 한다. 그리고 맨 처음 회의는 무조건 들어간다. 맨 처음 끝나는 시간을 기록하고 다음 회의 시작 시간과 비교한다. 만약 앞의 회의가 끝나는 시간보다 다음 회의 시작 시간이 같거나 크면 그 회의는 진행할 수 있다. 이런식으로 구현하면된다. 하지만 문제점은 저렇게 구현하면 시작 시간과 끝나는 시간이 같은 회의에서 틀리게 된다. 그렇기에 먼저 시작 시간으로 정렬을 한 번 해주고 나서 종료 시간을 정렬하면 해결된다. 코드 n = int(input()) ary = [] ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 해결법 이 문제는 동적 프로그래밍 문제이다. 따라서 규칙이나 패턴을 찾아야 한다. 1: (1) => 1개 2: (1+1), (2) => 2개 3: (1+1+1), (1+2), (2+1), (3) => 4개 4: (1+1+1+1), (1+1+2), (1+2+1), (1+3), (2+1+1), (2+2), (3+1) => 7개 5: (1+1+1+1+1), (1+1+1+2), (1+1+2+1), (1+1+3), (1+2+1+1), (2+1+1+1), (1+2+2), (2+1+2), (2+2+1), (..