목록2024/02 (99)
미소를뿌리는감자의 코딩
https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 1. 접근 방법 홀수 인 경우 막대기를 길이가 1이 될 때까지 잘라야 한다. 만약 23을 구하고 싶다면 따라서 필요한 막대기 수에 += 1 을 해주고, 23 -> 22 로 바꾸어서 생각하였다. ex) 22 = 16 + 4 + 2의 막대기를 더해주어야 한다. 그랬을 때, 22에 가장 가깝지만, 22 보다 작은 16(2^n) 을 구해준 후, 22- 16을 해준다. 더불어서 필요한 막대기 수에 +=..
힙 -> 완전 이진 트리 이어야함. ; 왼쪽 부터 꽉 채워져 있는 것. index 계산: 계산 편의를 위해 인덱스를 1부터 사용: parent: x. left: 2x. right: 2x + 1 def __len__(self):... def _percolate_up(self): # percolate 스며들다 cur = len(self) parent = cur // 2 # left : 2* cur, right = 2*cur + 1 이므로, parent는 cur//2 while parent > 0: if self.items[cur] > self.items[parent]: self.items[cur], self.items[parent] = self.items[parent], self.items[cur] cur ..
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 접근 방법 직관적인 문제인 것 같다. 0이 나오면 heappop해서 출력, 비어있다면 0 출력 값이 나오면 heap 에다가 저장. 유의해야할 점은 input이 아니라 sys를 이용해야한다는 점이다. input으로 제출을 하니 시간초과가 나왔다. 코드 상으로는 문제가 없다고 확신했기 때문에, sys를 적용하였고 통과할 수 있었다. 주의해야할 점은, python의 경우 최..
https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 접근 방법 직관적인 문제인 것 같다. 0이 나오면 heappop해서 출력, 비어있다면 0 출력 값이 나오면 heap 에다가 저장. 유의해야할 점은 input이 아니라 sys를 이용해야한다는 점이다. input으로 제출을 하니 시간초과가 나왔다. 코드 상으로는 문제가 없다고 확신했기 때문에, sys를 적용하였고 통과할 수 있었다. 2. 코드 import heapq impor..