모카의 촉촉한 개발 로그

동전 분배하기 N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다. 세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 해보세요. 단 세 사람의 총액은 서로 달라야 합니다. ▣ 입력설명 첫째 줄에는 동전의 개수 N(3

선행 순서가 있는 수업들을 각 입력이 들어올 때마다 해당 입력된 수업의 소비 시간을 구하라. 선행 순서 ==> 위상정렬을 사용해야 함 ! 나의코드 n=int(input()) arr=[] in_count=[] for i in range(0,n): arr.append(list(map(int,input().split()))) arr[i].pop() in_count.append(len(arr[i])-1) for x in arr: if len(x)==1: print(x[0]) else: S=x[0] for i in range(1,len(x)): S=S+arr[x[i]][0] print(S) print(S) 음.. 위상 정렬을 사용한다는것은 알겠지만.. 큐를 사용해서 하나씩 로직을 처리하지 못하고 나의 생각다로 ..

n개의 노드와 m개의 간선을 사용해서 2개의 그룹으로 만드는 최소신장트리를 구하라. 크루스칼 알고리즘을 사용하면 될것 같으며 최소신장 트리가 완성이 되면 뒤 최소 신장 트리의 집합내부에 가장 큰 비용을 가진 간선을 제외하고 모두 더하면 될것 같다..! 나의 코드 def union(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a>b: parent[a]=b else: parent[b]=a def find_parent(parent,x): if parent[x] != x: parent[x]=find_parent(parent,parent[x]) return parent[x] n,m=map(int,input().split()) edges=[] p..

n명의 학생들이 M개의 연산이 주어 진다. M개의 연산의 종류는 아래와 같다. 1. 팀 합치기 2. 같은팀인지 확인 2번과 같은 입력이 들어오면 그에 대한 출력을 Yes or NO로 하라. 나의 코드 def union(parent,a,b): a=check_parent(parent,a) b=check_parent(parent,b) if a>b: parent[a]=b else: parent[b]=a def check_parent(parent,x): if parent[x] !=x: parent[x]=check_parent(parent,parent[x]) return parent[x] n,m=map(int,input().split()) parent=[0]*(n+1) for i in range(n+1): pare..

위상정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘 (방향 그래패의 모든 노드를 방향성에 거스트리 않도록 순서대로 나열하는것) EX) 선수 과목을 고려한 학습 순서 진입차수 : 한 노드로 들어오는 간선의 개수 ( 고급 알고리즘의 진입차수는 2이다) 위상 정렬 알고리즘은 아래와 같다. 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐가 빌 때 까지 다음의 과정을 반복한다 1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 한다. (보통 위상정렬 문제에서는 사이클이 발생하지 않는다고 명시한다.) 위 그래프로 위상 정렬을 순서대로 이해해..

신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 위와 같은 하나의 그래프는 왼쪽 아래의 그래프와 같이 여러개의 신장 트리를 가질수 있다. 또한 오른쪽 아래 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