문제 출처: www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 1. 문제 접근 방식 - 동전을 리스트 형태로 받아 가장 큰 수부터 차근차근 나눠 가는 방법을 생각하였다. 2. 내가 푼 코드 import sys N, K = map(int, sys.stdin.readline().split()) coin = [] cnt = 0 for i in range(N): coin.append(int(sys.std..
현재 대부분의 스마트폰은 리튬이온전지를 사용하고 있다. 무게와 배터리 용량에 많은 관심을 기울이다 보니 어쩔 수 없는 선택일지도 모른다. 하지만 일반적으로 리튬이온배터리의 경우 충전 횟수의 한도가 지나면 배터리 성능이 급격히 줄어든다. 여기서 충전 사이클에 대해 한번 이해 해볼 필요가 있다. 충전 사이클이란? 충전 사이클의 개념은 '100% 충전을 얼마나 했는가'로 이해하면 편할 것이다. 남은 퍼센트가 몇 퍼센트인지 상관없이 100%를 한번 채우고 나면 사이클 횟수가 1 증가하게 된다. 배터리는 사이클 횟수가 굉장히 중요하다. 우리가 처음 산 핸드폰을 켰을 때 배터리가 100%가 아닌 절반 즈음만 채워져 있는 이유이기도 하다. 이뿐 아니라 배터리는 완전 방전, 완전 충전에도 영향을 많이 받는다. 완전 방..
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..
