알고리즘 PS/알고리즘8 [Python] 다이나믹 프로그래밍 (DP) 다이나믹 프로그래밍이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 의미한다. 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그 결과들을 결합하여 답을 구한다. 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는, 메모리 공간을 조금 더 사용함으로 연산 속도를 늘릴 수 있는 알고리즘 설계 기법이다. 예시 이렇게 글로만 보면 확 와닿지 않는다. 그럼 예시를 한 번 보도록 하자. 다이나믹 프로그래밍(이하 DP)으로 해결할 수 있는 대표적인 문제 예시로 피보나치 수열이 있다. n번째 피보나치 수는 n-1번째 수 더하기 n-2번째 수이다. 이걸 정리하면 f(n) = f(n-1) + f(n-2)이다. def fibo(n): if n == 0: retu.. 2022. 1. 15. [Python] 소수 찾기 알고리즘 소수란? 1보다 큰 자연수 중, 1과 자기 자신 외에는 나누어지지 않는 수 누가 알고리즘 문제를 만드는지 모르겠으나 이 사람들 소수 찾기에 진심이다. 학교에서 수학 배울 때 빼고 단 한 번도 신경 쓰지 않았던 소수, PS 하다가 소수 문제가 하도 많이 나와, 한 번 정리해야겠다 싶어 정리한다. 소수 찾기 알고리즘 소수 찾는 방법은 여러 가지가 있다. 소수인지 판별이 필요한 수를 n이라고 하겠다. 1. 숫자 n 나누기 2부터 n-1까지 나누기 def isPrime(n): for i in range(2, n): if n % i == 0: return False return True n-1까지, n이 1과 자기 자신 외의 수로 나누어지는지 판단하는 알고리즘이다. 만약 나누어진다면 바로 false를 리턴한다. .. 2021. 12. 20. 이전 1 2 다음
