7월 2주차 모의고사 결과 및 문제풀이 > 공지게시판



정올소식

커뮤니티

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

7월 2주차 모의고사 결과 및 문제풀이

페이지 정보

작성자 kimdongkyoo 작성일18-07-23 20:45 조회248회 댓글0건

본문

​이번주를 끝으로 전국대회 모의고사를 마칩니다.

각 주별 수상자 외에 그동안 참여도가 높은 참여자를 선정하여 별도 시상할 예정입니다.

그동안 수상자는 메일 또는 전화를 통해 주소를 알려주시기 바랍니다.

감사합니다.​

수상자

초등 - 최민수

중등 - 이서현

고등 -호수리

 

문제풀이

초등부#A. 프로그래머의 날

핵심 개념: 문제 이해 능력, 조건문 사용 능력

율리우스력(1918년보다 작을 때) : 4로 나누어 떨어지면 윤년이므로, 평년보다 느린 912일이 프로그래머의 날이 된다. 평년엔 913일이다.

그레고리력(1918년보다 클 때): 400으로 나누어 떨어지거나, 100으로 나누어 떨어지지 않으면서 4로 나누어지면, 윤년으로, 912일이 프로그래머의 날이다.

1918: 9 26일이다 프로그래머의 날이다.

윤년이냐 평년이냐 1918년이냐에 따라서,

“13.09.”, “12.09.” 또는 “26.09.”에 입력받은 Y를 붙여 출력하면 된다.

초등부#B 중등부#A. 포켄몬스터

핵심 개념: 빠르고 정확한 구현 능력, 복잡한 설명을 빠르게 이해하는 능력.

하라는 대로 배틀 시뮬레이션을 똑같이 하면 된다. 어느 한 명의 포켄몬이 다 쓰러질 때까지 공격하고, 체력을 깎고, 쓰러지면 다음 포켄몬을 내는 작업을 반복한다. 풀이는 자명하지만, 구현의 복잡함을 어떻게 빠른 시간안에 극복해 낼 것인지 물어보는 문제.

부분문제 1: 주어진 입력의 답인 Sangsoo를 출력하면 부분문제 1이 해결되며, KOI 규칙상 4점을 받는다.

부분문제 2: 노말 타입끼리는 상성관계가 없으므로, 상성관계를 구현하지 않고 풀면 부분점수인 16점을 획득한다.

부분문제 3: 입력받은 상수의 포켄몬의 공격력을 두배, 범수의 포켄몬의 공격력을 반감시키고 부분문제 2를 똑같이 돌리면, 부분점수인 24점을 획득한다.

초등부#C 중등부#B 고등부#A 버스 정류장

핵심 개념: 이진 탐색

버스보다 빠르거나 같은 속도를 가진 사람들(?)은 그냥 걸어서 끝까지 가면 답이다. (부분문제 1의 풀이기도 하며, KOI 규칙으로는 5점을 획득한다.)

부분문제 2, 3: 모든 버스정류장으로 다 가서 기다리는 식으로 구현하면 매 q명의 주민들의 경우마다 n개의 버스정류장을 순회해야하며, 이는 O(nq)가 된다. 부분문제 2, 3을 해결하기 충분하다.

정해:

버스보다 느린 정상인이라면,

정답은 3가지 중 하나이다.

-       본인보다 앞에 있는 버스정류장으로 가서 기다렸다가 버스를 타고 간다.

-       본인보다 뒤에 있는 버스정류장으로 가서 기다렸다가 버스를 타고 간다.

-       버스를 기다리지 않고, 걸어서 끝까지 간다.

몇 가지 생각해 보면, 다른 옵션들은 생각할 필요가 없다는 것을 쉽게 알 수 있다. 수학적으로 설명하는 것이 정확하겠으나, 이는 매우 지루하고 이해하기도 힘들기 때문에, 일상 생활 속의 예를 들어 설명해보겠다.

1.     바로 앞의 버스정류장보다 더 앞에 버스정류장은 갈 필요가 없다. 예를 들어보자. 당신은 대전역에서 서울역을 기차를 타고 가는데, 부산에서 출발한 열차를 타려고 한다. 굳이 일부러 대구역으로 가서 열차를 앞서 탈 필요가 있겠는가? 같은 열차가 어차피 대전역으로 올텐데 말이다.

2.     바로 뒤의 정류장보다 더 뒤의 정류장도 갈 필요가 없다. 대전역에서 서울역을 기차를 타고 가는데, 굳이 자전거를 타고 천안역까지 가서 탈 필요가 있겠는가? 어차피 같은 기차를 타면, 같은 시간에 도착할텐데 말이다.

자신의 위치보다 바로 앞이나 바로 뒤의 정류장을 찾는데는 log(n)의 시간이 걸린다. 버스 정류장의 위치는 어차피 모두 정렬되어 있기 때문에, 이진 탐색으로 빠르게 찾을 수 있기 때문이다. 따라서, O(qlog(n))만에 문제를 해결할 수 있다.

초등부 #D 중등부 #C 고등부 #B 삼목 게임

핵심 개념: DB(데이터베이스), 단순 탐색(백트래킹)

부분문제는 의미가 크게 없다. 마지막 백돌이 높이 1에서 끝난다고 해도, 다른 곳에서 높이 2, 3, 4짜리가 생길 수도 있기 때문이다.

이 문제는 일단 시간, 공간복잡도에 상관 없이 풀어내기만 한다면 무조건 O(1)로 만들 수 있다. 입력받는 경우의 수 자체가 1<=x<=4, 1<=a<=4, 1<=b<=4로써, 64개밖에 되지 않는다. 64개의 경우를 DB로 만들어 놓고, 입력 받아서 출력하기만 하면 된다.

따라서 풀이는, 모든 경우를 그냥 다 해보는 무식한 단순 DFS 탐색 방법이다(백트래킹)그러나 알고도 만만치 않아 보인다. 다음은 당신이 단순 탐색을 할 때 만날 수 있는 여러 장애물과, 그 해결법이다.

-       같은 상태가 한번 탐색했던 상태인지 아닌지를 확인하기 위해 소위 말하는 체크배열이 필요하다. 그러나, 보드판의 상태를 체크배열에 어떻게 넣을 것인가? 보드판은 빈 칸이거나, 흰돌 또는 검은돌이므로 칸마다 총 3개의 경우뿐이다. 칸이 16개밖에 없으므로, 총 경우는 3^16개인 43,046,721개이다. 이는 여전히 공간적으로 부족하긴 하지만, STL set이나 map을 이용하면 충분히 체크할 수 있다.

-       매 상태마다, 게임이 끝났는지 안끝났는지 확인하는 것은, 보드판의 상태가 주어졌을 때, 끝났는지 안끝났는지 확인하는 함수를 하나 만들면 간단하다. 답을 세는 경우는, 끝나는 조건일 때 마지막으로 놓은 게 백돌이고, (a,b)인 경우이다.

중등부 #D 고등부 #C. 닮은 문자열

핵심 개념: 접미사 배열, 이진 탐색, 정렬, 해싱

우선, 가장 무식한 방법(brute force)로 풀면, 즉 매 질문마다 해당 부분문자열과 닮은 부분문자열을 모두 순회하여 찾는 방식으로 풀면 부분문제 1을 풀 수 있다. 시간복잡도 O(n^2*q)가 되며, q개의 질문마다 닮은 부분문자열이 최대 n개 있고, 그마다 비교하는 과정이 n이 들기 때문에 위 시간복잡도가 나온다.

부분문제 2 정도의 제한을 풀려면, 접미사 배열(Suffix Array)를 정렬하는 방식을 사용한다. 접미사 배열의 사용은 다음과 같다. 예를 들어 주어진 예제 giggabaj에서,

0번 접미사 : giggabaj

1번 접미사 : iggabaj

2번 접미사 : ggabaj

3번 접미사 : gabaj

4번 접미사 : abaj

5번 접미사 : baj

6번 접미사 : aj

7번 접미사 : j

이후 위 배열을 정렬한다. 단 이때, 중요한 것은 이 문제에서 문자열끼리 같다(==)라는 것은, 기존의 정의대로가 아니라, 문자열끼리 닮았다는 것이기 때문에, 같다의 정의를 새롭게 해줄 필요가 있다. , 우리가 STL 정렬에서 두 객체끼리 비교를 하기 위하여, compare함수 포인터를 인자로 보내던가, < 연산자 오버로딩을 하게 되는데, 이 때 이 함수를 새로 정의해야한다는 것이다. 여기에서 단순히 문자열 길이만큼 순회하여 비교한다면 O(n^2logn)으로, 부분문제 2의 제한을 간당간당하게 통과한다. 답을 구하는 것은, 새로운 같다(==)의 정의로 해당 접미사를 이진탐색하면 된다.

정해는 다음과 같다. 문자열을 구성하는 문자는 결국 a부터 j까지 10개밖에 없기 때문에, 두 접미사를 비교함에 있어서, 가장 우선시되는 문자가 있을 것이다. 위의 예에서 0번 접미사의 우선순위 문자는 g, i, a, b, j, 나머지 안 쓰인 문자들 순이다. 각 접미사들마다 문자를 해싱하여 저장해 놓고, 비교할 때마다, 우선순위가 되는 문자들을 꺼내서 서로 닮았는지 비교하는 방법을 생각할 수 있다. 이로써 시간복잡도는 O(nlogn)이 되며, 문제의 제한을 풀기에 충분하다.   

고등부#D. 장난감 저울

핵심 개념: DP(동적 계획법), 라그랑지 보간법

일단 여러분이 고등부 D번 문제풀이를 보고 있다면, 이 문제의 42점 부분문제는 그냥 풀 수 있는 수준이라고 가정을 하겠다. 여러분이 생각하는 그것이 맞다. DP[i][j]를 무게i j번까지의 추만 써서 만드는 가짓수로 놓고, 점화식을 세워 풀면 된다. 출제자는, 여러분들이 문제를 보자마자 42점의 전략을 세우기 바라고 이 문제를 냈다.

문제는 정해이다. 우리의 유일한 힌트는 모든 무게추들의 곱이 10^5이하라는 것이다.

놀랍게도, 이 문제와 같은 형식에서 (동전 문제인데, 같은 가치의 동전도 다른 것으로 세며, 동전 수가 무한할 때 경우의 수 문제인 경우) 다음이 성립한다: 무게 x를 만드는 경우의 수를 f(x)라고 하고, 모든 동전의 가치(즉 추의 무게)의 곱이 w라고 하며, 동전의 종류(추의 종류)의 수를 N이라고 할 때, i에 관한 함수 f(wi+rem) (0<=rem<w , rem w는 정수 상수)는 변수 i에 있어서 N차 다항식이 된다. 따라서 함수 g(t) = i0부터 t까지 f(wi+rem)의 합 이라고 했을 때, g(t)(N+1)차 다항식이 된다. N+1차 다항식을 결정하기 위해선, N+2개의 정점이 필요하다. (예를 들어 직선의 식을 결정하려면 두 정점이 필요하다.) 따라서 우리는 g(0),g(1),g(2)..g(N+2)까지만 구하면 함수 g(t)를 구할 수 있어서 큰 t에 대해 그 값을 구할 수 있게 된다.

결론적으로, 문제에서 w의 제한이 10^5 이하였으므로, 10^5 * (N+2)까지만 부분문제 1처럼 단순 DP로 풀면, 이 문제를 풀 수 있다.

 

 


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.