devlog

출처 : https://www.acmicpc.net/problem/1005 풀이 방법 위 문제는 그래프에서 작업의 우선순위가 정해져 있으므로, 위상 정렬을 사용해 해결할 수 있다.위상 정렬에 dp알고리즘을 추가하여 현재 노드를 완료하기 위한 시간을 계산할 수 있다. from collections import dequedef topological_sort(N, K, cTime, linked, degree, win_num): 위상정렬 dp = [0] * (N + 1) queue = deque() # 시작 점 초기화 for i in range(1, N + 1): if degree[i] == 0: queue.append(i) dp[i] =..

출처 : https://www.acmicpc.net/problem/15686 풀이 방법M개의 치킨 집을 선택하는 과정에서 순서에 상관없는 조합을 이용해야 한다.조합을 구하기 위해 백트레킹 dfs를 사용했다.아래의 코드에서 chosen 배열에 넣은 후 dfs를 수행하고 chosen배열에서 pop을 통해 백 트레킹을 수행했다. 치킨 거리 계산은 그냥 유클리드 계산으로 수행하면 된다. N, M = map(int, input().split()) ## N, M 입력받기city = []for i in range(N): ## city 입력 받기 city.append(input().split())house = []store = []chosen = []ans = 987654321for i in range(N): #..

출처 : https://www.acmicpc.net/problem/2252 풀이 방법위상 정렬 알고리즘을 통해 풀이할 수 있다.위상 정렬 알고리즘이란 그래프에서 우선순위가 있는 작업을 할 때 순서를 정해주는 알고리즘이다 답이 여러 개가 될 수 있다.조건으로 사이클이 없어야 한다. 또한 최우선순위인 시작 점이 존재해야한다.진입 점이 0인 점을 큐에 넣어서 시작점으로 지정한다.큐에서 하나를 pop 하고 이와 연결된 노드의 진입 점을 -1 한다.만약 2번에서 진입 점을 -1 한 노드의 진입점이 0이면 큐에 추가한다.위 2~3번 과정을 N번 반복하는데 만약 N번 반복하기 전에 큐에 empty가 되면 사이클이 존재하는 경우이다.코드from collections import dequeN, M = map(int, i..

출처 : https://www.acmicpc.net/problem/2565 풀이 방법전깃줄이 갖아 길게 안 꼬이는 경우를 찾으면 된다.와이어 A를 기준으로 연결된 쌍을 정렬한 뒤 B의 최장 증가 부분 수열을 구한 후 이를 원본 쌍에서 빼주면 된다. 1. 먼저 모든 연결된 쌍을 입력받는다.2. 와이어 A를 기준으로 정렬한다.3. 와이어 B를 저장하는 배열을 생성한다.4. 와이어 B를 탐색하며 만약 최장증가 부분 수열의 임시 배열인 lsb_arr의 마지막 원소보다 크다면 뒤에 추가한다.5. 크지 않다면 lsb_arr에서 현재 원소가 들어갈 인덱스를 이분탐색을 통해 구한 후 추가해 준다.6. lsb_arr의 길이를 구하면 이것이 최장 증가 부분 수열의 길이이다. N = int(input())wire = [] ..

출처 : https://www.acmicpc.net/problem/13418 풀이 방법union-find알고리즘을 통해 해결할 수 있다. 기존의 알고리즘과 다른 점은 0에서 1로 가는 간선은 무조건 포함되어야 한다는 점이다. 또 가장 힘든 경우와 가장 덜 힘든 경우를 계산하기 위해 mst알고리즘을 2번 사용했다.주의: mst알고리즘을 사용하기 전 parents를 초기화해주어야 한다.  N, M = map(int, input().split())edges = []parents = [ i for i in range(N+1)]a, b, c = map(int, input().split()) ## 0~1 엣지 무조건 추가되어야 할 edgefirst_weight = 1 - c ## 첫 번째 edge의 weight 오..

출처 : https://www.acmicpc.net/problem/1197 풀이 방법kruskal 알고리즘을 사용해서 풀이할 수 있었다.kruskal 알고리즘을 이용하기 위해 union find 알고리즘을 구현해야 한다.입력을 받을 때 간선(edges)을 기준으로 입력을 받는다.그 후 edges의 weight가 작은 것으로 정렬을 한다.weight가 작은 간선 중  간선에 연결된 두 노드의 부모가 같지 않다면 해당 간선을 추가한다.간선이 V-1개가 될 때까지 반복한다. V , E = map(int, input().split())parents = [i for i in range(V+1)] ## 부모 배열 생성edges = []for i in range(E): ## 입력 받기 a, b, w = map..

출처 : https://www.acmicpc.net/problem/31791풀이 방법일반적인 bfs 문제에서 퍼질 수 있는 시간이 정해진 문제이다.바이러스의 시간이 많은 것부터 처리하기 위해 map heap의 우선순위 큐를 사용했다. 그러기 위해 남은 시간을 음수로 하여 저장했다.그 후 시간이 많이 남은 바이러스 부터 전파를 시작해 빈 곳이면 시간 - 1을 우선순위 큐에 넣어주고만약 건물이라면 남은 바이러스 시간 - 건물 전파시간 - 1을 해주어서 이 수가 만약 양수이면 건물이 감염된 것이고 음수이면 건물이 감염이 안 된 것으로 처리했다. 그 후 계산한 값을 우선순위 큐에 넣어주었다. bfs를 탐색하며 우선순위 큐에서 값을 꺼내어 남은 시간이 양수이면 전파를 시작했고 0 이하라면 전파를 멈췄다.   전체..

출처 : https://www.acmicpc.net/problem/1717풀이 방법일반적인 유니온 파인드 문제로 해결할 수 있다. 실수한 부분문제를 풀 때 union 함수에서 큰 실수를 했다.def union(a, b): temp1 = min(find(a), find(b)) parents[a], parents[b] = temp1, temp1위와 같은 실수를 했는데 코드를 자세하게 보면 a와 b의 부모를 찾아 작은 부모로 모두 바꾸어 주었는데이렇게 코드를 작성하게 된다면 인덱스가 큰 부모를 갖는 원소가 작은 부모를 갖는 원소의 부모로 교체되며 원래 자신의 부모와는 연결이 끊기게 되는 문제가 발생한다. 그래서 아래와 같이 코드를 수정했다. def union(a, b): a = fin..

출처 : https://www.acmicpc.net/problem/12015 풀이 방법LIS 알고리즘 중 binary search를 이용한 방법으로 풀이하면 된다. LIS의 binary search가 기존의 binary search와 다른 점은 기존의 binary search는 특정 값을 찾아야 하지만 LIS에서의 binary search는 특정 값을 찾는 거뿐만 아니라 찾아야 하는 값이 없다면 자신보다 작은 수 중에 가장 큰 수의 인덱스에 +1 한 인덱스를 찾아주어야 한다.  def binary(num): left = 0 right = len(temp)-1 mid = 0 while (left  위의 binary search 코드처럼 해당 값이 존재한다면 해당 값의 idx를..

출처 : https://www.acmicpc.net/problem/12865풀이 방법일반적인 냅색 문제로 DP를 이용해서 풀이할 수 있다.하지만 문제를 풀이할 때 엄청난 실수를 했다.top-down 방식을 사용했는데 이를 잘 못 적용한 것이다.DP의 핵심은 문제를 분리할 때 서로 영향을 받지 않아야 한다. 하지만 처음 코드는 서로가 영향을 받는 코드를 작성했다.  N, K = map(int, input().split())arr = [[0, 0] for _ in range(N)]dp = [[-1 for _ in range(100001)] for _ in range(N) ]for i in range(N): arr[i][0], arr[i][1] = map(int, input().split())def ka..