위상정렬 알고리즘 -큐를 이용 1. 진입차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. --> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. (특징) - 사이클이 없는 방향그래프(DAG)여야 한다. - 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답 존재. - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있음 (시간복잡도) - 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하므로 시간복잡도는 O(V+E)이다. 위상정렬 코드 from ..

최소 스패닝 트리란 스패닝 트리중 모든 가중치의 합이 최소인 트리이다. (프림, 크루스칼) 1. 크루스칼 알고리즘 - 가중치가 최소인 간선을 하나씩 선택해 나가는 간선 기반 알고리즘이다. 사이클이 발생하는 경우에 대해서는 예외 처리가 필요하다. def find_parent(a): # 부모찾기 if parent[a] == a: return a else: parent[a] = find_parent(parent[a]) return parent[a] def merge(a, b): x = find_parent(a) y = find_parent(b) if x != y: parent[x] = y return True return False v, e = map(int, input().split()) parent = d..

1. BFS def depth(tree,root): queue = deque() queue.append((root,1)) visit = [] count = 1 while queue: #while문을 돌리는 만큼 깊이 증가 v, count= queue.popleft() visit.append(v) for node in tree[v]: if node != '.' and node not in visit: queue.append((node,count+1)) return count 각 노드에서의 count를 계속 늘려주고 while문을 빠져나왔을 때 마지막 count를 리턴하면 최대 깊이를 구할 수 있다. 2. 재귀 def depth(tree,root): if root =='.': return 0 left = d..

말그대로 미로탐색 문제였다. 1,1에서 n,m까지 이동하는 경우의 수를 찾으면 된다. 최소의 칸 수를 출력해야 하기 때문에 BFS를 사용하였다. from collections import deque def bfs(v): queue.append((0, 0)) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] while queue: x, y = queue.popleft() for i in range(4): # 자식노드 큐에 추가하기 위함 nx, ny = x + dx[i], y + dy[i] if 0

위의 예제를 2차원 배열로 표현하면 이렇게 된다. (양방향이므로) matrix[i][j]라면 i에서 j를 갈 수 있으면 1, 아니면 0이다. def dfs(v): # v가 시작점 print(v, end=' ') visit[v] = 1 # 방문한 점 1로 for i in range(1, n + 1): if visit[i] == 0 and matrix[v][i] == 1: # 방문을 아직 안했고 v에서 i로 갈수있다면 dfs(i) # i를 다시 v로 하면서 dfs 로 탐색 def bfs(v): queue = [v] # 들려야 할 점 저장 visit[v] = 0 # 방문한 점 0으로( dfs로 인해 1로 바뀌어 있으므로) while queue: # 큐가 빌 때까지 v = queue.pop(0) print(v,..

입국심사를 받아야 하는 n명의 사람이 있을 때 심사관들은 심사할 때 각각 주어진 times와 같은 시간이 소요된다. 총 n명의 사람이 전부 검사를 받는데 걸리는 최소의 시간을 구하는 문제였다. 일단 n명의 사람이 검사받는데 걸리는 최악의 시간은 가장 오래 시간이 소요되는 심사관에게 모든사람이 검사를 받는 경우이다. 이진 탐색을 이용해 left = 0 right= 최악의 시간으로 하여 가장 최소로 걸리는 시간을 찾는다. left = 0 right = max(time_list) * n # 모든사람이 다 받을 때 끝나는 시간의 최악의 경우 while left = n: answer = mid right = mid - 1 elif people < n: left = mid + 1 print(answer) 나는 이진..

나는 브루트포스 방식을 이용해서 문제를 풀었다. 그거밖에 생각이 나지 않았다. 모든 경우를 탐색해봐야 하는데 그 방법을 찾는 것도 알고리즘 초보인 나에게는 너무 어려웠다. 모든 순열을 탐색해야하는데 이 방법은 찾아보았다. w[i][j]가 도시 i에서 j로 가는 비용이라고 하였기 때문에 w[i][i+1]과 같은 방식으로 거리비용을 세야지 모든 도시를 경유할 수 있다. permutation을 이용하여 0부터 n-1까지의 수를 순열로 짜고 그 경우의 수마다의 비용을 구한다. 예를 들어 도시를 0,1,2,3이 있다고 할 때 perm = [3 1 2 0]이라면 3->1 1->2 1->0으로 가는 비용이다. 그렇게 모든 경우를 다 탐색해본 후 최소 비용을 구하면 된다. import itertools n = int(..

처음에는 문제가 이해가 안갔는데 그냥 A와 A를 짝짓고 B와 B를 짝지었을 때 겹치는 선이 없고 남는 문자가 없으면 좋은 문자로 세어주는 것이었다. 이 문제를 푸는 알고리즘은 1. 스택에 같은 문자가 들어오면 pop 2. 스택에 다른 문자가 들어오면 push 하는 것이다. 파이썬으로 알고리즘을 짜기 시작한지 얼마 되지 않아 리스트가 비어있을 경우에 대한 조건문을 만들때 아래와 같은 코드를 사용하는 것이 len(stack)을 사용하는 것보다 훨씬 나은 코드라는 것도 알게 되었다. if not stack: 그리고 리스트의 마지막 원소에 접근할 때 stack[-1]처럼 사용한다는 것을 알게 되었다. def main(): n = int(input()) word_list = [] stack=[] count = 0..

이 문제는 생각한 것 보다 어려웠다. DP로 풀어야겠다고 생각을 하고 짰는데 배열 1에서부터 시작하니 날짜 계산을 어떻게 해야할 지 감이 안왔다. 그래서 상담잡는 순서를 마지막날에서부터 시작하였다. 일단 상담을 잡을수 없는 날과 상담을 잡을 수 있는 날로 조건을 나눈다. 1. 상담을 잡으면 퇴사일을 넘기는 경우 DP[i] = DP[i+1] 전날에 잡은 상담 가격 대입 2. 상담 잡을 수 있는 경우 max(DP[i+1], DP[i+time[i]]+Price[i]) 전날에 잡은 상담가격과 (오늘상담가격+상담일지난후의 상담가격) 중 큰 값 def main(): n = int(input()) max_price_list = [0 for _ in range(n + 2)] time_list = [0 for _ in ..

처음에는 그냥 조건문을 만들어 그리디알고리즘 방식으로 계속 그때그때 작은수를 만들면서 짜면 될 줄 알았다. 하지만 10을 입력으로 넣었을 때 예외가 발생하였고 우선순위를 정해놓고 짜는 방식으로는 하면 안되겠다는 생각이 들었다. 위의 문제에서 의도한 풀이법은 DP 알고리즘을 이용하는 방식으로 점화식을 이용하는 것이 가장 좋다. DP(다이나믹 프로그래밍)란 큰 문제를 작은 문제로 나누어 푸는 방법이다. 이 작은 문제들은 어딘가에 저장해놓는다. 그리고 이 작은 문제들을 이용해서 답을 도출해낸다. f(n/2)+1 f(n/3)+1 f(n-1)+1 중 최솟값이 f(n)의 값이 된다. 불필요한 연산을 여러번 하는 것을 막기 위해 리스트에 연산횟수를 저장해놓는다. 예를 들어 10을 입력했을 경우 배열 인덱스 1부터 1..