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..

https://codeup.kr/problem.php?id=3004 데이터 재정렬 50 23 54 24 123 에서 23, 24, 50, 54, 123 순서로 0, 1, 2, 3, 4 가 된다. 그리고 원래의 위치대로 출력한다. codeup.kr 1. 문제 데이터를 오름차순으로 정렬했을 때의 순위를 각 원소 순위에 맞게 출력하라. 2. 알고리즘 데이터를 정렬하여 순위를 찾고 해당 순위를 각 원소에 부여한다. 3. 주의할 점 python에서 제공하는 index()함수는 시간복잡도가 O(N)이므로 이 함수를 이용했을 경우에는 시간초과가 발생한다. 따라서 binary search를 구현하고 해당 알고리즘을 사용해서 index를 찾아야한다. 4. 소스코드 n = int(input()) # 입력 처리 data =..

https://codeup.kr/problem.php?id=3006 완전 제곱수 찾기 $n \times n = n^2$을 만족하는 $n^2$을 완전 제곱수라고 한다. $k$개의 숫자 $a_1, a_2, a_3, ... , a_k$가 제시되면, 각각의 수보다 같거나 작은 가장 큰 완전 제곱수를 구하여라. 단 이 문제는 코드에 sqrt라는 텍스트가 나와서는 안 된다. 금지 키워드 : sqrt codeup.kr 1. 문제 주어진 값보다 크지 않으며 가장 큰 완전 제곱수를 구하라. 2. 알고리즘 주어진 값의 제곱근을 구한 뒤, 소수점을 버린 후에 다시 제곱한다. 3. 주의할 점 sqrt를 사용하면 안된다. **는 써도 되겠지만 그러면 sqrt를 쓰지않는 의미가 없다. 따라서 제곱근을 수행하는 함수를 만들어야한다..