[파이썬] 백준 1929 소수 구하기, 소수 판별법
백준 1929 문제풀이https://www.acmicpc.net/problem/1929풀이소수란1과 자기 자신으로밖에 나누어 떨어지지 않고, 자기 자신의 곱셈의 역수가 없는 수소수 예시101, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 2,3,5,7알고리즘어떤 수 N 이하의 수로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수여기서 N 이하는 N의 양의 제곱근 이하의 수로 판별할 수 있는 것이 key point→ math 모듈의 sqrt() 함수 활용아래와 같이 주어진 입력값 기반의 반복문으로 풀면 시간초과 발생import sysvar = sys.stdin.readline().rstrip().split(" ")rtn = ""for i in range(int(var[0]), int(..
2024. 6. 17.
[파이썬] 백준 2609 최대공약수, 최소공배수
백준 2609 문제 풀이https://www.acmicpc.net/problem/2609풀이최대공약수와 최소공배수는 파이썬의 math 모듈의 gcd(), lcm() 함수로 구할 수 있다. 최대공약수란0이 아닌 두 정수 n과 m이 서로 공통으로 가지고 있는 약수 중 가장 큰 수를 말한다.약수란어떤 수를 나누어 떨어지게 하는 수6 은 1,2,3,6 이 약수두 수를 곱해서 어떤 수를 나오면 그 두 수가 약수최대 공약수 예시 : 12와 20인 경우12 : 1, 12, 2, 6, 3, 4 정렬하면 1, 2, 3, 4, 6, 1220 : 1, 20, 2, 10, 4, 5 정렬하면 1, 2, 4, 5, 10, 20같은 약수중에 제일 큰 것은 4. 최대공약수는 4☞ 참고 사이트 최대공약수 - 위키백과, 우리 모두의 백..
2024. 6. 16.
백준 1003 피보나치 함수, 다이나믹 프로그래밍 DP (with 파이썬)
피보나치 수열 알고리즘 문제 풀이▶ 백준 문제풀이 1003https://www.acmicpc.net/problem/1003피보나치 수열이란연속한 두 수의 합이 그다음 수가 되는 수열{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... }재귀적으로 표현 가능Fn = Fn-1 + Fn-2 또는 Fn+1 = Fn + Fn-1단, F0 = 0, F1 = 1참고 사이트 피보나치 수열Fibonacci Numbers, 피보나치 수www.ktword.co.kr다이나믹 프로그램이란답을 재활용 하는 방법앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다.이미 구했던 값은 메모리에 담아두고 필요시 메모리에서 값을..
2024. 6. 13.
