알고리즘

최적화 문제를 해결하기 위한 알고리즘다단계 해결 알고리즘 부분문제를 모두 해결한 후 큰 크기의 부분문제들을 해결 각 단계의 부분문제의 답을 기반으로 전체문제의 답을 구하는 방법

4. 그리디 알고리즘 부분 배낭 문제 0-1 배낭 문제 집합 커버 문제 (7장) np문제 전체 집합 U 부분집합 F1, F2, ... Fn 어떤 부분집합을 합쳐야 최소한의 집합을 사용해 전체집합을 표현할 수 있을까?... > ex) 신도시 계획 학교배치 어떤 위치에 학

알고리즘_동적 계획 프로그래밍_편집 거리 알고리즘

w무개, v가치를 가지고 있는 n개 물건이 존재할 경우용량이 C인 배낭을 가지고 어떤 물건을 담아야 배낭에 담긴 물건의 가치를 최대화 할 수 있는가?절대 배낭의 용량을 넘겨서 물건을 담을 수 없다정보물건의 무게 wi물건의 가치 vi배낭의 용량 C

ㅁ

1.6 TSP(여행자 문제)해밀턴 경로 K상수보다 짧은 거리로 여행자가 모든 도시를 돌아보고올 수 있는가?

입력 n개의 점을 K개의 그룹으로 나눌때 중심점을 K개 선택하는 문제단, 가장 큰 반경을 가진 그룹의 지름이 최소가 되도록 해야함임의의 점 하나를 선택한다위에서 선택된 모든 점과 가장 먼 점을 선택 K번 반복점의 갯수 k중심점의 갯수 n시간 복잡도 = O(kn)어떤 점

ㄴㅁㅇ

분기한정

최적화 문제를 해결한다.가능한 해중에서 가장 좋은 해를 찾는 문제현재 상태에서 욕심내서 선택하는 알고리즘(근시안적)한번 선택된것은 결코 버려지지 않는다.근사알리즘의 형태로 탐욕 알고리즘을 많이 사용할 수 있다.동전 거스름돈현재 거스름돈에서 가장 큰 액면의 동전을 먼저

주어진 가중치 그래프에서 사이클이 없이 모든 점을 연결시킨 트리중 선분의 가중치의 합이 최소인 트리(a) 기중치 그래프(b) 최소 신장트리 <-(c) 신장트리(d) 신장트리그래프에 n개의 점이 있을때 선분의 갯수는 (n-1)이 된다트리에 선분을 하나 추가하면 반드

ㅁ