2024년 5급 공채 기술 2차 알고리즘
문제 3개 · 50점. 참고 답안·채점 기준은 앱에서 볼 수 있습니다.
제1문 (10점)
아래 C언어 코드에 대한 물음에 답하시오. (총 10점)
#include <stdio.h>
int main() {
int number = 11;
int answer = 0;
while(number > 0) {
if(number % 2 == 1)
answer++;
number /= 2;
}
printf("answer : %d\n", answer);
return 0;
}
int main() {
int number = 11;
int answer = 0;
while(number > 0) {
if(number % 2 == 1)
answer++;
number /= 2;
}
printf("answer : %d\n", answer);
return 0;
}
- (1) 수행결과를 작성하시오. (5점)
- (2) 위의 코드를 다음과 같이 수정했을 때, 수행결과를 작성하시오. (5점)#include <stdio.h>
int main() {
int number = 11;
int answer = 0;
while(number > 0) {
if(number % 3 == 1)
answer++;
number /= 3;
}
printf("answer : %d\n", answer);
return 0;
}
제2문 (20점)
다음 물음에 답하시오. 아래 그림들에서 알파벳은 정점의 이름, 간선에 제시된 수는 간선의 길이, 정점에 저장될 값은 시작 정점 S로부터의 최단 거리이다. 무한대(∞)값은 초기값으로 주어진 것이다. (총 20점)
- (1) 다익스트라 알고리즘(Dijkstra’s algorithm)을 이용하여 다음 그래프에서 시작 정점 S로부터 각 정점까지의 최단 거리를 구하는 과정을 설명하시오. 정점에 저장된 값이 변화하는 과정과 각 변화를 위해 사용된 간선을 명확히 보이시오. (10점)
[그림] - (2) 다익스트라 알고리즘의 시간복잡도를 분석하고, 간선의 길이값의 조건에 따라 다익스트라 알고리즘을 적용할 수 없는 경우를 설명하시오. (6점)
- (3) 벨만 포드 알고리즘(Bellman-Ford algorithm)을 이용하여 다음 그래프에서 시작 정점 S로부터 각 정점까지의 최단 거리를 구하는 과정을 설명하시오. 정점에 저장된 값이 변화하는 과정과 각 변화를 위해 사용된 간선을 명확히 보이시오. (4점)
[그림]
제3문 (20점)
다음과 같은 조건의 배낭 문제(knapsack problem)가 주어졌다. 배낭 하나와 A, B, C, D, E 다섯 개의 물건이 주어져 있고, 여러분은 이 배낭의 용량 이내에서 최대의 이익을 얻을 수 있도록 배낭에 물건을 담아야 한다. 즉, 담은 물건들의 무게의 합은 배낭의 용량에 비해 작거나 같아야 한다. 다음 물음에 답하시오. (총 20점)
배낭의 용량 11kg
| ||||||||||||||||||||||||
| 물건의 정보 | ||||||||||||||||||||||||
| 물건 | A | B | C | D | E | |||||||||||||||||||
| 무게 | 5kg | 3kg | 2kg | 4kg | 6kg | |||||||||||||||||||
| 이익 | 200원 | 300원 | 400원 | 500원 | 600원 | |||||||||||||||||||
- (1) 배낭에 넣을 수 있는 물건을 쪼갤 수 있다고 가정할 때 최대 이익은 얼마인지 계산하는 과정을 보이시오. 예를 들어, 물건 A를 2kg만 배낭에 넣었을 때 배낭에는 (200원/5kg)*2kg＝80원만큼 이익이 추가된다. (7점)
- (2) 배낭에 넣을 수 있는 물건을 쪼갤 수 없다고 가정할 때 최대 이익은 얼마인지 계산하시오. 즉, 어떤 물건은 배낭에 들어가거나 배낭에 들어가지 않거나 둘 중 하나만 가능하다. 반드시 배낭의 용량과 물건의 개수의 곱에 비례하는 시간에 동작하는 동적계획법(dynamic programming)을 이용하여 풀이하는 과정을 보이시오. (13점)