어디까지 갈 수 있을까?

정리 하는중 최소 신장 트리 모든 노드를 이었을때 간선의 가중치의 합이 최소인 트리 크루스칼 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 = ..

[배열돌리기 2] 문제링크 https://www.acmicpc.net/problem/169267 배열돌리기 1을 할 때는 원본 배열을 copy해서 돌렸는데 한번 돌릴때마다 계속 배열을 복사해야 하다보니 시간이 오래걸렸다. 배열돌리기 2에서도 배열돌리기 1에서 하던 로직으로 pypy3는 통과했지만, python에서는 시간초과가 났다. 그래서, queue를 사용해서 1차원적으로 접근해 돌릴 수 있는 만큼 다 돌리고 원본배열에 반영했는데 훨씬 쉬웠다. queue같은 경우 linkedlist로 구현돼 맨앞이나 맨뒤에서 append나 pop이 일어난다고 해도 O(1)안에 연산이 가능해 시간도 많이 줄었다. python으로도 268ms에 맞았습니다 판정이 났다. [배운점] while과 queue의 조합이 너무 좋았..

접두사와 접미사를 이용한 알고리즘이다 비교 과정을 보면 텍스트 : 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) 자바는 배..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/67258 1. 최소 길이를 구할 땐 투포인터 알고리즘을 생각해보자 2. 0 인덱스를 갖는 값은 미리 넣어준다 [답코드] from collections import defaultdict def solution(gems): gems_len=len(set(gems)) dic=defaultdict(int) dic[gems[0]]=1 answer=[] start=0; end=0 while start

문제링크 https://programmers.co.kr/learn/courses/30/lessons/72412 0. 딕셔너리에 문자열 모두 붙여서 key값으로 넣기 1. 컴비네이션으로 내가 들어갈 수 있는 모든 경우의 수를 만들어 내 int 값을 넣기 2. 정렬된 값에서 이분탐색으로 위치 찾기 [답코드] from collections import defaultdict from itertools import combinations def solution(info, query): dict=defaultdict(list) for i in info: i = i.split() dict_key=i[:-1] dict_val=int(i[-1]) for size in range(0, 5): for c in combina..