문제 출처: 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..
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..
