Chapter6 - 힙과 힙 정렬 6.1 힙 힙(heap)은 내부노드에 키를 저장하면서 두 가지 속성을 만족하는 이진트리 힙순서(heap-order): 모든 부모-자식 관계에서 부모노드의 키가 자식노드의 키보다 작거나 같도록 구성된 이진트리 완전 이진 트리(complete binary tree)로 구성 6.1.1 힙의 높이 n개의 키를 저장한 힙의 높이는 O(log n) 6.2 힙을 이용한 우선순위 큐 구현 힙을 이용하여 우선순위 큐 ADT 구현 가능 6.2.1 힙에 삽입 삽입 노드 z, 새로운 마지막 노드 찾음 k를 z에 저장 후 z을 내부노드로 확장 힙순서 속성 복구 Alg insertItem(k) input key k, node last output none 1. advanceLast() 2. z ..
문제 출처: www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. 문제 접근 방식 - 일단 100을 기준으로 나눠야 한다. 두자리 수일 때는 항상 성립하지만 세 자리 수일 경우는 등차수열을 성립하는지 조건을 확인해야만 한다. 세 자리 수 밖에 없으므로 간단하게 각 자리 숫자들끼리 빼서 확인한다. 2. 내가 푼 코드 import sys N = int(sys.stdin.readline()) num = 0 # 100 보다 작은 경우는 다 등차수열 성립 -> count..
문제 출처: www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. 문제 접근 방식 - 위에서 밑으로 내려가면서 계속해서 값을 대체하는 방법을 이용해야 겠다고 생각하였다. 양 끝의 숫자들은 하나의 경우만 고려하면 되는데 가운데 있는 숫자들은 두 가지 중 큰 수를 골라야 했다. 하지만 파이썬은 max()함수가 있다! 2. 내가 푼 코드 import sys n = int(sys.stdin.readline()) num = [] s = 2 for i in range(n): num.append(list(map(int, sys.stdin.re..
Chapter5 - 우선순위 큐 5.1 우선순위 큐 ADT 정렬에 자주 응용 5.1.1 우선순위 큐 ADT 임의의 데이터 항목이 삽입되며, 일정한 순서에 의해 삭제되는 데이터구조 일반적인 큐와 비교했을 때 삽입과 삭제가 가능한 것은 동일하지만 일반적인 큐는 삽입 순서 그대로 삭제되고 우선순위 큐는 키 순서에 따라 삭제 5.1.2 우선순위 큐 응용 정렬(Sort): 데이터원소들을 일정한 키 순서에 의해 다시 배치하는 것 5.1.3 우선순위 큐 ADT 메서드 주요 메서드 insertItem(k, e): 키 k인 원소 e를 큐에 삽입 element removeMin() 일반 메서드 integer size() boolean isEmpty() 접근 메서드 element minElement() element min..
