알고리즘 정복하기! 64

백준 9613번 Python / Math 문제 링크 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 import math t = int(input()) answer=0 for _ in range(t): data = input().split() del data[0] for i in range(len(data)-1): cnt = len(data) for j in range(cnt): if i < j: answer += math.gcd(int(data[i]), .. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 1934번 Python / Math 문제 링크 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 풀이 import math t = int(input()) for _ in range(t): a,b = map(int, input().split()) gcd = math.gcd(a,b) lcm = a*b // gcd print(lcm) math 라이브러리를 불러 와 math.gcd() 함수를 사용해 최대공약수를 구했습니다. 그 이후에 두 수의 곱에 최대공약수를 나누어 .. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 1049번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 n,m = map(int, input().split()) prices = [] min_prices = [] for _ in range(m): prices += list(map(int, input().split())) min_prices.append(min(prices[::2])) min_prices.append(min(prices[1::2])) if min_prices[0] >.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 1439번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 S = input() split_one = S.split('1') split_zero = S.split('0') cnt1 = split_one.count('') cnt2 = split_zero.count('') print(min(len(split_one)-cnt1, len(split_zero)-cnt2)) 입력한 문자열을 받아 1과 0으로 각각 .split()을 해주었습니다. ex.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 9461번 Python / Dynamic Programming 문제 링크 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 T = int(input()) arr = [0] * 101 arr[0] = 1 arr[1] = 1 arr[2] = 1 for i in range(0,98): arr[i+3] = arr[i] + arr[i+1] for _ in range(T): n = int(input()) print(arr[n-1]) 1 1 1 2 2 3 4 5 7 9 12 16 ... 규칙을 보면 i+3 번째의 수가 .. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 2609번 Python / Math 문제 링크 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 import math num1, num2 = map(int, input().split()) gcd = math.gcd(num1,num2) print(gcd) print(num1*num2//gcd) math 라이브러리를 불러와 최대공약수를 구해주는 gcd()함수를 사용했습니다. replit에서 math.lcm() 을 사용하니 오류가 발생하여 최소공배수는 직접 구했습니다. 최소공배수는 두 수의 곱 / 최대공약수를 하면 구할 수 있기 때문에 계산을 진행.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 11.
백준 10610번 Python / Greedy 문제 링크 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 풀이 N = list(input()) N.sort(reverse=True) sum = 0 if '0' not in N: print(-1) else: for i in N: sum += int(i) if sum%3 != 0: print(-1) else: print(''.join(N)) 30의 배수가 될 수 있는 조건은 끝자리가 0이면서 각 자리 수의 합이 3의 배수여야 합니다. 처음에 내림차.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 10.
백준 1929번 Python / Math 문제 링크 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 m,n = map(int, input().split()) state = 0 for i in range(m, n+1): state=0 if i > 1: for j in range(2, i): if i % j == 0: state += 1 if state == 0: print(i) 처음에는 위와 같은 풀이로 진행했습니다. 2부터 i-1 까지 모든 수를 체크해가며 출력하다보니 시간 초과가 발생했습니다. import m.. 알고리즘 정복하기!/백준 문제풀이 2022. 2. 10.

티스토리툴바