모의고사 해법(5/9) > 공지게시판



정올소식

커뮤니티

정올소식
자유게시판
질문게시판
자주하는질문(FAQ)

모의고사 해법(5/9)

페이지 정보

작성자 관리자 작성일15-05-19 20:04 조회1,069회 댓글0건

본문

 모의고사 해법을 올려달라는 요구가 많아 간단하게 해법을 정리해서 올려드리니 참고하시기 바랍니다.

완전초보자가 이해하기 위한 상세한내용은 텍스트로 올리기 어렵기에 기본적인 알고리즘을 알고 있다는 전제로 작성한 것이니 양해를 바랍니다.
 
초등부 A : 분수크기 비교
 
해법1 : 출력형식에 있는 식을 그대로 적용하여 출력하면 된다. 이 때 a, b, c, d를 정수로 선언했다면 1개 이상을 반드시 실수로 형변환을 해 주어야 한다. (- double(a) / b > c / d)
 
해법2 : 가능한 모든 연산은 실수보다는 정수로 처리하는 것이 더욱 명확하다.
위 식을 통분하여 정수 연산식으로 변환하면 실수를 사용하지 않고 더욱 명확한 결과를 얻을 수 있다.
(- a * d > c * b)
 
 
초등부 B, 중등부 A : 정보과학 경시대회
 
입력받은 점수를 정렬하여 중앙값을 출력하면 된다.
0번부터 입력받았다면 n/2번의 점수를 출력하고
1번부터 입력받았다면 (n+1)/2번의 점수를 출력하면 된다.
 
 
초등부 C, 중등부 B, 고등부 A : 동굴탐험
 
해법1) 한명씩 비교하면서 합계가 동굴의 크기 이하인 개수를 센다.
시간복잡도는 O(N2) 으로 부분점수를 받을 수 있다.
 
해법2) 정렬을 한 후 첫 번째 학생과 짝이 가능한 가장 큰 위치를 이진탐색으로 찾아내면 그보다 작은 학생들은 짝이 가능하므로 하나하나 비교해 볼 필요없이 모두 카운트한다.
같은 방법으로 두 번째, 세 번째... 모두 자신보다 큰 번호에서 짝이 가능한 개수를 세면 된다. O(N log N) 시간 복잡도로 만점을 받을 수 있다.
 
해법3) 해법2와 같이 정렬한 후 가장 큰 값부터 첫 번째 학생과 짝이 가능한 위치까지 앞으로 이동한 후 가능한 개수를 카운트 한다.
위에서 이동한 위치부터 다시 두 번째 학생과 짝이 가능한 위치까지 앞으로 이동한다.
(첫번째 학생과 짝이 불가능한 학생은 그 다음 학생들과는 당연히 짝이 불가능하다.)
앞으로 이동하면 다시는 뒤로 이동하지 않기 때문에 시간복잡도는 O(N)으로 가장 효율적이긴 하지만 어차피 정렬을 해야 하므로 전체적인 시간복잡도는 역시 O(N log N) 이다.
 
 
 
초등부 D, 중등부 C, 고등부 B : 카드놀이
 
해법1-그리디) 두 사람의 카드를 모두 정렬한 후 가능하면 상대방의 카드를 이길 수 있는 카드를 선택한다. 이 때 주의할 것은 다음 두 가지 조건을 만족할 수 있도록 카드를 선택해야 한다.
첫째, 상대방을 이길 수 있는 내 카드 중 가장 작은 카드라야 한다.
둘째, 내 카드로 이길 수 있는 상대방의 카드 중 가장 큰 카드라야 한다.
위 두 조건을 만족하는 카드를 모두 처리한 후 남은 카드 중 같은 카드를 세어서 처리하면 된다.
 
해법2-다이나믹) D[i][j] = 내 카드 i번까지 상대방카드 j번까지의 카드로 게임을 했을 때 확보할 수 있는 카드의 최대값 으로 정의하면 다음과 같은 점화식을 얻을 수 있다.
D[i][j] = MAX(D[i][j-1], D[i-1][j-1] + result(mycard[i], yourcard[j])
* result(mycard[i], yourcard[j]) 는 내카드 i번이 상대방 j번보다 크면 2, 같으면 1, 나머지는 0이 되는 것이다.
 
 
중등부 D, 고등부 C : 열매따기
 
해법) D[i][j] = i번째 나무까지 j에너지를 유지하면서 얻을 수 있는 최대 열매수로 정의하고 다음과 같이 구하면 된다.
D[i][j] = MAX(D[i-1][j-1], D[i-1][j+1] + S[i]) , S[i]i번째 나무의 열매수
* jM일때는 D[i-1][j+1] + S[i] D[i-1][j] + S[i] 로 바꾸어 주어야 한다.
 
 
고등부 D : 해저터널
 
해법1-이진탐색) 최대수심의 범위는 1~1000000 사이이다.
이진탐색으로 최대수심을 정하고 다익스트라 알고리즘으로 1부터 N까지 가기 위해 필요한 다리의 최소 개수가 K이하인지 확인하고 가능하다면 최대수심을 늘리고 불가능하면 줄이는 작업을 반복해서 가능한 최대수심의 최소값을 찾으면 된다.
 
해법2-다이나믹) D[i][j] = i번까지 j개의 다리를 놓아서 연결하기 위한 최대수심의 최소값으로 정의하고 점화식은 각자 생각해보도록 하자.
 

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.