Algorithm/Math5 [백준] 10166번 관중석 _ Python https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 1. Preview 시간 복잡도: O(N^2) 공간 복잡도: O(N^2) 참고 : https://burningjeong.tistory.com/525 유형: 수학 2. 초기 접근 방법 각도에 따라 의자를 배치하도록 했다. 하지만 이 방법은 부동소수점 오차로 인해, 기존에 놓았던 각도인지 판별이 불가능하다. circle = set() for i in range(a, b+1): init = 360 / .. 2024. 3. 23. [백준] 1676번 팩토리얼 0의 개수 _ Python https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Preview 시간 복잡도: O(N) 공간 복잡도: O(1) 유형: 수학 2. 초기 접근 방법 N! 값을 계산하고 결과값(처음으로 0이 아닌 숫자가 나올 때까지 0의 개수)을 구하기에는 N!의 값이 너무 커진다. N! 의 값을 구할 때 1의 자리만 남겨줘도 0의 개수를 구할 수 있기 때문에, N! 계산 도중. 10으로 나눠질 경우 바로 나눠주어 zeroCount를 진행해준다. 3. 생각 - 4. 코드 N = int(input()) fact = 1 zeroCount = 0 for.. 2024. 3. 21. [백준] 1676번 팩토리얼 0의 개수 _ Python [초기 접근 방법] 1. N! 을 구하자 2. 0의 개수를 세자 [생각] 위와 같이 심플한 방법으로 접근하면 문제에서 N의 범위가 500까지이기 때문에 'OverflowError'가 발생한다. 따라서 OverFlow를 방지하기 위해 N!을 하는 과정에서 수의 크기를 관리해주어야 한다. 이 때, N!의 1의 자리만 보존해도 되기 때문에 다음과 같이 코드를 작성한다. # 10으로 나눠질 경우 if fact % 10 == 0: while True: # 1의 자리만 남기도록 한다. if fact % 10 != 0: fact %= 10 break fact /= 10 zeroCount += 1 [코드] # 풀이 시간 : 10 + 25분 # 시간복잡도 : O(N) # 공간복잡도 : O(1) # 참고 : - # 왜 .. 2024. 2. 18. [백준] 18110번 solved.ac _ Python [초기 접근 방법] 1) 상위 15%, 하위 15% 절사 - 이 때, 소수점은 반올림 계산 2) 계산된 평균 반올림 계산 [생각] 1) 수식을 작성할 때, "0 / x" 와 같은 ZeroDivision 주의 2) 파이썬의 반올림은 ".5"와 같이 올림, 내림했을 때 동일하게 차이가 나는 경우에는 짝수 값으로 반올림 합니다. → 따라서 파이썬으로 풀 경우, epsilon. 즉 굉장히 작은 값을 더해 우리가 일반적으로 생각하는 반올림이 될 수 있게끔 해야 한다. [코드] # 풀이 시간 : 20분 # 시간복잡도 : O(NlogN) # 공간복잡도 : O(N) # 참고 : python round() 관련 자료 # https://blockdmask.tistory.com/418 import sys input = sy.. 2024. 2. 17. [백준] 1011번 Fly me to the Alpha Centaur _ Python [초기 접근 방법] 1) 문제 조건 위배 (x) def solve(move): if move = move: break return k - 도착 직전 이동거리가 1광년이라는 것을 고려하지 않았다. 2) dp (x) dp[i] : i 위치까지 가는데, 장치 작동 횟수의 최솟값 점화식 k : 직전에 이동한 거리 +- 1 dp[i] = dp[i-k] + 1 dp[i+k] = min(dp[i+k], dp[i] + 1) - 경우의 수가 매우 많아진다. [생각] - 수학적인 규칙을 찾는 문제이다. - 빠른 유형 파악과, 노트에 끄적이면서 수학적인 규칙을 빨리 찾는 훈련이 필요할 듯하다. [코드] # 풀이 시간 : 35분 + 40분(dp) + 30분 # 시간복잡도 : O(1) # 공간복잡도 : O(1) # 참고 : h.. 2024. 2. 8. 이전 1 다음
