PengTory

문제: 백준 1312 소수 https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. A÷B를 했을 때, 소숫점 아래 N번째 수를 출력해주는 문제이다. 해결 과정 문제의 제약조건에 있는 N이 100만까지였기 때문에 그냥 나누어서 n+1 자리를 출력하려..

유클리드 호제법이란? (최대공약수 구하기) 유클리드 호제법 또는 유크리드 알고리즘은 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로 상대방 수를 나누어 결국 원하는수를 얻는 알고리즘을 나타낸다. 예시 * mod란 나머지 연산을 의미한다. 1071, 1029의 최대공약수 1) 1071은 1029로 나누어 떨어지지 않기 때문에 1071 mod 1029를 계산한다. => 42 2) 1029는 42로 나누어 떨어지지 않기 때문에 1029 mod 42를 계산한다. => 21 3) 42는 21로 나누어떨어진다. => 최대공약수: 21 24와 18의 최대공약수 1) 24와 18은 나누어 떨어지지 않기 때문에 24 mod 18을 계산한다. => 6 2) 18은 6으로 나누..

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ 1번 시도 -> 잘 돌아가는가 했으나 Time Limit Exceeded 2중 for문을 사용해 브루트포스 방법으로 모든 경우의 수를 돌려보려 했으나 시간복잡도가 O(n^2)여서 Time Limit에 걸린 것 같음 이중 for문을 사용하지 않는 방식을 고려해보자 class Solution: def maxProfit(self, prices: List[int]) -> int: # small이 무조건 가장 작은 값이 아님 -> 계산을 한 값을 넣어야 할 것 같음 small = prices[0] profit = [] minIndex = 0 for i in range(len(prices)): if pr..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 짜는 문제이다. 나는 이 문제를 모든 경우를 대입해보는 브루트포스 - 재귀 방법으로 풀어보았다. go()라는 함수에는 합을 나타내는 sum과 문제에서 제공해주는 정수 n 값을 인자로 받는다. 함수의 종료 조건은 다음과 같다. 1) 1,2,3 들의 합(sum)이 n을 넘어가면 함수를 종료 2) sum과 n이 일치하면 우리가 찾는 결과이기 때문에 count를 +1 해준다. sum이 아직 n보다 작다면 1을 ..