방통대 컴퓨터과학과 1학기 기말 알고리즘 과제

소개

"방통대 컴퓨터과학과 1학기 기말 알고리즘 과제"에 대한 내용입니다.

목차

1. 제 1장 알고리즘 소개
2. 2장 분할정복 알고리즘
3. 3장 동적 프로그래밍 알고리즘
4. 4장 욕심쟁이 알고리즘
5. 5장 정렬 알고리즘
6. 제6장 탐색 알고리즘
7. 제 7장 근사 알고리즘
8. 제 8장 해 탐색 알고리즘

본문내용

제 1장 알고리즘 소개

1. 다음 중 교재 및 강의에서 다루어지지 않은 부류의 알고리즘은?(2018기말)(차례 참조)
① 기하 알고리즘
② 정렬 알고리즘
③ 유전 알고리즘
④ 욕심쟁이 알고리즘
정답 : 1번
해설 : 교재에서 다루고 있는 알고리즘의 종류에 대한 문제이다. 교재 5장에서 정렬 알고리즘, 교재 8장 3절에서 유전 알고리즘, 교재 4장에서 욕심쟁이 알고리즘을 다루고 있다.

2. 다음 그래프에 대해서 오일러 경로를 찾으려고 한다. 이때 출발점이 되어야 하는 정점은?(2018대체)(1장 4p)

① (a) ② (b)
③ (c) ④ (d)
정답 : 1번
해설 : 오일러 경로란 그래프의 모든 간선을 오직 한 번씩만 지나가는 경로를 찾는 문제로, 각 정점의 차수가 홀수인 점이 없거나 두개 두개이어야 하며, 홀수점이 두 개일 경우에는 홀수점에서 시작해야만 한다. 따라서 위의 그림에서 a가 홀수점이기 때문에 시작점이 되어야 한다.

3. 주어진 문제를 컴퓨터로 해결하려고 한다. 이를 위한 명령어들이 만족해야 할 조건과 거리가 먼 것은?(2018기말)(1장 6p)
①모든 명령은 컴퓨터에서 수행 가능해야 한다.
② 각 명령은 단순하고 명확해야 한다.
③ 한정된 수의 단계를 거친 후에는 반드시 종료해야 한다.
④외부 입력이 반드시 존재해서 하나 이상의 출력을 생성해야 한다.
정답 : 4번
해설 : 알고리즘의 조건에 대한 문제이다. 1번은 유효성, 2번은 명확성, 3번은 유한성에 대한 설명이다. 4번은 입출력에 대한 설명이지만 0개 이상의 외부입력과 하나 이상의 출력이 있어야 한다고 고쳐야 한다.

4. 이론적으로 문제 해결이라는 관점에서 반드시 만족하지 않아도 되는 알고리즘의 조건은?(2019기말)(1장 6-7p)
① 유효성 ② 명확성
③ 효율성 ④ 유한성
정답 : 3번
해설 : 알고리즘의 정의 부분에서 설명하고 있다. 문제 해결이라는 관점에서 주어진 문제가 컴퓨터로 해결 가능한 알고리즘이 존재하는 문제일 지라도 현실적으로는 상당히 긴 처리 시간을 요구하여 효율적으로 풀 수 없는 문제도 있다는 점이다.

참고자료

· 없음