개발 기록기록📝

Heap 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조입니다. 부모노드와 자식 노드 사이에 대소 관계가 성립하며(자식 노드간에는 대소관계 없음) 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 최대 힙, 부모 노드의 키 값이 자식 노드의 키 값보다 작은 힙을 '최소 힙'이라고 합니다. 위 이미지는 최대 힙을 나타냅니다. 파이썬 heapq 모듈 인덱스 k번째 노드는 그 자식 노드 2K+1과 2K+2 보다 항상 작은 최소 힙의 형태로 정렬되게 합니다. heapq.heappush(list, item) : item을 list에 추가 heapq.heappop(list) : list에서 가장 작은 원소를 pop, 리..

시간복잡도(time complexity) 시간복잡도(time complexity)란 가장 널리 사용되는 알고리즘의 수행 시간 기준입니다. 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것입니다. 기본적인 연산이란 더 이상 쪼갤 수 없는 최소 크기의 연산이라고 생각하시면 됩니다. 예를 들어 다음은 기본적인 연산이라고 볼 수 있습니다. 두 부호 있는 32비트 정수의 사칙연산 한 변수에 다른 변수 대입하기 가장 깊이 중첩된 반복문의 내부에 있는 기본적 연산들은 더 쪼갤 수 없기 때문에 이것이 시간 복잡도의 대략적인 기준이 됩니다. 시간복잡도가 높다 입력의 크기가 증가할 때 알고리즘 수행 시간이 더 빠르게 증가한다는 의미입니다. 시간복잡도가 낮다고 언제나 더 빠른것은 ..