모카의 촉촉한 개발 로그

신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 위와 같은 하나의 그래프는 왼쪽 아래의 그래프와 같이 여러개의 신장 트리를 가질수 있다. 또한 오른쪽 아래 2개의 그래프와 같이 노드1을 포함하지 않거나 사이클이 존재할 경우 신장 트리가 아니다. 크루스칼 알고리즘 모든 도시를 최소한의 비용으로 연결 하는 경우에 대한 예시를 들어보자. 왼쪽과 같은 그래프는 3개의 도시가 있고 각각 도시 간 도로를 건설하는 비용은 23,13,25이다. 여기서 노드 1,2,3을 모두 연결하지 위한 가장 최소한의 비용을 가지는 신장 트리는 36이다. 1) 23 + 13 = 36 2) 23 + 25 = 48 3) 25 + 13 = 38 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있..

서로소 집합 자료 구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작한다. union연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find연산 : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = fin..

n개의 노드와 m개의 간선의 정보를 받은 뒤 1번노드에서 출발하여 k번 노드를 거쳐 x번 노드로 가는 최소 시간을 구하라 !! 입력 조건에서 n,m이 모두 1이상 100이하 이니 플로이드 워샬 ㄱㄱ 나의 코드 n,m=map(int,input().split()) INF=int(1e9) graph=[[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): for j in range(n+1): if i ==j: graph[i][j]=0 for i in range(m): a,b=map(int,input().split()) graph[a][b]=1 graph[b][a]=1 x,k=map(int,input().split()) for q in range(1,n+1): for w..

플로이드 워셜 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우 사용한다. - 노드의 개수가 N개 일 때 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다. - 2치원리스트에 '최단거리' 정보를 저장한다 - 노드의 개수가 N개일 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신(다이나믹 프로그래밍) - 현재 확인중인 노드를 제외하고 N-1개의 노드중에서 서로 다른 노드 (A,B)쌍을 선택한다. 이후 A->1번 노드 -> B로 가는 비용을 확인한 뒤에 최단 거리를 갱신한다. 점화식은 아래와 같다. 따라서 전체적으로 3중 반복문을 이용하..

c라는 도시에서 출발할 때 n(1

방법 2 힙을 사용하여 구현은 어렵지만 빠르게 동작하는 코드 이번 방법은 최악의 경우에도 시간 복잡도 O(ElogV)를 보장할 수 있다.(V는 노드의 개수,E는 간선의 개수) 방법 1 에서는 매번 최단거리 테이블을 선형적으로(모든 원소를 앞에서부터 하나씩) 탐색해야 했다. 이 과정에서 O(V)의 시간이 걸렸다. 하지만 최단거리가 가장 짧은 노드를 단순히 선형적으로 찾는것이 아니라 더욱 빠르게 찾을수 있다면 시간 복잡도를 더 줄일 수 있다. 이 과정에서 힙 자료구조를 사용하게 된다. 힙을 사용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 답아서 처리하므로 출발 노드로부터 가장 짧은 노드를 더욱 빠르게 찾을 수 있다. 힙 자료 구조 힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나..

다익스트라 알고리즘의 동작원리 기본적으로 그리디 알고리즘으로 분류가 된다. '매번 가장 비용이 적은 노드를 선택'해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리는 아래와 같다. 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화 한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 3에서 선택한 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 3,4번을 반복한다. '각 노드에 대한 현재까지의 최단거리' 정보를 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면..

n가지 종류의 화폐를 사용해 m원을 만드는 최소한의 가지수를 출력하는 문제. 나의 코드 n,m=map(int,input().split()) coin=[] for i in range(n): coin.append(int(input())) dy=[10001]*(m+1) dy[0]=0 for i in range(n): for j in range(coin[i],m+1): dy[j]=min(dy[j],dy[j-coin[i]]+1) if dy[m]==10001: print(-1) else: print(dy[m]) 이번에도 문제를 풀지 못했다.. 30분 가량 끙끙된 이후 분명 이전에 봤던 문제 같아 인터넷 서칭을 해보니 이전에 봤던 유형이 맞았다..! 초반 dp테이블값을 0으로 모두 고정을 하고 접근을 하려다 보니 막..

N을 입력 받았을 떄 가로가 N 세로가 2인 바닥이 생긴다. 그떄 1 x2, 2x1, 2x2 크기의 3종류의 타일로 덮을수 있는 경우의 수를 찾아라. 나의 코드 n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=3 for i in range(3,n+1): dp[i]=dp[i-1]*2-1 print(dp[n]%796796) 음.. 이번 DP 문제도 확신이 안든다... 애초에 위 코드는 결국 다이나믹프로그래밍이 아니라 그냥 입력값*2-1을 출력한 값이기도 하고... 확실한 근거를 바탕으로 패턴을 찾아야 하는데 그 확실한 근거는 늘 안보이고 짜잘한 의심? 정도를 가지고 코드를 짜게 된다.. 나의 그 짜잘한 의심은 아래 사진과 같다. 보라색 선으로 표시한 부분을 보면 i번쨰의 경우의 수..

N 개의 숫자가 입력 될때 최소 한칸 이상씩은 간격을 두고 선택할 때 선택한 숫자의 합의 최댓값을 구하라. 입력 예시) 4 1 3 1 5 출력예시) 8 나의 코드 N=int(input()) arr=list(map(int,input().split())) arr.append(0) dy=[0]*(N+1) dy[1]=1 dy[2]=max(arr[0],arr[1]) for i in range(3,N+1): dy[i]=max(dy[i-1],max(dy[:i-1])+arr[i-1]) print(dy[4]) 음..그림을 그려가며 생각한 로직대로 짜서 입력값대로의 출력값은 나오긴 했는데 확신이 없다.. dp테이블은 한칸을 건너뛰어야 하니 '바로 이전 테이블 값'과 ' 두칸 이전 까지의 dp테이블 값의 최대값과 현재 ar..