728x90 반응형 코딩/백준 리스트형 알고리즘 - Python / 백준 - 9084번 : 동전 9084번: 동전 (acmicpc.net) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 DP 알고리즘의 대표적인 문제다. 동전이 주어지고 , 그 동전들을 가지고 해당 금액을 만들 수 있는 경우의 수를 구하는 문제다. DP 점화식은 DP[I] = DP[I-K] + DP[I] 로 I 금액을 K 금액의 동전으로 만드는 경우를 이야기한다. 만약 1원 2원을 가지고 17원을 만드는 경우는 16원을 만드는 경우에 1원 동전을 사용하는 경우 , 15원을 만드는 경우에 2원 동전을 사용하는 경우 2.. 더보기 알고리즘 - Python / 백준 - 4150번 : 피보나치 수 4150번: 피보나치 수 (acmicpc.net) 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 풀이 1000자 이내의 피보나치 수를 구하는 문제다. 단순하게 배열을 통해 S[i] = S[i-1] + S[i-2]로 피보나치 수를 구하였다. 구할 때마다 1000자가 넘는지 혹은 이미 구할 숫자까지 왔는지 체크해서 break 하고 답을 출력하였다. a = int(input()) s=[0,1,1] idx = 3 while True: p = s[idx-1]+s[id.. 더보기 알고리즘 - Python / 백준 - 2581번 : 소수 2581번: 소수 (acmicpc.net) 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이 범위의 양 끝 값을 입력받고 , 그 범위 내의 모든 소수의 합과 가장 작은 소수를 출력하는 문제다. 최대 10,000 까지의 소수를 찾아야 하므로 단순하게 에라토스테네스의 체로 구현하였다. n=10001 def isPrime(a): if(a 더보기 알고리즘 - Python / 백준 - 8871번 : Zadanie próbne 2 8871번: Zadanie próbne 2 (acmicpc.net) 8871번: Zadanie próbne 2 Twój program powinien wypisać dwie liczby oddzielone pojedynczym odstępem. Pierwsza liczba to minimalna liczba zadań jaka może pojawić się podczas n rund punktowanych i jednej rundy próbnej w trakcie SKI'10. Druga liczba to maksymalna liczba zada www.acmicpc.net 풀이 및 문제 해석 브론즈 5 문제를 싹 밀다가 발견한 문제다. 문제 해석이 안돼서 힘들어하는 사람들이 있을까봐 블로그에 정리하기로.. 더보기 알고리즘 - Python / 백준 - 14677번 : 병약한 윤호 14677번: 병약한 윤호 (acmicpc.net) 14677번: 병약한 윤호 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 약을 먹어야 하는 날짜인 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄에는 3N개의 약의 상태가 주어지는데, 아침 약은 B, 점심 약은 L, 저녁 www.acmicpc.net 풀이 약봉투가 일렬로 있을 때 , 아침 , 점심 , 저녁 약을 순서대로 중간의 약봉투를 끊지 않고 먹을 수 있는 최대의 경우의 수를 구하는 문제다. 부분 문제의 답들이 모여 전체 문제의 답이 될 수 있으므로 , DP로 접근했다. DP 배열은 DP[왼쪽에서 뜯은 약의 개수][오른쪽에서 뜯은 약의 개수] = 그 단계의 최대 약의 개수로 두었다. 처음에 DP[1][0] (왼쪽에서 하나 뜯는 경우.. 더보기 알고리즘 - Python / 백준 - 9527번 : 1의 개수 세기 9527번: 1의 개수 세기 (acmicpc.net) 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 풀이 어떤 범위 안의 모든 이진수들의 1의 개수를 더해 출력하면 되는 문제다. 최대 범위가 10^16 이므로 단순하게 모두 세는 방법으로는 어렵다고 판단했다. 이진수의 특징 중 하나가 점점 수가 커짐에 따라 다음 자릿수에 1 혹은 0이 오므로 부분 문제를 전체 문제에 사용할 수 있다고 판단하고 , 이를 이용하기로 했다. 또한 어떠한 범위 내의 수를 구하는 문제이므로 누적합을 사용하기로.. 더보기 알고리즘 - Python / 백준 - 1418번 : K-세준수 1418번: K-세준수 (acmicpc.net) 1418번: K-세준수 첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을 때 그 수를 K-세준수 라고 하고 범위 내의 K-세준수가 몇 개인지 찾는 문제다. 에라토스테네스의 체를 활용해 각 수의 소인수중 최댓값을 배열에 저장하고 이후 배열을 돌며 조건을 만족하는지 확인하는 방법으로 문제를 해결하였다. import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) s = [0 for i in range(n+1)] for i in ra.. 더보기 알고리즘 - Python / 백준 - 1500번 : 최대 곱 1500번: 최대 곱 (acmicpc.net) 1500번: 최대 곱 세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다. 만약 S=10, K=3이면, 3,3,4는 www.acmicpc.net 풀이 S와 K가 주어졌을 때 , K개의 수를 가지고 S를 만든다. 이때의 K개의 수를 곱해서 나올 수 있는 가장 큰 수를 찾는 문제다. S를 K개의 수로 고르게 나누고 , 남는 나머지를 각각 K개에 될 수 있는 만큼 나눠주면 곱했을 때 가장 큰 경우가 나온다. 예를 들어 , S = 10 , K = 3의 경우 10을 3개로 고르게 나누므로 3 3 3이다. 고르게 나눈 후 나머지가 1 이므로 남는 나머.. 더보기 이전 1 2 3 4 5 6 7 8 ··· 13 다음 반응형
