Data Structure & Algorithm/Algorithm3 03. 그리디 알고리즘(Greedy Algorithm) Q. 주어진 거스름돈을 가장 적은 수의 동전으로 거슬러주는 알고리즘을 고안하라. (이후로 후보군 집합을 C, 해결책 집합을 S라고 명명함.) A. 그리디 알고리즘에서 필요한 세 가지 함수 1. Select() - 조건에 맞는 원소를 선택 2. Feasible() - S 집합에 들어갈 수 있는지 판단 3. Solution() - 문제가 해결되었는지 확인 * 최적화 문제 대상 함수 $f$를 제약 조건(Condition or Constraint) C에 맞게 최적화(대체로 최대화 또는 최소화) 하는 것. 가능(feasible)한 해결책 : C를 만족하는 아무 결과 최적의 결과 : 대상 함수를 최적화하는 해결책 * 그리디 알고리즘(Greedy Algorithm) 현재 갖고 있는 정보만을 가지고 결정을 내리는 것... 2023. 10. 23. 02. 알고리즘 분석 알고리즘의 효율성 분석을 위한 만능 공식은 없음. 대신, 몇몇 기본적인 방법들이 존재함. 알고리즘 분석은 대체로 안에서 바깥쪽으로 진행됨. 1. 순차적 규칙(Sequencing Rule) P1과 P2가 알고리즘의 두 부분이라고 한다면, 각각은 하나의 명령어이거나 복잡한 서브-알고리즘일 것임. 추가로, t1과 t2를 P1과 P2의 실행에 걸리는 시간이라고 했을 때 순차적 규칙에 의하면, P1과 P2의 실행에 거리는 시간은 단순히 t1+t2임. 최대 규칙(Maximum Rule)에 따르면, 이 시간은 θ( max{t1, t2} )임. 2. for 반복문 for i ← 1 to m, do P(i); 이 반복은 큰 알고리즘의 일부이고, 사이즈 n짜리 인스턴스에서 동작함. 2-1. P(i)에 걸리는 시간이 i와 .. 2023. 10. 18. 01. 알고리즘이란 * 문제와 해결방법 2 + 3 = ? 3 + 5 = ? 5 + 2 = ? ... 위와 같은 상황일 때, 알고리즘의 측면에서 문제는 한 개임. 일반적으로 말하는 문제를 여기선 인스턴스라고 함. 즉, 위에는 인스턴스가 3개인 것임. 해당 과목에서 "문제(Problem)"와 "인스턴스(Instance)"는 구분되어 사용됨에 유의할 것. - 한 문제는 많은(대체로 무수히 많은) 인스턴스를 가짐. 예를 들어, 두 양의 정수가 주어졌을때, 최대공약수(GCD, Greatest Common Divisor) 구하기라는 "문제"가 있을 때, 461,952 와 116,298 의 최대공약수를 구하기 (정답 = 18) 와 같은 "인스턴스"가 얼마든지 생성 될 수 있음. * 일반화 문제 P ) f : D -> R 인 f를 구해라.. 2023. 10. 11. 이전 1 다음
