에르미타쥬 에르미타쥬

힙이라는 자료구조는 무엇일까. 한 노드(node)가 최대 2개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 트리구조를 말한다.모든 노드의 값이 각자의 자식 노드의 값보다 크거나 같은 것을 최대 힙(Max heap)이라한다.모든 노드의 값이 각자의 자식 노드의 값보다 작거나 같은 것을 최소 힙(Min heap)이라한다.힙은 최대 힙이거나 최소 힙이어야 한다.또한, 마지막 레벨을 제외한 모든 노드가 꽉 채워진 완전이진트리(complete binary tree)이다. 이러한 힙 속성(최대 힙, 완전이진트리)를 만족하면 다음 그림처럼 트리구조가 완성된다.힙은 완전이진트리 성질을 만족하기 때문에 1차원 배열로도 표현이 가능하다. [100, 19, 36, 17, 3, 25, 1, 2, 7]..

이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는값보다 크면 그 값은 새로운 최댓값이 되며, 작은 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두배가 되므로 속도가 빠르다는 장점이 있다. 123456789101112131415def binary_search(target, data): data.sort() start = 0 end = len(data) - 1 while start

우선순위 큐의 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다. 즉, 우선순위가 다르다면 우선순위에 따라 원소들이 처리되지만 우선순위가 같은 경우 큐의 본래 특성인 선입 선출에 따라 큐가 처리된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#노드 클래스 생성class Node: def __init__(self, data, pri): self.data = data self.next = None self.pri = pri #우선순위 큐class Priority_Queue:..

node와 node사이의 연결을 이용해 데이터를 엮어내는 자료구조입니다. node를 정의하고 node.next를 정의해 다음에 올 node를 node.next에 담아 엮는 것입니다. 저는 오름차순으로 숫자를 추가하는 add 메서드, 링크드 리스트에 있는 노드를 조회하는 desc메서드, 원하는 노드를 삭제하는 delete 메서드를 구현 했습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051class Node: def __init__(self, data): self.data = data self.next = None class NodeMgmt: def __init__(self, data..

https://www.acmicpc.net/problem/5639전위 순회(Preorder traversal)는 기존의 트리구조를 그대로 보존해 다른 곳으로 옮길 수 있다는 장점이 있다. 이 문제에선 그 장점을 이용한다. 전위 순회 값을 받아 그대로 투입하면 온전한 트리구조를 만들 수 있다. 그 트리를 다시 후위 순회로 뽑아내기만 하면 된다. 하지만 보다시피 '실패' 예제 입력과 예제 출력을 충실하게 반영하므로 잘못 짠 것 같진 않다. 하지만 미세한 반례가 있는지 계속 틀리다고 한다. 내 생각엔 지금까지 풀어본 문제에 비해 이 문제의 입력 조건이 특이해서 그런 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142..

위의 움짤을 참고하면 이해하기 쉽다.맨처음 root노드가 등장한다. 추가된 노드는 root노드와 대소 비교를 통해 왼쪽서브트리로 빠지거나 오른쪽 서브트리로 빠진다.이후 추가된 노드들도 대소비교를 거쳐 왼쪽, 오른쪽 서브트리로 빠진다.​123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125..

https://www.acmicpc.net/problem/196612345678910111213141516171819202122T = int(input())for _ in range(T): NM = list(map(int,input().split(' '))) N = NM[0] M = NM[1] imp = list(map(int,input().split(' '))) judge = [0 for _ in range(N)] judge[M] = 'T' cnt = 0 if len(imp) == N: while True: if imp[0] == max(imp): cnt += 1 if judge[0] == 'T': print(cnt) break else: imp.pop(0) judge.pop(0) else: imp.a..

https://www.acmicpc.net/problem/10866 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class deque: def __init__(self): self.items = [] def push_front(self,x): self.items.insert(0,x) def pop_front(self): if len(self.items) == 0: return -1 else: return self.items.pop(0) def push_back(self,x): self.items.append(x) def pop_back(self): if len(self...