백준
-
[백준 1629] 곱셈 python (수학)study/PS 2021. 2. 4. 22:49
자연수 A를 B번 곱한수를 만들고 이를 C로 나눈값을 출력하면 된다. A ** B % C 하면 될 것 같지만 시간 복잡도 O(B)이기 때문에 시간 초과한다... 매우 크게.. 이때 이진수를 활용하면 빠르게 풀이 할 수 있다. 아이디어 : 거듭제곱은 거듭제곱 간의 곱으로 표현 가능하다. A^13이라는 값을 이진수로 표현하면 A^1101이 되는데 1101 / 2 => 110 ... 1 110 / 2 => 11 ... 0 11 / 2 => 1 ... 1 1 / 2 => 0 ... 1 이렇게 2로 나누면 나머지가 원래 가지고 있던 이진수가 됨을 알 수 있다. A^13 = A * A^4 * A^8 조건문 + N진수 변환 방법으로 해결 가능하다는 것을 알 수 있다. def answer(a, b): ret = 1 w..
-
알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)study/알고리즘 2020. 2. 10. 17:03
알고리즘 풀이를 하다보면 많은 문제가 다이나믹 프로그래밍(DP)를 이용해 풀이가 가능합니다. 그렇기 때문에 알고리즘을 공부하기 위해서는 꼭 알아가야 하는 파트입니다. 다이나믹 프로그래밍은 동적 계획법으로도 불리는데, 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어지면 각 단계의 부분 문제에 대한 답을 기반으로 하여 전체 문제의 답을 구하는 방법 입니다. 정리하자면 큰 문제를 작은 문제들로 쪼개어 푸는 알고리즘이라 생각하면 됩니다. TMI - 다이나믹 프로그래밍의 이름은 알고리즘의 고안자인 리차드 벨만이 Dynamic이란 말이 멋있어서 붙였다고 합니다. 문제를 다이나믹 프로그래밍을 사용하여 풀기 위해서는 2가지 속성을 만족해야합니다. Overlapping Subproblem (부분 문제 반복) Opt..