728x90 반응형 코딩 리스트형 알고리즘 - Python / 백준 - 2467번 : 용액 2467번: 용액 (acmicpc.net) 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 오름차순으로 나열된 수들을 더해서 0이 되는 2개의 수를 구하는 문제다. 입력 자체가 오름차순으로 나열되어 있다는 점에서 힌트를 얻었다. 투 포인터를 사용해 좌측 , 우측에서 부터 수를 더해가면서 MIN 값과 비교한다. 만약 더한 값의 절댓값이 MIN보다 작으면 업데이트한다. 더한 값이 양수라면 0에 가까워지기 위해 양수 부분을 줄여야 하므로 뒤쪽 포인터를 앞으로 하나 민다. 더한값이 음수라면 0에 가까워지기.. 더보기 알고리즘 - 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.. 더보기 이전 1 ··· 3 4 5 6 7 8 9 ··· 17 다음 반응형
