목록2024/06/26 (2)
NIRVANA
1. 힙 주요 연산 힙 생성(heapify): 배열에서 힙을 생성하는 프로세스, 전체 요소 검사 → O(n) 시간 복잡도 삽입: 기존 힙에 요소를 삽입하는 과정, O(logn) 시간 복잡도 삭제: 힙의 최상위 요소 혹은 우선순위가 가장 높은 요소를 삭제한 후, 나머지 요소로 다시 힙을 생성, O(logn) 시간 복잡도 찾기(peek): 힙에서 가장 우선순위가 높은 요소를 찾는 것, 루트 노드를 찾으면 되므로 O(1) 시간 복잡도를 가짐 2. 파이썬에서 힙 구현 파이썬에서는 heapq 라이브러리를 사용하여 힙 구현 가능heapq는 최소 힙을 사용import heapq nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]heapq.heapify(nums)print(nums) #[0, 1..
1. 문제 자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항3 ≤ n ≤ 1,000,000 2. 문제 풀이 방법 10 - 1 = 912 - 1 = 117 - 1 = 6 과 같이 n을 1로 나누었을 때 나오는 몫을 소인수 분해하면, n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 찾을 수 있는 것을 확인할 수 있다. 1) n-1 값이 소수인지 확인한다.2) 만약 n-1이 소수라면 바로 값을 return한다.3) n-1이 소수가 아니라면 n-1의 약수를 구한 뒤 가장 작은 약수를 반환한다. def solution(n): a..