study/알고리즘
-
알고리즘 - 최대공약수(GCD)와 최소공배수(LCM)study/알고리즘 2021. 2. 4. 23:06
최대공약수(GCD) 공통적인 약수 중 최댓값, 최대공약수가 1이면 서로소이다. def gcd(a, b): ret = 0 for i in range(min(a, b)):# 1부터 체크 if a % i == 0 and b % i == 0: ret = i return ret; a의 공약수는 a보다 작고, b의 공약수는 b보다 작으므로 최소값 까지만 구하면 되기 때문에 min(a, b)까지 검사 def gcd(a, b): ret = 0 for i in range(min(a, b), 0, -1):# min(a, b)부터 체크 if a % i == 0 and b % i == 0: return i 역방향으로 진행하면 O(1)만에 끝나는 경우가 있다. 유클리드 호제법 GCD(A, B) = GCD(B, A % B) de..
-
알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)study/알고리즘 2020. 2. 10. 17:03
알고리즘 풀이를 하다보면 많은 문제가 다이나믹 프로그래밍(DP)를 이용해 풀이가 가능합니다. 그렇기 때문에 알고리즘을 공부하기 위해서는 꼭 알아가야 하는 파트입니다. 다이나믹 프로그래밍은 동적 계획법으로도 불리는데, 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어지면 각 단계의 부분 문제에 대한 답을 기반으로 하여 전체 문제의 답을 구하는 방법 입니다. 정리하자면 큰 문제를 작은 문제들로 쪼개어 푸는 알고리즘이라 생각하면 됩니다. TMI - 다이나믹 프로그래밍의 이름은 알고리즘의 고안자인 리차드 벨만이 Dynamic이란 말이 멋있어서 붙였다고 합니다. 문제를 다이나믹 프로그래밍을 사용하여 풀기 위해서는 2가지 속성을 만족해야합니다. Overlapping Subproblem (부분 문제 반복) Opt..
-
알고리즘 - 배낭문제 (Knapsack Problem)study/알고리즘 2020. 2. 9. 17:32
배낭문제는 조합 최적화의 유명한 문제입니다. 한 가방에 넣을 수 있는 무게의 최대 값이 정해져 있을 때, 일정한 가치와 무게가 있는 물건들을 가치의 합이 최대가 되도록 가방에 넣는 방법을 찾는 문제입니다. 분할 가능 문제 (Fractional Knapsack Problem) 짐을 쪼갤 수 있는 경우 그리디 알고리즘(greedy method)으로 다항 시간 안에 풀이 가능하다. 0-1 배낭 문제 (0-1 Knapsack Problem) 짐을 쪼갤 수 없는 경우 동적 계획법(dp)등을 사용하여 의사 다항 시간 안에 풀이 가능하다. NP-완전이기 때문에 FPTAS만 존재한다. reference - https://ko.wikipedia.org/wiki/배낭_문제