센로그

◆ 동적 계획법 (Dynamic Programming)입력 크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 문제를 해결해나가는 알고리즘. 다음 두 가지 조건을 만족해야 동적 계획법으로 쓸 수 있다.작은 문제들의 해를 활용해 큰 문제를 풀 수 있어야 함.최적의 원칙 : 전체가 최적이면 부분에 대해서도 최적이어야 함. ◆ 분할 정복법 vs 동적 계획법ㆍ분할 정복법- 하향식(top-down) 해결법- 큰 문제를 해결하는 데에만 관심이 있음 ㆍ동적 계획법- 상향식(bottom-up) 해결법- 작은 문제의 해결을 활용해 큰 문제를 해결 ◆ 이항 계수(binomial coefficient) 구하기분할 정복법 vs 동적 계획법으로 이항 계수를 구하는 법을 알아볼 것이다.  ◆ 이항 ..

◆ 분할 정복식 설계 전략큰 문제를 작은 문제로 나누어 해결한 후, 해답을 모아 큰 문제의 해를 만드는 방법문제의 성질과 전체 형태가 작은 문제에서도 똑같이 유지 됨  분할(Divide): 해결하기 쉽도록 문제를 여러 개의 작은 부분으로 나눈다.정복(Conquer): 나눈 작은 문제를 각각 해결한다.  통합(Combine): (필요하다면) 해결된 해답을 모은다. 이러한 문제 해결 방법을 하향식(top-down)  접근 방법이라고 한다. ◆ 바닥 함수와 천장 함수 바닥 함수: 실수 x에 대해, x보다 작거나 같은 정수 중 가장 큰 정수 천장 함수: 실수 x에 대해, x보다 크거나 같은 정수 중 가장 작은 정수    ◆ 이분 검색 (binary search)배열을 반으로 나눠서, 찾아야할 x와 locatio..

◆ 알고리즘의 정의 문제를 해결할 수 있는 1) 잘 정의된, 2) 유한시간 내에 종료되는, 3) 계산적인 절차 1) well defined: 잘 정의 되었다는 것은 a가 설명했으면 b가 그걸 정확하게(다르게 해석되지 않게) 이해할 수 있는 것. 2) finite : 언젠가는 끝나는 게 보장되어야 함 3) computational: 입력을 받아서 출력으로 전환시켜주는 일련의 계산 절차. 알고리즘은 프로그램의 엔진에 해당하는 중요한 절차이다!! ◆ Algorithm vs Method Algorithm은 유한 시간 내에 종료됨 Method는 유한 시간 내에 종료되는지 모름 ◆ 문제의 표기 방법 문제 답을 찾고자 던지는 질문 parameter 매개변수 문제에서 특정 값이 주어지지 않은 변수 instance 문제..