코딩 테스트/이취코테

Ch10.그래프 이론 - 커리큘럼

[ 접근 방법 ] 딱 보았을때 위상정렬 알고리즘을 구현해서 풀이하면 되는것으로 보인다. 10강에서 제일 어려웠던 문제이다. 그냥 단순하게 이 문제가 어려운게아닌, 나에게 있어 위상 정렬이 조금 구현이 어색한것 같다. [ 작성 코드 ] from collections import deque n = int(input()) # 수업 걸리는 시간 data = [0] * (n+1) task = [0] * (n+1) # 들어오는 차수 indegree = [0] * (n+1) #그래프 graph = [[] for _ in range(n+1)] for i in range(1,n+1): indata = list(map(int,input().split())) data[i] = indata[0] for x in indata[..

Ch10.그래프 이론 - 도시 분할 계획

[ 접근 방법 ] 최소 신장 트리를 통해 알고리즘을 구현한다. 단 여기서, 2개의 최소 신장 트리를 구현하는데 한개의 최소신장트리를 크루스칼 알고리즘을 통해 구현하고 제일 큰 간선을 제거하여 두개의 최소 신장 트리를 구현하면 된다. [ 작성 코드 ] def find_parent(parent, x): if x != parent[x]: parent[x] = find_parent(parent, parent[x]) return parent[x] def union_parent(parent, a, b): a = find_parent(parent,a) b = find_parent(parent,b) if a < b: parent[b] = a else: parent[a] = b n , m = map(int , input..

Ch10.그래프 이론 - 팀 결성

[ 접근 방법 ] 전형적인 서로소 집합 알고리즘 문제이다. 9강, 10강 부터는 이론을 암기하고 코드로 구현하는 연습이 필요한 것으로 보인다. [ 작성 코드 ] def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] 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 n , m = map(int,input().split()) parent = [ i for i in range(n+1) ] for _ in rang..

Ch9.최단 경로 - 전보

[ 접근 방법 ] 전형적인 다익스트라 알고리즘 문제이다. 책의 학습내용을 토대로 다익스트라 알고리즘을 구현한다. [ 작성 코드 ] import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m, c = map(int, input().split()) distance = [INF] * (n + 1) graph = [ [] for _ in range(n+1) ] for i in range (m): a, b, c = map(int , input().split() ) graph[a].append((b,c)) def dijkstra(c): q = [] distance[c] = 0 heapq.heappush(q,(0,c)) while q: dist, n..

Ch9.최단 경로 - 미래 도시

[ 접근 방법 ] 전형적인 플로이드 워셜 알고리즘 문제이다. 책의 학습내용을 토대로 플로이드 워셜 알고리즘을 구현한다. 단 여기서 k, a, b 순서대로 리스트를 갱신하는 것을 잊지않도록 한다. [ 작성 코드 ] INF = int(1e9) n ,m = map(int,input().split()) data = [[INF]*(n+1) for _ in range(n+1)] for i in range(n+1): data[i][i] = 0 for i in range(m): a,b = map(int,input().split()) data[a][b] = 1 data[b][a] = 1 # x = 최종목적지 k= 들릴곳 x , k = map(int,input().split()) for i in range(n+1): fo..

Ch8.다이나믹 프로그래밍 - 효율적인 화폐 구성

[ 접근 방법 ] 단순하게 그리디로 접근을 하였으나, 당연히 오답이 나왔다. 큰 단위의 화폐가 작은 단위의 화폐 배수로 이루어졌을 때에만 그리디로 접근 할 수있다고한다. 정답을 도출하기 위해서는 이와 같이 접근 해야한다고 한다. 그리디로 구현한 코드와 정답 코드를 확인해 보자. [ 작성 코드 ] # 그리디 구현 - 오답 n , m = map( int , input().split()) cointype = [] for _ in range(n) : cointype.append(int(input())) cointype.sort(reverse = True) count = 0 for i in cointype: if m < i: continue if m % i == 0: count += m // i m = -1 br..

Ch8.다이나믹 프로그래밍 - 바닥 공사

[ 접근 방법 ] 다이나믹 프로그래밍이므로 점화식을 찾아내야한다. 규칙성을 이전 값을 이용해서 만들어내야하는데, 생각하기 조금 어려운 것 같다. 1 일 때 > 1 2 일 때 > 3 3 일 때 > 이전꺼 x 2 - 1 >> [] [~~] 와 [~~] [] 이 경우로인해 이전꺼 x 2 ........ 라고 생각하는데 왜 1을 빼는지 모르겠다. 해설을 보고 한번 내가 생각한 원리대로 코드를 작성하고 정답이 맞는지 비교해 보도록 하자. [ 작성 코드 ] n = int(input()) floor = [0]*n floor[0] = 1 floor[1] = 3 for i in range(2,n): floor[i] = floor[i-1]*2 -1 print("my answer : ",floor[n-1]) for i in..

Ch8.다이나믹 프로그래밍 - 개미 전사

[ 접근 방법 ] 리스트를 통해 인자값을 받은 후 bottom up 방식으로 최대로 강탈하는 식량을 찾아내가면 될 것 같다. 강탈하는 방법은 n 번째 식량 창고의 경우 식량(n-1)이 더 큰지, 아니면 식량(n-2 + n) 이 더큰지 확인하여 갱신해 나가면 될것으로 보인다. [ 작성 코드 ] # 3