1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 더보기 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열..
힙
The K Weakest Rows in a Matrix - LeetCode Can you solve this real interview question? The K Weakest Rows in a Matrix - You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1 leetcode.com 문제 m x n이진 행렬 mat이 제공 되는데, 1의 개수가 가장 적은 k 개의 인덱스를 반환하는 프로그램을 작성하시오. 과정 힙을 활용해 문제를 풀어준다..
Maximum Product of Two Elements in an Array - LeetCode Can you solve this real interview question? Maximum Product of Two Elements in an Array - Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1). Example 1: Inpu leetcode.com 문제 정수 배열이 주어지면 해당 배열의 두 가지 다른 인덱스를 선택후 그 곱의 최대값을 반환합니다. 과정 가장 큰값과 두 번째로 큰값을 ..
Kth Largest Element in an Array - LeetCode Can you solve this real interview question? Kth Largest Element in an Array - Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct eleme leetcode.com 문제 배열과 숫자를 입력받고 배열 중 입력받은 K번째 큰 요소를 추출해라 과정 heapq 모듈을 이용해서 문제 풀이 heapq에서는 최대 힙을 제공하지 ..
힙이란? 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 항상 최대/최소의 값들이 필요한 연산이 있는 경우 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조 부모 노드의 값이 자식 노드의 값보다 항상 큼 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있게 된다. 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아니다 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞다 ..
해시 테이블 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 균일하게 분포 사용할 키의 모든 정보를 이용하여 해싱 해시 테이블 사용 효율이 높을 것 해싱 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 말한다. h(x) = x mod m 로드 팩터(Load Facto..
