SYDev

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. Dynamic Programmingdivide-and-conquer(분할정복식, 재귀): top-down 해결법Dynamic Programming: bottom-up 해결법작은 문제 해결 먼저 -> 결과를 큰 문제의 해결로 확산재귀 관계식(recursive property) 정립작은 사례를 먼저 해결하는 상향식 방법으로 진행 1. 이항계수 구하기문제: 이항계수를 계산입력: 음수가 아닌 정수 n과 k, 여기서 k 출력: bin, nCk- 시간복잡도(분할정복식 접근방법)귀납증명에 따라, nCk를 구하기 위해서 알고리즘이 계산하는 항(term)의 개수는 2*nCk - 1 - 동적계획법 알고리즘 설계전략recursive property 정립n..

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. 분할정복(Divide-and-Conquer)식 설계 전략분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눔정복(Conquer): 나눈 작은 문제를 각각 해결통합(Combine): (필요하다면) 해결된 해답을 모음-> 이런 문제 해결 방법을 하향식(top-down) 접근방법이라 함 1. 이분검색(binary search): 재귀식 방식설계 전략x가 배열의 중간에 위치한 항목과 같으면 stop, 그렇지 않으면Divide: 배열을 반으로 나누어 x와 중앙값을 비교하여 배열 반쪽을 선택Conquer: 선택된 반쪽 배열에서 x를 찾음def bs(data, item, low, high): # item 존재 X i..

경희대학교 한치근 교수님의 알고리즘 수업을 기반으로 정리한 글입니다. 1. 알고리즘문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(prodcedure)input -> output: 일련의 계산 절차- 알고리즘과 Method의 차이Algorithm: 유한 시간 내에 종료Method: 유한 시간 내에 종료하는지 모름 문제의 표기 방법문제: 답을 찾고자 던지는 질문Parameter: 문제에서 특정 값이 주어지지 않은 변수 - 매개변수Instance(입력): 파라미터에 특정 값을 지정한 것Solution(출력): 주어진 사례에 관한 질문에 대한 답 수학적 귀납법(mathematical induction)귀납 출발점(bas..