2022. 4. 18. 16:51ㆍ알고리즘(Python)/백준
https://www.acmicpc.net/problem/3036
<문제>
첫번째 원이 돌아갈 때 다른 원들은 몇 번을 도는지를 계산해 출력하는 문제다.
<풀이>
1. 일단 첫번째로 원이 회전하는 것은 원의 둘레에 따라 달라지고 원의 둘레를 구하는 식은 2ㅠr인데 2ㅠ는 약분되어 사라지므로 영향을 미치는 요소는 r만 남게 된다. 따라서 원의 반지름의 길이가 곧 얼마나 회전하는지를 결정하는 요소이므로 원의 반지름 길이의 비율을 출력하면 된다.
2. 출력할 비율을 기약분수 형태로 나타내려면 어떻게 해야 할 지 생각해보았다. 기약분수는 더 이상 공통된 수로 나눠지지 않는 수이므로 가장 큰 공통약수로 나눈면 더 이상 나눠지지 않을거라는 생각을 했고, 가장 큰 약수를 구하는 개념은 최대공약수이다.
3. 따라서 원들의 반지름을 첫번째 원과의 최대공약수로 나누면서 그 값을 저장해 출력하면 된다고 생각했다.
<코드1>
import math
n = int(input())
numList = list(map(int, input().split()))
answer = ""
for i in range(1, len(numList)):
gcd = math.gcd(numList[0], numList[i])
answer += f"{numList[0]/gcd:0.0f}/{numList[i]/gcd:0.0f}\n"
print(answer)
32952 kb | 88 ms |
<코드2>
from collections import deque
import math
from sys import stdin
n = int(input())
numList = list(map(int, input().split()))
for i in range(1, len(numList)):
gcd = math.gcd(numList[0], numList[i])
print(f"{numList[0]/gcd:0.0f}/{numList[i]/gcd:0.0f}")
33020 kb | 88 ms |
위의 코드는 정답 문자열을 저장하지 않고 바로 출력하면 메모리를 적게 사용할 수 있지 않을까? 하는 생각에 시도해 보았는데 차이는 없었고, 오히려 아주 약간 메모리가 증가하는 결과를 보였다.
이를 통해, 정답을 변수에 저장해서 한 번에 출력을 하던 바로바로 출력을 하던 결과에는 큰 차이가 없다는 것을 알 수 있었다.
<코드3>
def GCD(a,b): return GCD(b,a%b) if b else a
N = int(input())
li = list(map(int, input().split()))
result = ''
for i in range(1,len(li)):
tmp = GCD(li[0],li[i])
result += str(li[0]//tmp) + '/' + str(li[i]//tmp) +'\n'
print(result)
30840 kb | 68 ms |
이 코드와 내가 작성한 코드의 차이는 최대공약수(GCD)를 구하는 방식이다. 나는 math클래스의 gcd( )를 사용해서 구했는데 여기서는 직접 계산해 값을 반환했고, 여기서 속도의 차이가 난 것으로 보인다.
평소에는 gcd함수를 사용하는 것이 편하지만 익숙해지거나 속도를 조금이라도 더 빨리 내야 한다면 직접 계산하는 방식을 사용하는 것이 좋을 것 같다.
'알고리즘(Python) > 백준' 카테고리의 다른 글
[3986] 좋은단어 (C#) (0) | 2022.09.13 |
---|---|
[백준] 1931. 회의실 배정 (0) | 2022.04.22 |
[백준] 2606. 바이러스 (0) | 2022.04.15 |
[백준] 2010. 플러그 (0) | 2022.04.10 |
[백준] 1260. DFS와 BFS (0) | 2022.04.07 |