[컴퓨터과학과]알고리즘_출석수업과제물

목차

없음

본문내용

[문제 1]
주어진 그래프에서 오일러 경로가 존재하는지 여부를 작성한 다음, 해당 선분을 순서대로 그려서 한 눈으로 볼 수 있도록 표시하고 그 이유(규칙)를 설명하시오.
- 오일러 경로(Eulerian Trail)은 그래프에 존재하는 모든 간선을 정확히 한 번씩 방문하는 연속된 경로를 의미한다.
- 각 정점의 차수가 홀수인 정점이 0개 혹은 2개 이어야 한다.
- 홀수점이 2개일 경우에는 홀수점에서 시작해야 한다.

[문제 2]
용량이 20인 배낭이 있다. 물체의 이익과 무게가 다음과 같이 주어져 있고 물체를 쪼개 넣을 수 있다고 할 때 배낭에 넣기 위한 진행 과정과 최대 이익을 구하시오. 반드시 풀이과정을 정확히 작성하시오.
다음 쌍에는 앞에는 물체의 무게, 뒤에는 이익이 주어져 있으며, 물체 1부터 순서대로 나열되어 있음.
(7, 21), (5, 20), (4, 28), (6, 36), (2, 10)
- 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제
- 물체를 쪼개서 넣을 수 있음
- 물체의 무게는 적으면서도 이익이 가장 큰 물체부터 골라서 ‘욕심을 내어’ 최대한 넣는 과정을 반복

참고 자료

없음