Page 214 고등학교 프로그래밍 교과서

② 알고리즘 설계

총 운송비를 최소로 하려면 제품 1개당 운송비가 적은 제품을 우선적으로 수출하
는 전략을 세워야 한다. 그러므로 먼저 운송비를 기준으로 오름차순으로 자료를 정

렬하고 정렬된 자료의 순서에 따라 각 국가에 수출할 수량을 결정하는 과정이 필요
하다. 운송비를 정렬하는 부분은 사용자 정의 함수로 별도 작성하면 프로그램의 구

조가 간결해진다.
두 곳의 공장에서 두 지역의 국가로 수출할 수 있으므로 총 4개의 항목이 존재하
며, 이 값은 배열 cost에 들어 있다. 그러므로 배열 cost를 탐색하고 최솟값을 찾아

서 이때의 공장 번호(factory)와 국가 번호(nation)를 배열 work에 저장한다. 변수
k를 0~3까지 4번 반복하면 최종적으로 work[4][3]에는 운송비가 적은 순서대로 자

료가 저장된다.

알고리즘 실행 결과 [표 Ⅲ- 1] 배열 work[4][3]의 저장 자료
배열 work에는 운송비가 적은 순서
구분 0 1 2
대로 자료가 저장된다. 예를 들어,
첫 번째 항목의 경우 인천(1)에서 B k(순번) 운송비 공장 국가
국가(1)로 운송하기 위한 비용이 4
0 4 1 1 0은 부산, 1은 인천
임을 의미한다.
1 5 1 0
0은 A 국가, 1은 B 국가
2 11 0 0
3 16 0 1

다음은 운송비를 정렬하기 위한 알고리즘을 C 언어 의사 코드로 작성한 것이다.

[운송비 정렬 알고리즘]

for k ← 0 to 3
min ← 999;
변수 i는 공장 번호 저장
for i ← 0 to 1
for j ← 0 to 1 변수 j는 국가 번호 저장
if ((cost[i][j] > 0) AND (cost[i][j] < min))
min ← cost[i][j];
cost 배열에서
factory ← i;
최솟값 찾기
nation ← j;
end if
loop
loop
work[ ][ ] ← min, factory, nation;
최소 비용, 공장 번호, 국가 번호 저장
cost[factory][nation] ← 0;
loop

212 Ⅲ. 프로그래밍 설계와 구현

(책)2015프로그래밍-교과서3차심의본 본문.indb 212 2017-09-05 오후 4:16:54