코딩테스트

오늘은 heap에 대해서 알아보겠다. 우선 heap을 한단어로 설명하자면 규칙을 가진 이진트리이다. 이진트리가 무엇이냐면 각각의 노드가 최대 2개의 자식노드를 가진 트리를 말한다. 자식노드는 왼쪽 자식과 오른쪽 자식노드로 나뉜다. 다음으로 규칙으로는 최소힙과 최대힙이 있는데, 최소힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 말하고 최대힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 말한다. 위 그림처럼 두개의 자식노드만 가지면서 왼쪽 자식은 부모노드의 index*2 위치에 넣고, 오른쪽 자식은 부모노드의 index*2+1위치에 넣는다. 우선 힙은 첫번째 인덱스를 0으로 하면 계산이 복잡해져서 1로 두고 10을 인덱스 1위치에 넣는다. 다음으로 15는 1*2위치인 인덱스 2에..

문제 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 코드 My answer import sys import heapq input=sys.stdin.readline n=int(input()) heap = [] for i in range(n): tmp=int(input()) if(tmp!=0): heapq.heappush(heap, (-tmp, tmp)) else: if(heap==[]): print(0) else: result=heapq.heappop(heap) print(result[1])..

문제 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 코드 My answer from collections import deque T = int(input()) for _ in range(T): L = input() left = deque() right = deque() for i in L: if(i==""): if(len(right)!=0): left.append(right.popleft()) elif(i=="-"): if(len(left)!=0): left.pop() else: left.append..

문제 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 코드 My answer import sys from collections import deque input=sys.stdin.readline n,m=map(int,input().split()) a=deque([i+1 for i in range(n)]) b=list(map(int,input().split())) cnt=0 while(len(b)!=0): if(a[0]==b[0]): a.popleft() b.pop(0) else: ind=a.index(b[..

문제 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline from collections import deque tc=int(input()) for _ in range(tc): n,m=map(int,input().split()) imp=deque(map(int,input().split())) doc=deque([i for i in range(n)]) i=1 m=doc[m] while(1): if(max(imp)==imp[0]): i..

문제 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 코드 My answer import sys input=sys.stdin.readline t=int(input()) for i in range(t): n1=int(input()) note1=list(map(int,input().split())) n2=int(input()) note2=list(map(int,input().split())) result=set(note1)&set(note2) for j in note2: if(j in result):print(1) e..