개발스토리

최소 비용 신장 트리 - n(> 1) 개의 도시들을 최소한의 비용으로 연결하는 철도망을 새로 구축하려고 한다. - 모든 도시들을 서로 연결하기 위해 도시간 철도를 최소한 (n - 1)개 깔아야 한다. - 각 철도는 두 도시를 연결한다. - 이 철도망들 중에서 철도 노선들의 총 길이가 최소가 되도록 철도망을 구축해야 한다. ■ 신장트리: 연결된, 무방향 그래프안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분 그래프 ■ 신장트리는 순환을 포함하지 않으며 그래프 안에 있는 모든 정점들을 연결시킨다. ■ 신장트리의 가중치: 모든 간선들의 가중치들의 합 ■ 최소 비용 신장 트리: 최소 가중치를 가진 신장트리 예 : 최소 길이 철도망 억지 기법 알고리즘 ■ 모든 신장 트리를 찾은 후에 그 중에서 최소 ..

동전 던지기 - 3개의 동전들을 던질 때, 나올 수 있는 값들의 모든 가능한 조합들을 출력하는 문제 - 가정) 앞면 : 0, 뒷 면 : 1 - 알고리즘) for (c1 = 0; c1

되추적(Backtracking) ● 완전 탐색을 개선한 기법 ● 후보 해들을 단계적으로 만들어 가는 과정에서 후보 해들을 평가 ● 만약 한 후보 해가 최종 해가 될 수 없다고 판단되면 탐색을 멈추고 다른 후보 해를 탐색 ● 최적화 문제와 결정 문제 해결 가능 하산 길 선택 ● 하산 길에 갈림길에 안내 표지판이 없다면?? 1. 갈림길에서 한 길을 선택한 후 그 길을 따라 계속해서 간다. 2. 길이 끊어지거나 절벽에 도달하면 갈림길로 되돌아온다. 3. 갈림길에서 다른 길을 선택해서 간다. 상태공간 트리란 무엇일까? ● 특정 알고리즘의 진행 과정을 나타낸 트리 - 노드: 한 해의 구성요소들에 대한 특정 선택 - 후보 해: 루트 노드에서 종단 노드까지의 경로 - 후보 해 중에 해가 있음 - 해가 될 가능성이 전..

탐욕 기법 소개 ● 매 번 선택할 때 마다 그 순간에 가장 좋은 선택을 함으로써 최종적인 해에 도달한다. ● 최적인 해들을 모아서 최종 해를 만들었다고 해서, 그 해가 궁극적으로 최적이라는 보장이 없다. ● 따라서 탐욕 기법은 항상 최적의 해를 만들어 내는 지를 반드시 검증해야 한다. 선택 기준 ● 선택이 실현 가능해야 한다. ● 모든 선택들 중에서 최적이라고 여겨지는 선택을 해야 한다. ● 한 번 선택하면 나중에 되돌릴 수 없다. 설계 전략 ● 비어 있는 해 모음으로 시작한다. ● 탐욕적인 기준에 따라 해 모음에 추가할 다음 해를 선택한다. ● 새 해 모음이 실현 가능한지를 확인한다. 실현 가능하다면 새 해 모음을 확정하고 아니면 선택한 해를 버린다. ● 새 해 모음이 최종 해라면 종료한다. 아니면 2..