killog

참고: 개선된 프림 알고리즘 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식 초기화 - 정정: key 구조를 만들어 놓고, 특정 정점의 key값은 0, 이외의 정점들의 key값은 무한대로 놓음. 모든 정점: key 값은 우선순위 큐에 넣음 가장 key값이 적은 정점:key 를 추출한 후(pop 하므로 해당 정점:key 정보는 우선순위 큐에서 삭제됨,) (extract min 로직이라 부름) 해당 정점의 인접한 정점들에 대해 key값과 연결된 가중치 값을 가지는 정점 :key를 루트 노드로 올려놓도록 재구성함(decrease key 로직이라 부름) 개선된 프림 알고리즘 구현시 고려사항 우선순위 큐(최소힙)구조에서, 이미 들어잇는 데이터의 값 변경시, 최솟값을 가지는 데이터를 루트 노드로 올려놓도록..

BFS 문제임을 인지해야하고 최단거리 문제를 풀때, deque 에 cost 를 넣는 좋은 방법이라는 것을 인지해야하고 map 의 크기가 바뀔 수 있음을 인지해야하고 가로 세로를 이렇게 쿨하게 표현할 수 있음에 유의해야한다. 문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는..

다른 방법도 생각나는데, 코딜리티가 딕셔너리를 좋아하길래 넣어줬더니 맞았다. 내맘대로 풀면 88점이 나온다. A non-empty array A consisting of N integers is given.A permutation is a sequence containing each element from 1 to N once, and only once.For example, array A such that: A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2is a permutation, but array A such that: A[0] = 4 A[1] = 1 A[2] = 3is not a permutation, because value 2 is missing.The goal is to c..

열심히 코딜리티 pdf 를 읽은 보람이 있다!!! 어제 3시간동안 낑낑댄걸 바로 풀었다 Detected time complexity: O(N) or O(N * log(N)) import collections def solution(A): # write your code in Python 3.6 max_a = max(A) min_a = min(A) if max_a1: return 1 else: counter_a = dict(collections.Counter(A)) # print(counter_a) for i in range(1, max_a+1): if i not in counter_a: return i return max_a+1

나의 무궁무진한 슈퍼 블로거꿈을 위해, 코딜리티pdf를 한국어로 번역해보자. 떡상할수 있어 3.TimeComplexity 3.1. Comparison of different time complexities 3.2. Time limit 온라인 시험의 시간 제한은 보통 1초에서 10초까지입니다. 그러므로 우리는 시간 복잡성을 추측할 수 있습니다.(슈퍼 갓뎀 중요) • n

코딜리티는 발암이다... 시간 초과가 여기서 났다.. 나 울어ㅠ 알아서 엣지 포인트를 생각해야하는데 쉽지 않다. 시간 초과가 계속 나는데 진짜 창의적으로 돌아갔다. 다시 여기다. 테케 통과했다고 바로 submit 안하는 습관을 늘려야한다. 히든 케이스는 반드시 존재한다. 하다 안돼서 답봤다. def solution(N,A): li = {i:0 for i in range(1, N+1)} max_sum = 0 max_num = 0 for key in A: if key ==N+1: max_sum +=max_num li.clear() max_num = 0 else: if li.get(key) is None: li[key]=1 else: li[key]+=1 max_num = max(max_num, li[key])..

1. 프림 알고리즘 대표적인 최소 신장 트리 알고리즘 크루스칼 알고리즘, 프림 알고리즘 프림 알고리즘 시작 정점을 선택한후, 정점에 인접한 간선 중( 숲, 무리의 느낌으로 기억 ) 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해나가는 방식 크루스칼 알고리즘과 프림 알고리즘 비교 둘다, 탐욕 알고리즘을 기초로 하고 있다.( 당장 눈 앞의 최소 비용을 선택해, 결과적으로 최적의 솔루션을 찾는다.) 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 MST를 구한다. 프림 알고리즘은 특정 정점에서 시작, 해당 정점 연결괸 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선중에서 가장 가중치가 작은 간선..

문제 Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다. 먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다. 곡의 개수 N과 시작 볼륨 S..