어디까지 갈 수 있을까?

정리 하는중 최소 신장 트리 모든 노드를 이었을때 간선의 가중치의 합이 최소인 트리 크루스칼 from heapq import heappop, heappush def find(x): if x == parent[x]: return x parent[x] = find(parent[x]) return parent[x] def union(x,y): x,y=find(x),find(y) parent[x]=y def kruskal(): cost=0 while q: dist, v1, v2 = heappop(q) if find(v1) == find(v2): continue else: cost += dist union(v1, v2) return cost if __name__=="__main__": N = int(input()..

위상이 위치를 뜻한다고 한다 위상정렬은 각 노드들의 순서를 찾는 알고리즘이다 이 사진을 보고 바로 이해가 갔다. 0->1->2->4->3->5 순으로 진행해야 한다. 그림에서 보면 알겠지만 먼저 탐색을 시작하는 것은 진입차수가 0인 노드부터이다. 진입차수 배열을 따로 만들어서 진입 차수가 0인 정점을 모두 큐에 삽입 큐에서 정점를 빼며 진입차수를 감소시킴 진입차수가 0이 됐다면 큐에 삽입 순으로 진행하면 일의 순서를 알 수 있게 된다 from collections import deque def topology(): q = deque() ##진입 차수가 0인 정점을 모두 큐에 넣는다 for i in range(N): if cnt_input[i] == 0: q.append(i) while q: curr = ..

접두사와 접미사를 이용한 알고리즘이다 비교 과정을 보면 텍스트 : ABABABC 패턴 : ABABC 일 때, 1. 인덱스 0 1 2 3 4 5 6 텍스트 A B A B A B C 패턴 A B A B C 2. 인덱스 0 1 2 3 4 5 6 텍스트 A B A B A B C 패턴 A B A B C index 4에서 불일치가 일어났을 때, index 0~1과 2~3의 패턴이 [AB]로 일치함을 이용해 중간 비교과정을 건너 뛰는 알고리즘이다. 이를 만들기 위해서는 전처리가 필요하다 비교하고 싶은 pattern이 abcdabcy라고 할 때 인덱스 문자열 최장 패턴 일치 길이(pi[j]) 0 a 0 1 ab 0 2 abc 0 3 abcd 0 4 abcda 1 5 abcdab 2 6 abcdabc 3 7 abcdab..

Next Permutation 사전순으로 다음에 올 수를 구하는 알고리즘 1 2 3 4 라는 배열이 있다고 했을때 next_permutation()을 사용하면 1 2 4 3 그러니까 사전순으로 다음 배열을 반환한다 c++에는 라이브러리로 있는데 자바에는 없어서 사용하려면 직접 구현해야한다 알고리즘 순서 1. 배열을 오름차순으로 정렬합니다 2. 뒤에서부터 탐색해 꼭대기 값을 찾습니다 3. 꼭대기-1 값보다 크거나 같은 값을 뒤에서부터 탐색해 둘을 교환합니다 4. 꼭대기값 ~ 끝값까지 오름차순 정렬합니다 5. 2~4를 반복합니다 이 알고리즘을 가장 잘 설명한다고 생각하는 사진을 공유한다 출처 : https://velog.io/@hongcheol/%EA%B0%9C%EB%B0%9C%EC%9D%BC%EC%A7%8..

순열 순서가 부여된 집합 {1, 2, 3}과 {2, 1, 3}을 다른 집합으로 생각한다. 이게 조합과 순열의 차이점 순열 라이브러리 X def permutation(brr, depth): if depth == N: print(*brr) return for i in range(0, len(arr)): if visited[i]: continue visited[i]=True brr[depth]=arr[i] permutation(brr, depth+1) visited[i]=False if __name__ == "__main__": N=int(input()) arr=[i for i in range(1, N+1)] visited = [False] * len(arr) permutation([0]*N, 0) 자바는 배..