Computer Science59 [알고리즘] Dynamic 프로그래밍과 예제들 우리가 여태 배워온 것들은 아래와 같다. - D&C 기법 - Backtracking 기법 : 어떤 결정의 연속을 통해 문제의 답을 점차적으로 만들어가는 것. Recursion을 돌린다. -> 문제에 대한 일반화가 필요함. // 이번시간에 배울 것 - Recursion은 항상 옳은가? - 쓸데 없이 많은 Recursive call을 줄여보자. - 점화식을 이용한 효율적 구현 >> Dynamic program (동적 계획법) Dynamic Programming을 사용한 알고리즘 - Fibonacci number 계산 - Longest Increasing Subsequence(LIS) - Subset Sum ---------------------------------------------------------.. 2020. 5. 13. [알고리즘] D&C 기법의 예시와 좋은 pivot이란? (지난주) D&C기법? 같은 문제의 더 작은 instance로 recursion 하는 방법. D&C 알고리즘의 시간 복잡도 분석 1. 점화식을 찾아라 ( 재귀하는 부분 & 나머지 부분 ) -> T(n) = r*T(n/c)+O(f(n)) 형태 2. 점화식을 풀어라 ( Recursion tree , Master Theorem 등) Mater Theorem : 점화식이 T(n) = r*T(n/c) + O(f(n)) 형태를 만족할 때만 적용 가능, f(n)과 n^(log c r)을 비교 - f(n) = Ω(n^(logc r+ε) >> T(n) = O(f(n)) - f(n) = Θ(n^(log c r) >> T(n) = O(f(n) * log n) - f(n) = O(n^(log c r-ε) >> T(n) = O.. 2020. 5. 11. [알고리즘] D&C 기법, Recursion tree와 Master Theorem //저번 시간 Recursion : simple and delegate! 자기 자신으로 reduce 하는 전략 Reduction >> 다른 문제의 알고리즘을 활용한다. Recursive algorithms : Correctness : induction으로 증명한다. Time Complexity Analysis : 점화식을 구한다. ---------------------------------------------------------------------------- //이번 시간 1. Divide and Conquer //패턴(결국엔 recursion) 알고리즘 설계, 문제 해결 기법 n이 주어지면 -1씩 줄어드는 것이 아닌 더 덩어리가 크게 나누어진다. 2. D&C (divide and conquer).. 2020. 5. 8. [알고리듬] 시간복잡도 분석(피보나치, Peasant, Hanoi, Quick sort, Merge sort) 지난주는 시간복잡도, 알고리즘을 수행하는데 걸리는 시간(running time) 어떻게 측정하는가? 알고리즘 자체가 추상적인 상태이므로, 시간 복잡도를 이용하자. 시간 복잡도 분석 = 연산의 개수 세기 >> (시간복잡도 = n에 대한 함수) n에 대한 개수를 정확하게 세는 것은 어렵다. 따라서 최악의 경우를 따짐 -> 최대 개수에 대한 상한을 분석 ◇예제. 피보나치 수열◇ : O(mn)만큼의 한 자릿수 곱셈 (안쪽 for문) >> ppt 내용 인덱스 범위 지정이 잘못됐음. if문을 써서 i 안쪽 for 문 : 상수 개+1번의 상한을 갖게 됨. // O(k+1)를 넘지 않는 빅오를 갖게 된다. >> 안쪽 for문에서 hold += hold*X[i][j]의 값이 O(mn)의 값을 가진다. 그 이유는 i와 j.. 2020. 5. 8. [알고리즘] 시간복잡도란? 빅오표기법을 사용하는 이유? 1. 시간 복잡도 2. 빅오 표기법 3. 정렬 알고리즘 시간 복잡도(Time Complexity) 시간 복잡도는 왜 필요한가? 알고리즘 中 최선의 방법을 찾기 위하여. (학교 수업을 바탕으로 생각한 그적 피셜) 우리는 알고리즘의 효율성 즉, 실행시간은 컴퓨터가 해당 알고리즘을 실행하는 속도에 의존적이다. 시간 복잡도를 이용해 최선의 방법을 찾음으로써 알고리즘의 효율성을 따질 수 있다. 알고리즘 실행속도는 코드, 언어, 컴파일러, 컴퓨터의 스펙 등 다양한 요인에 따라서 수행 시간이 달라진다. 그럼 어떻게 알고리즘 실행 시간을 측정할 수 있을까? 매 시간 알고리즘의 정확한 실행 시간을 측정하기 어렵기 때문에 우리는 알고리즘의 환경적 요인들을 날려버린다. 알고리즘의 환경적 요인을 날려버린 상황에서 우리는 알고.. 2020. 5. 8. 이전 1 ··· 7 8 9 10 다음
