1. 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 가장 단순하지만 강력한 문제 해결 방법 -> 탐욕법 현재 상황에서 당장 가장 좋은 것만 고르는 방법 현재의 선택이 나중에 미칠 영향까지는 고려하지 않음 유형이 매우 다양하기 때문에 문제를 많이 접하면서 훈련하는 것을 추천 문제를 풀기위한 최소한의 아이디어를 생각해낼 수 있는 능력 요구 = 창의력 예제: 거스름돈 문제 설명: 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하고 거스름돈이 N원일 때 거슬러줘야 할 동전의 최소 개수 (단, N은 항상 10의 배수) 내가 푼 코드 import sys N = int(sys.stdin.readline()) a = N // 500 N = N % 500 b = N..
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 ..
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..
Chapter4 - 기본 추상자료형 4.1 리스트 ADT 4.1.1 추상자료형이란 ADT(Abstract Data Type): 인간이 데이터를 다루는 관점에서 데이터구조를 명세한 것 다루는 데이터 데이터에 대한 작업들 발생 가능한 에러상황들 4.1.2 리스트ADT 연속적인 임의 개체들 모델링 4.1.3 리스트 ADT 메소드 일반 메소드 integer size(): 원소 수 반환 boolean isEmpty(): 비어있는지 확인 iterator elements(): 원소 전체 반환 접근 메소드 element get(r): r에 저장된 원소 반환 갱신 메소드 element set(r, e) add(r, e) addFirst(e) addLast(e) element remove(r) element removeF..
