[ 알고리즘연습문제 ] [ 문제 1] 국립공원방문자다음은 1년동안국립공원방문자에대해일별평균방문자수와, 최대방문자수, 최소방문자수를찾는알고리즘이다. - 1년동안의일별방문자수는 V(365) 로주어진다. - 알고리즘에사용되는변수는다음과같다. S : 합계 MA : 최대값 MI

Size: px

Start display at page:

Download "[ 알고리즘연습문제 ] [ 문제 1] 국립공원방문자다음은 1년동안국립공원방문자에대해일별평균방문자수와, 최대방문자수, 최소방문자수를찾는알고리즘이다. - 1년동안의일별방문자수는 V(365) 로주어진다. - 알고리즘에사용되는변수는다음과같다. S : 합계 MA : 최대값 MI"

창석 국
5 years ago
Views:

1 [ 알고리즘연습문제 ] [ 문제 1] 국립공원방문자다음은 1년동안국립공원방문자에대해일별평균방문자수와, 최대방문자수, 최소방문자수를찾는알고리즘이다. - 1년동안의일별방문자수는 V(365) 로주어진다. - 알고리즘에사용되는변수는다음과같다. S : 합계 MA : 최대값 MI : 최소값 J : 첨자 M : 평균 - 1 -

2 답항보기 S 7 J + S 8 J < 20 9 J < J <= J > J > J >= MA 15 MA * MI 16 MA - MI 17 MA = 0 18 MA = 1 19 MA = MI 20 MI = 0 21 MI = 1 22 MI 23 S * S * V(J) 25 S S + MA 27 S + MA + MI 28 S + MI 29 S + V(J) 30 S + V(K) 31 S S / S / V(J) 34 V(0) 35 V(1) 36 V(128) 37 V(365) 38 V(J + 1) 39 V(J) < MA 40 V(J) <= MI 41 V(J) = MA 42 V(J) > MA 43 V(J) >= MI 44 V(J) 45 V(K + J) 46 V(K - J) 47 V(K) 48 V(MA) 49 V(MI + J) 50 V(MI) - 2 -

3 [ 문제 2] 성적처리다음은전교생의영어점수가평균이상인학생들의수학점수평균을출력하는알고리즘이다. - 전교생의수는 200명이다. - I번째학생의영어점수는 ENG(I) 에수학점수는 MAT(I) 로주어진다. - 알고리즘에사용되는변수는다음과같다. S : 합계 J : 첨자 ME : 평균영어점수 K : 첨자 MM : 평균수학점수 - 3 -

4 답항보기 ENG(J) 7 ENG(J) <= ME 8 ENG(J) > ME 9 ENG(J) >= ME 10 ENG(K) 11 ENG(K) / S ENG(K) <= ME 13 J J + K 15 J < J < N 17 J <= J = J * 2 19 J = J J = J J > J > N 23 K K = K K = S * 2 26 MAT(J) + ENG(J) 27 MAT(J) 28 MAT(K) 29 MM = K / S 30 MM = S * MM = S / MM = S / J 33 MM = S / K 34 S * N 35 S + ENG(J) 36 S / S / S / N 39 S = S = 0 41 S = 1 42 S = 2 43 S = ENG(J) + K 44 S = J * 3 45 S = K + S / 2 46 S = ME / S = N S = S + ENG(J) 49 S = S + MAT(J) 50 S MOD

5 [ 문제 3] 성적검색다음은학번을입력받아 N명의학생중에서해당학번을갖는학생의이름과석차를출력하는알고리즘이다. - N명의학생에대해 I 번째학생의학번은 ID(I), 해당학생의이름은 NA(I) 로, 석차를내기위한점수는 SC(I) 로제공된다. - 입력받은학번의학생이존재하지않는경우 학생정보없음 을출력한다. - 석차를구함에있어동점자에대해서는동일석차를갖도록한다. 예를들어 1등이 1명, 2등이 2명일경우, 3등은없고다음으로높은점수를갖는학생은 4등이되도록처리한다. - 알고리즘에사용되는변수는다음과같다. R : 학번 J : 첨자 K : 첨자 - 5 -

6 답항보기 J 7 ID(1) 8 ID(J) 9 ID(K) 10 ID(N) 11 ID(SC(J)) 12 J 13 J * 2 14 J = J = 0 16 J = 1 17 J = 2 18 J = J * 2 19 J = J J = J + N 21 J = J J = J / 2 23 J = SC(0) 24 K K + J + R 26 K K / 2 28 K < N 29 K <= N 30 K > J 31 K > N 32 K >= N 33 N 34 N * 2 35 N * N 36 N + J 37 N / 2 38 R + J 39 R / J * 2 40 R = ID(K) 41 R = J 42 R = K 43 R = R R = SC(K) 45 SC(J + 1) 46 SC(J) 47 SC(J) / 4 48 SC(K) 49 SC(K) + ID(J) 50 SC(N) - 6 -

7 [ 문제 4] 주차요금계산다음은공영주차장에서 N 대의차량에대해주차요금의총합을구하는알고리즘이다. - 주차시간은최대 24시간을넘지않는다. - I번째차량의주차시간은분단위로배열 T(I) 로제공된다. - 주차시간이 15분미만인차량에대해서는요금이면제된다. - 최초 30분까지는기본요금 1,000원이징수된다. - 30분초과부터 10분당 400원의요금이징수된다. - 일일최대주차요금은 40,000원이다. 즉, 계산된주차요금이 40,000원이넘을경우 40,000원만징수된다. - 알고리즘에사용되는변수는다음과같다. S : 주차요금합계 J : 첨자 TI : 임시변수 F : 주차요금 - 7 -

8 답항보기 * J (F * 400) > J / J F * J 16 F - S 17 F / J 18 F = 0 19 F = J 20 F = 400 * J 21 F = 400 * J F = F = N 24 J <= N 25 J = J = 0 27 J = 1 28 J = J = J J > (N * F) 31 J > J > N 33 J >= N 34 NULL 35 S + F 36 S + F - J 37 S - F 38 S / 2 39 S / F 40 S = S + T(J) 41 S = S / F 42 T(J) = 0 43 T(J) > T(N) 45 TI < TI <> TI = 400 * J 48 TI = TI TI = TI TI >=

9 [ 문제5] 요일별교통위반건수계산다음은 2005년도의 N건의교통위반자료를바탕으로일요일의위반건수를출력하는알고리즘이다. - I번째위반이발생한날짜는월, 일에대해각각 M(I), D(I) 로제공된다 년 1월 1일은토요일이다. - 1월부터 12월까지각달의날짜수는배열 A(12) 에제공된다. 즉, A(1) = 31, A(2) = 28 A(12) = 31과같이저장되어있다. - 알고리즘에사용되는변수는다음과같다. C : 교통위반건수 J : 첨자 NS : 요일계산을위한임시변수 K : 첨자 Y : 요일 - 9 -

10 답항보기 A(J) 19 A(J) > K 20 A(K + 1) 21 A(K + 2) 22 A(K + J) 23 A(K) 24 C = C C = C C = K C 28 D(J + 1) 29 D(J - 1) 30 D(J) 31 J 32 J = J = 0 34 J = 1 35 J = J = 2 37 J = C + J 38 K 39 K = K = 0 41 K = 1 42 K = A(J) 43 K = D(J) 44 K = J 45 M(J) < K 46 M(J) <= K 47 M(J) = K 48 M(J) > K 49 M(J) >= K 50 NS

11 [ 문제6] 영업점판매순위다음은 7월한달동안일별매출액을누적하여영업점별판매순위를계산하는알고리즘이다. - 영업점의수는 20개이며영업점별매출액은 S(20, 31) 로제공된다. - 계산된영업점의판매순위는 R(20) 에저장한다. - 알고리즘에사용되는변수는다음과같다. J : 첨자 K : 첨자 T(20) : 영업점별 7월매출액합계를저장하기위한배열

12 답항보기 J J + K 8 J <= 20 9 J <= J = J J = J / 2 12 J = K + J 13 J > J > J > K 16 K 17 K K + J 19 K K / 2 21 K < K <= K <= K > K > R(20) = 1 27 R(J + 1) 28 R(J) = 0 29 R(J) = 1 30 R(J) 31 R(K + 1) 32 R(K) 33 R(K) = 0 34 R(K) = 1 35 R(S(J, K)) 36 S(20, K) 37 S(31, 20) 38 S(J, K) 39 S(K, 20) 40 S(K, J) 41 T(20) = 0 42 T(J) < T(K) 43 T(J) <= T(K) 44 T(J) <> T(K) 45 T(J) = 0 46 T(J) = 1 47 T(J) > T(K) 48 T(J) >= T(K) 49 T(K) = 0 50 T(K) =

13 [ 문제7] 성과급계산다음은전체사원의연말성과급을계산하는알고리즘이다. - 전체사원의수는 100명이고, 계산된성과급은배열 PRO(100) 에저장한다. - 성과급은각사원의고과에따라차등지급된다. 고과가 가 인사원은연봉의 50%, " 나 인사원은연봉의 30% 가지급되며나머지고과에대해서는성과급이지급되지않는다. - I번째사원의고과는 EVL(I) 로제공되며, 고과가 가 는 1, 나 는 2, 다 는 3, 라 는 4로주어진다. - 모든사원에게지급된 1년동안의월급은 SAL(100, 12) 에저장되어제공된다. - 알고리즘에사용되는변수는다음과같다. J : 첨자 Y : 연봉 K : 첨자 P : 성과급지급률

14 답항보기 EVL(J) < 2 12 EVL(J) = EVL(J) = 0 14 EVL(J) = 1 15 EVL(J) = 2 16 EVL(J) = 3 17 EVL(J) > 2 18 EVL(K) = 0 19 EVL(K) = 1 20 EVL(K) > 2 21 K 22 K K K + J 25 K K < K < K <> K > K > P = 0 32 P = P = P = P = SAL( J, 1) 37 SAL(J) * P / SAL(J, K) 39 SAL(K, J) 40 SAL(P, K) 41 SAL(Y, J) 42 Y * (100 / P) 43 Y * P 44 Y * P Y * P / Y = 0 47 Y = 1 48 Y = J Y = K Y = SAL(J, 1)

15 [ 문제 8] 청구금액계산다음은각영업점에재고량에따른추가공급해야할물량을구하고이에따라영업점에청구해야할영업점별청구금액을계산하는알고리즘이다. - 영업점의개수는 N이며상품 A, B, C에대해각영업점별재고량은배열 A(N), B(N), C(N) 으로주어진다. - 재고량은 0부터 100사이의값이며, 상품별로재고의개수가 100을유지하도록추가공급물량을결정한다. - 영업점에공급하는상품 A의단가는 5,000원, 상품 B의단가는 3,000원, 상품 C의단가는 4,500원이다. - 영업점등급이 5 이상일경우 10% 의할인율이적용된다. 영업점등급은배열 G(N) 으로주어진다. - 계산된영업점별청구금액은배열 M(N) 에저장한다. - 알고리즘에사용되는변수는다음과같다. J : 첨자 NA : 상품A 추가공급량 NB : 상품B 추가공급량 NC : 상품C 추가공급량 MA : 상품A 청구금액 MB : 상품B 청구금액 MC : 상품C 청구금액

16 답항보기 * NB * NB * NC A + B + C 18 A(J) 19 A(J) + B(J) + C(J) 20 B(J) 21 B(K) 22 C(J) 23 C(K) 24 G(J) < 5 25 G(J) <= 5 26 G(J) <> 5 27 G(J) > 5 28 G(J) >= 5 29 J < N 30 J <= N 31 J = N 32 J > N 33 J >= N 34 MA * MB * MC 35 MA + MB + MC 36 NA + NB 37 NA + NB + NC 38 NA 39 NB 40 NB NB + NC 42 NB + NC / NB / NC 45 NC * NC = 0 47 NC = C(J) 48 NC = C(J) 49 NC = C(J) 50 NC = C(J)

17 [ 문제 9] 대여점회원관리다음은연말에비디오대여점에서우수고객의수를계산하는알고리즘이다. - 우수고객은지난 1년간대여점의총방문회수가 30회이상이거나총대여비디오수가전체고객의평균대여비디오수이상인고객이다. - 총연체회수가 3회를초과하는고객은우수고객에서제외한다. - 고객의총수는 N명이며 I번째고객의월별방문횟수, 월별대여비디오수, 월별연체횟수는각각 V(I, 12), R(I, 12), D(I, 12) 로제공된다. - 알고리즘에사용되는변수는다음과같다. S : 합계 J : 첨자 K : 첨자 M : 평균대여비디오수 C : 우수고객수 TV : 월별방문횟수 TR : 월별대여비디오수 TD : 월별연체횟수

18 - 18 -

19 답항보기 C 12 C = C C = C C = M 15 C = TR 16 C = TV 17 D(0, 0) 18 D(1, J) 19 D(J, K) 20 D(K, 1) 21 D(K, J) 22 J 23 M 24 N 25 N / S 26 R(0, 0) 27 R(1, J) 28 R(J, 1) 29 R(J, K) 30 R(K, 1) 31 R(K, J) 32 S 33 S * S / (12 * N) 35 S / S / N 37 TD 38 TD + D(J, K) 39 TR 40 TR + R(J, K) 41 TR + R(K, J) 42 TR <= TR >= TV + V(J, K) 45 TV + V(K, J) 46 TV <= TV > TV >= TV 50 V(J, 1)

20 [ 문제 10] 최우수강사찾기다음은영어전문학원에서학생들의토익점수를사용하여최우수담당강사를찾는알고리즘이다. - 학원에다니고있는총학생의수는 500명이다. - I번째학생의토익점수는 SC(I) 로제공된다. - I번째학생의담당강사코드는 T(I) 로제공되며이때강사코드는 1부터 10 사이의값이다. - 최우수담당강사는담당학생들의평균토익점수가가장높은강사이며, 최우수강사코드를출력한다. - 알고리즘에사용되는변수는다음과같다. J : 첨자 S(10) : 강사별토익점수합계배열 C(10) : 강사별학생수배열 B : 강사코드 MA : 강사별평균토익점수의최대값 M(10) : 강사별평균토익점수 MT : 최우수강사코드

21 답항보기 B = 0 7 B = J B = S(J) 9 B = SC(J) 10 B = T(J) 11 C C(B) C(B) C(B) / 2 15 J < J < J <= J <= J = J > J > J > J >= J >= M(B) < MA 26 M(B) > MA 27 M(J) < MA 28 M(J) = MA 29 M(J) > MA 30 MT = 0 31 MT = 1 32 MT = J MT = J 34 MT = M(J) 35 S + C 36 S(0) 37 S(J) * C(B) 38 S(J) * C(J) 39 S(J) S(J) + C(J) 41 S(J) / C(B) 42 S(J) / C(J) 43 S(J) 44 S(K) 45 S(T(J)) 46 SC(0) 47 SC(B) 48 SC(J + 1) 49 SC(J) 50 SC(S)

°ø±â¾Ð±â±â

°ø±â¾Ð±â±â 20, 30, 40 20, 30, 40 1 2 3 4 5 6 7 8 9 10 3.1 6.3 9.4 12.6 15.7 18.8 22.0 25.1 28.3 31.4 2.4 4.7 7.1 9.4 11.8 14.1 16.5 18.8 21.2 23.6 7.1 14.1 21.2 28.3 35.3 42.4 49.5 56.5 63.6 70.7 5.9 11.9 17.8 23.7