반응형 전체 글229 Greedy Algorithm Python [ Greedy Algorithm ] 그리디 알고리즘(Greedy Algorithm)은 탐욕 알고리즘이라고 한다. 탐욕이라는 말이 붙기 때문에 느낌이 좀 쌔하긴 하다. 쌔한 느낌 그대로 이 알고리즘은 지금 당장 좋은 것만 골라서 사용하는 알고리즘이다. 0부터 시작하는 A라는 그래프가 있다. 이 중 가지의 합이 가장 큰 경우를 찾아야 할 때 Optimal 처럼 0-3-100을 골라내야 한다. 하지만 Greedy는 0-10-8 처럼 당장 좋은 것만 고른다. Greedy는 0에서 시작해서 3과 10의 선택 순간에 10을 선택하고 7과 8의 선택 순간에 8을 선택함으로써 탐욕을 채운다. 항상 최적의 결과를 만들지 않기 때문에 그리디 알고리즘으로 문제를 풀었어도 최적의 결과인지를 확인해야 한다. 최적의 결과를 만.. 2021. 4. 11. 빅오(Big O) 시간복잡도 [ Big O, 시간복잡도 ] 빅오(Big O) 시간복잡도는 위 그림하나도 전부 설명이 가능하다. 빅오는 처리시간이 아니라 시간의 증가율을 나타낸다고 보면 된다. X는 데이터의 갯수, Y는 처리의 갯수이다. 순서를 보면 $O(2^n)$ > $O(n^2)$ > $O(n log n)$ > $O(N)$ > $O(log n)$ > $O(1)$ 이다. 참고로 빅오 표기법에서 상수는 연산에 고정된 값이라서 연산에 크게 작용하지 않는다고 본다. 그래서 상수 10을 빅오랑 곱해도 값은 빅오 그대로 라는 것을 알아야 한다. 예를들어 $10 \times O(1)$ = $O(1)$ 이다. 시간 증가량에 대한 표기법은 점근적 상한(Upper Bound)인 Big-O 외에 점근적 일치(Tight Bound)인 Big-Theta.. 2021. 4. 10. Dynamic Programing Algoritm [ 다이나믹 프로그래밍 ] 다이나믹 프로그래밍(Dynamic Programing)은 메모리를 적절하게 사용하는 방법으로 알고리즘의 수행 시간을 향상시키는 것을 목적으로 둔다. 메모리는 작은 문제라고 불리는 이미 계산된 결과를 저장하는 데 사용된다. 다이나믹 프로그래밍을 구현하는 방법은 탑다운 방식과 바텀업 방식 이렇게 두 가지로 알려져 있다. 결과적으로는 이렇게 작은 문제를 저장해서 이미 계산된 내역을 메모리에서 빠르게 찾아서 문제를 해결한다는 것이다. 이런 문제를 해결할 수 있는 조건이 두가지가 있는데 하나는 최적 구조이고 다른 하나는 중복 구조이다. 최적 구조는 큰 문제를 작은 문제로 쪼개서 처리할 수 있는 구조를 말하고 중복 구조는 같은 문제가 반복적으로 나오는 구조로 볼 수 있다. 대표적인 중복문.. 2021. 4. 10. 이전 1 ··· 33 34 35 36 37 38 39 ··· 77 다음 반응형
