https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 문제 N개의 줄을 교체하려고 한다. 6줄 패키지를 사거나 1개 또는 그 이상의 줄을 낱개로 살 수 있다. 이때 M개의 브랜드에 따른 패키지가격과 낱개 가격이 주어질 때 기타줄을 교체하는데 최소금액을 구하라. 2. 접근 1. M개의 브랜드를 모두 포함하여 최소 패키지 금액과 최소 낱개 금액을 구한다. 2. 패키지와 낱..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 1. 문제 문자열 A, B가 주어진다. A는 B보다 같거나 짧다. 1. A의 앞에 아무 알파벳을 추가한다. 2. A의 뒤에 아무 알파벳을 ..

https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는 www.acmicpc.net 1. 문제 숫자가 주어질 때, 해당 자릿수 숫자들의 조합으로 30의 배수 중 최대값을 만들어서 출력한다. 없을 경우 -1을 출력한다. 2..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 www.acmicpc.net 1. 문제 여러 로프와 각 로프의 최대중량이 주어질 때 해당 로프들의 조합으로 들 수 있는 최대 중량을 구하라. 2. 접근 여러 로프들에서 들 수 있는 중량이 가장 작은 로프부터 하나씩 제외해가며 최대중량을 비교한다. 3. 소스코드 n = int(input()) rope = [int(input()) for _ in range(n)] def w(rope, n): rope.sort() max_w..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 문제 각 사람이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하라. 2. 접근 뒷사람은 앞사람이 먼저 끝나야 업무를 처리할 수 있다. 따라서 처리시간이 가장 짧은 사람먼저 업무를 수행하는 것이 가장 빠르다. 그러므로 다음과 같이 수행한다. 1. 업무 처리시간을 오름차순으로 정렬 2. 뒤사람의 처리시간은 앞사람의 처리시간 + 자신의 처리시간 3. 소스코드 n = int(input()) time = list(map(int,..

1. 동전 거스름돈 2. 이항계수 1. 동전 거스름돈 사용할 수 있는 동전의 종류 : 1원, 4원, 6원 이때, 거스름돈 8원에 대한 최소 동전 개수는 몇개인가? 그리디 - 6원, 1원, 1원 최적해 - 4원, 4원 => 완전 검색 방법 또는 동적계획법 1원을 선택하는 경우 - 1원 동전 한개 + 나머지 7원에 대한 최적해 4원을 선택하는 경우 - 4원 동전 한개 + 나머지 4원에 대한 최적해 6원을 선택하는 경우 - 6원 동전 한개 + 나머지 2원에 대한 최적해 위의 3가지 중에서 최적해를 선택한다 > 7원에 대한 최적해는 다시 1원, 4원, 6원 동전을 선택하고 나머지 액수에 대한 최적해이다. 재귀 알고리즘에 메모이제이션 적용 change : 거스름돈 금액, coin = [6, 4, 1], 동전종류 ..

1. 피보나치 수 2. 수학적 귀납법과 비둘기 집의 원리 3. 메모이제이션과 동적계획법 1. 피보나치 수 > 현재 항의 값은 전항과 전전항의 합이다. > f(n+2) = f(n) + f(n+1) - 레오나르도 피보나치가 연구한 수열 0, 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열 > 0, 1, 1, 2, 3, 5, 8, 13 피보나치 수열의 n번째 값을 계산하는 함수 F의 정의 > F(0) = 0, F(1) = 1 초기값 > F(n) = F(n-1) + F(n-2), n >= 2 1) 재귀함수로 구현 def fibo(n): if n < 2: return n else : return fibo(n-1) + fibo(n-2) n이 2미만일 경우, 즉 n이 0일 때는 0을 리턴하고, 1일 때는 1..

https://codeup.kr/problem.php?id=3720 nCr (Hell) 첫째 줄에 n, r이 주어진다. ( 0

https://codeup.kr/problem.php?id=3014 정렬을 빠르게! 첫 줄에 데이터의 개수 N이 입력된다. ( 1

https://codeup.kr/problem.php?id=3019 스케줄 정리 5 sleep 2014 05 23 golf 2014 06 02 travel 2015 11 22 baseball 2013 02 01 study 2014 05 23 codeup.kr 1. 문제 날짜별를 기준으로 스케줄을 정리한 후 스케줄명을 출력하라. 2. 알고리즘 주어진 문자열을 날짜를 기준으로 정렬한 후 스케줄명을 출력한다. 년도, 월, 일, 스케줄명 사전순으로 비교하여 정렬한다. 3. 팁 python에서 제공하는 sorted함수를 사용하면 매우 쉽게 문제를 풀 수 있다. python에서 정렬 혹은 비교와 같은 함수들은 모두 기준(key)를 정할 수 있다. 4. 소스코드 # 입력처리 n = int(input()) schedu..