문제풀이

[문제] https://www.acmicpc.net/problem/1350 1350번: 진짜 공간 첫째 줄에 파일의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아 www.acmicpc.net [풀이] 코드를 두 개 올렸는데(둘 다 맞음) 두 번째 코드가 첫 번째 코드를 간단하게 수정한 코드이다. 최종적으로는 입력 받은 파일크기가 몇 개의 클러스터에 저장하게 되는지 개수를 used 에 저장하고 used 에 클러스터 크기인 c_size 를 곱해주었다. [코드] if __name__ == '__main__': n = int(input()) f_size = list..

[문제] https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net [풀이] 지수인 b가 백만까지 가능한 걸로 봐서 딱 봐도 간단하게 a ** b 를 이용해서 풀 문제는 아닐 것 같았다. 우선 예제에서 나온 숫자로 규칙성을 찾아보니 1의 자리에 같은 숫자가 반복되는 규칙성이 있었다. 처음에는 제곱한 수의 마지막 자리를 인덱싱해 가져와 그 수가 베이스 수와 같은지 확인을 했다. 예를 들어 베이스 수가 9일 경우, 제곱한 수 81의 1의 자리 숫자 1은 9과 같지 않아..

[문제] https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] [코드] if __name__ == '__main__': n = int(input()) time_li = [int(x) for x in input().split()] ys = 0 ms = 0 for i in time_li: ys += (i//30 + 1) * 10 ms += (i//60 + 1) * 15 if ys < ms: print("Y", ys) elif ys == ms: prin..

[문제] https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net [풀이] 전에 풀었던 문제들에 비해 너무 쉬웠다. 풀이 설명할 것도 없음.. -_- [코드] if __name__ == '__main__': n = int(input()) i = 2 while n != 1: if n % i == 0: n /= i print(i) i = 2 continue i += 1

[문제] https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net [풀이] 처음에는 키 순으로 정렬 후 뭐 어찌어찌 풀어갈까 해서 코드를 짜던 중.. 생각해보니 정렬을 할 필요가 없는 것.. 왜 복잡도만 늘어나게 정렬을 하려 했지?? 과거의 내가 이해가 되지 않는다.. 이렇게 하나둘씩 배워가는 거겠지 하하 ^0^ 나름 간단한 코드가 완성되었는데 다행히도 맞았다!.. 예제를 입력했을 때 student_li = [(55, 185), (58, 1..

[문제] https://www.acmicpc.net/problem/17496 17496번: 스타후르츠 1, 11, 21, 31, 41 일에 스타후르츠 씨앗을 심으면 됩니다. 51일에 심으면 61일에 수확이 가능한데 여름은 60일까지 이므로 61일에는 수확할 수 없습니다. 따라서 총 5 * 300 = 1500개의 스타후르츠를 수확 www.acmicpc.net [풀이] 원래는 자바로 백준을 풀었어서 Python 외부 라이브러리를 사용할 수 없는지 몰랐다 ㅎㅎ 대표적으로 numpy를 사용해서 ModuleNotFoundError가 난다고 하는데 나는 sympy를 사용해서 런타임오류가 났다. 방정식 부분만 외부 모듈을 사용하지 않게 코드 수정 중 어이없게도 진짜 간단하게 풀 수 있었다.. 이렇게 비효율적인 코드라..

[문제] https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net [풀이] 1. 최대공약수 (GCD: Greates Common Divisor) 최대공약수를 구할 때 반복문을 사용해 알고리즘을 짰었는데 언뜻 봐도 시간복잡도가 O(n)이나 된다.. 시간복잡도를 줄일 다른 알고리즘을 찾아보니 유클리드 호제법(Euclidean algorithm)이 있었다!! 유클리드 호제법(Euclidean algorithm) 원리 : a, b의 최대공약수 == b와 a%b의 최대공약수 -> GCD(a, b) = GCD(b, a%b) a%b..