짧은코딩

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

그래프 구현 방법 그래프 구현 방법은 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가지이다. 이 중 다익스트라 최단 경로 알고리즘, 플로이드 워셜이 코딩 테스트에서 가장 많이 등장하는 유형이다. 다익스트라 최단 경로 알고리즘 다익스트라 알고리즘은 그래프에서 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 경로에 음수가 없을 때 정상적으로 동작한다. 다익스트라 알고리즘은 가장 비용이 적은 노드를 선택해 과정을 반복하여 그리디 알고리즘으로 분류된다. -알고리즘 원리 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중 최..

해결법 이 문제도 보텀업 방식으로 푸는 문제이다. 리스트 d에 작은 수부터 체크하면서 푼다. 이 문제의 핵심 풀이 방식은 지금의 숫자와 비교했을 때, 동전의 숫자만큼 뺀 숫자가 존재하면 당연히 동전 수만큼 더한 수도 존재한다는 것이다. 풀이 n, m = map(int, input().split()) ary = [] for i in range(n): ary.append(int(input())) d = [10001] * (m+1) d[0] = 0 # 동전 수만큼 반복 for i in range(n): # 가장 작은 동전 수부터 구하려는 목표 수까지 반복 for j in range(ary[i], m+1): # (i-k)원을 만들 수 있으면 if d[j - ary[i]] != 10001: d[j] = min(d..

다이나믹 프로그래밍은 종종 결과가 너무 클 수 있어서 어떤 수로 나눠서 출력하라고 한다. 풀이법 -N이 3일 때의 예시 1. N이 3이고, i-1번째 즉, 2번 칸까지 채워져 있으면 경우에 수는 1개이다. 2. i-2번째 즉, 1번 칸까지 채워져 있으면 경우의 수는 2가지이다. -점화식 따라서 점화식은 이렇게 구할 수 있다. 풀이 n = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3, n + 1): d[i] = (d[i-1] + d[i-2] * 2) % 796796 print(d[n]) 점화식에 맞게 코딩을 했다. 이 문제의 풀이도 처음엔 생각하지 못했다. 다이나믹 프로그램을 코딩하면 쉽지만 점화식 같은 풀이를 생각하는 것이 어렵다. 앞으..

교재 풀이 이렇게 바로 옆을 털면 지금 창고를 털지 못한다. 그리고 2번 떨어진 창고를 털면 지금 창고를 털 수 있다. 따라서 바로 옆 창고 vs (옆옆 창고 + 현재 창고) 이렇게 비교해서 더 큰 값을 찾아야 한다. n = int(input()) ary = list(map(int, input().split())) d = [0] * 100 d[0] = ary[0] d[1] = max(ary[0], ary[1]) for i in range(2, n): d[i] = max(d[i-1], d[i - 2] + ary[i]) print(d[n-1]) 이런 풀이가 나온다. 위에서 설명했듯이 옆 창고 vs (옆옆 창고 + 현재 창고)를 비교하면서 푸는 문제이다. 이 문제를 다시 풀면서 for문 안에 max에서 (옆옆..

비효율적으로 푼 내 풀이 #내가 풀어본 비효율적인 방식 from collections import deque x = int(input()) answer = 0 q = deque([(x, 0), (x-1, 1)]) while True: t = q.popleft() nx = t[0] count = t[1] if nx == 1: answer = count break if (nx % 5) == 0: q.append((nx // 5, count+1)) q.append(((nx // 5) - 1, count+2)) if (nx % 3) == 0: q.append(((nx // 3) - 1, count+2)) if (nx % 2) == 0: q.append(((nx // 2) - 1, count+2)) print(a..