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



정올소식

커뮤니티

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

6월 4주차 모의고사 결과및 문제풀이

페이지 정보

작성자 kimdongkyoo 작성일18-06-27 20:57 조회990회 댓글0건

본문

이번주 수상자 명단

 

초등부 - 변재우

중고등부 - 이동현, 반딧불

문제풀이

 

초등 #A. 텔레포트

 

 

답은 3가지 중 하나이다. (여기서 ||는 절대값을 말하는것으로, 두 장소간의 거리를)

농부 반디가 a에서 b로 직접 간다 -> |a-b|,

농부 반디가 a에서 x로 가서 y로 텔레포트해서 b로 간다 -> |a-x| +|b-y|

농부 반디가 a에서 y로 가서 x로 텔레포트해서 b로 간다 -> |a-y| + |b-x|

저 세개의 값 중 최소값이 답이다.

 

초등 #B. 무당벌레

한 칸이라도 빈 칸이 있으면, 모든 무당벌레의 이동이 자유롭기 때문에 빈 칸(_)이 있을 때와 없을 때가 다르다.

빈 칸이 없다면, 현재 이미 행복한 상태면 YES, 한 마리라도 행복하지 않은 무당벌레가 있다면 NO이다.

빈 칸이 있다면, 무당벌레 종류를 A부터 Z까지 다 세서, 종류당 한 마리밖에 없는 경우가 있다면 NO, 모든 종류가 두 마리 이상이 있다면 YES이다.

중등 #A. 짝짓기

모든 값이 0으로 초기화된 두 배열을 만든다. 한 배열은 혁규네 반 학생들의 번호에 해당하는 인덱스를 1로 체크해놓고, 다른 배열은 혁규네 옆 반 학생들의 번호에 해당하는 인덱스를 1로 체크해놓는다.

1부터 20까지 중, 두 배열 다 1로 체크된 번호는 짝이 있는 학생들이고, 두 배열 다 0인 번호는 아예 어느 쪽 반에도 없는 학생 번호이므로, 한 배열만 1로 체크된 학생들의 인덱스를 출력한다.

 

초등 #C./중등 #2 장난감 만들기

DFS를 사용하는 방법: 재귀함수 f(x,y,z)를 선언한다.

이 함수는 1)좌표 (x,y,z)의 노출된 표면적을 최종 답에 더해주고 2) 인접한 다른 붙어있는 육면체를 호출해주는 함수이다.

f(1,1,1)를 호출한 후, 이 방법을 통해 모든 육면체를 순회해주면 답이 구해진다.

(가로*세로*높이로 순회 : O(n^3))

 

보드판 내에서 가로 세로를 순회하며 더해주는 방법

 

(x,y)좌표에서 높이 h의 육면체의 총면적은 2+4*h이다. 그런데 상하좌우에 있는 겹치는 면적(인접한 육면체와 자신의 높이 중 낮은 값) 만큼은 안보이므로, 빼 주면 된다. 가로 세로만 순회하므로, O(n^2)이다.

 

초등#D 중등#C : 우유짜기

 

문제 풀이에 앞서, 이렇게 여러 개 의 순서들이 서로 공존할 수 있다는 것은, 방향 그래프로 바꿨을 때 사이클이 안 생긴다. DAG(Directed Acyclic Graph)를 이룬다는 말과 같다. 이 것을 바탕으로, 우리는 앞으로 사이클이 안 생기는 위계질서 체계를 가능하다라고 부르고, 아닌 것을 불가능하다라고 할 것이다.

처음으로 할 일은 위계질서의 한계치인 X를 구하는 것이다.

1부터 M까지 중 어느 위계질서 Z까지가 가능하다고 하면,

1부터 Z 중 어느 값이든 위계질서 유지가 가능하지만, Z+1부터 M까지는 아직 모른다.

반대로 1부터 M까지 중 어느 위계질서 Z까지가 불가능한 위계질서면, Z+1부터 M까지는 당연히 X값의 후보가 안되므로, 그 위에는 볼 필요가 없다.

이것은 이진 탐색의 알고리즘적 아이디어랑 정확히 일치하므로, 우리는 1M을 시작점 끝점으로 해서 이진 탐색을 할 수 있다. mid(=(st+ed)/2) 까지 위계질서가 가능하면 stmid+1, 불가능하면 edmid-1로 하는 식으로 말이다.

여기까지 과정은, M까지를 다 고려한 그래프의 모든 간선 수를 E라고 할때, O(ElogM)이 걸린다. 우선 X를 찾고 나면, 그 때의 그래프가 나올 것이다.

이 중 제일 우선 출력해야 하는 것이 현재 자신을 가리키는 간선이 없는 정점들이다. 이 정점들이 여러 개 있을 수 있으나, 우리는 가장 작은 숫자가 앞에 오는 것을 답으로 하므로, 우선순위 큐에 이 정점들을 다 넣고, 우선순위 큐에서 정점 번호를 하나 뽑아와서 출력하고, 그 정점을 그래프에서 지우고, 다시 자신을 가리키고 있지 않은 정점을 추가하는 식으로 진행한다.

그 과정은 O(E+NlogN)이 걸린다. 결과적으로 O(ElogM+NlogN)의 시간복잡도를 가지므로, 문제 조건을 만족시키기 충분하다.

 

 

중등#D. 몰래게임 감지기

 

 

시작에 앞서, 출제자가 원하는 이 문제의 접근방식:

1.     중 최대치, …중 최소치, …중 최적값, …를 다 구하는 경우의 수, …를 구하는 확률. 이런 키워드들은 DP(Dynamic Programming, 다이나믹 프로그래밍, 즉 동적 계획법)에 따라다니는 꼬리표들이다.

2.     DP라는 걸 가정하고, 부분문제를 정의 할려고 한다. 당연히 하나의 인덱스는 N을 나누는 것이다. 제한을 의심해 보자. 이 문제의 N제한은 100 이하이다. O(N^3) 정도의 상태 분할이 가능하다는 것이다.

3.     따라서 상태를 정의할 때, N의 부분문제를 생각하는 것 말고도, 두 가지 정도의 상태를 더 정의할 수 있다.

이렇게 꼼수(?)로 접근하면, 접근 시간을 조금 아낄 수 있다. DP문제는 보통 DP임이 자명하지 않기 때문에, DP냄새를 맡는 연습이 필요하다.

입력한 각 분마다의 기록을 엔트리라고 부르겠다.

이제 정해를 찾아보자. 우선, 우리가 문제를 보면, 몇 번 게임을 했느냐 따라서 답을 각각 출력해야 하므로, 하나의 인덱스는 몇 번 게임을 했느냐로 생각하자. 또한, 마지막에 게임한 시간이 지금 현재 엔트리(입력된 값)가 맞는 엔트리인지 틀려서 바꿔야 하는지를 결정하므로, 마지막에 게임한 시간도 인덱스로 정의해보자. 예를 들어, 3분에 마지막으로 게임을 했으면, 5분에는 엔트리가 2여야 맞는것이고, 2가 아니면 최적값에 1을 더해줘야 한다(그 값을 2로 바꾸는데 드는 값이다.)

이제 간단하다. Dp.i.j.k.를 정의하고, 연계된 점화식을 찾으면 된다.

DP.i.j.k. = i분까지만 봤을 때, j분에 마지막으로 게임한 학생이 있어서, k번 게임을 하는 경우의 최적값(최소 엔트리 변경 회수)이라고 하자. 여기서 jk는 우선관계가 없으므로, 서로 바꿔 써도 무방하다.

여기서 j<i라면, i분에 게임을 한 것이 아니기 때문에, 부분문제의 최적값인 DP[i-1][j][k]와 같다.

j==i라면, i분에 게임을 한 것이 된다. 이 경우는 총 게임 횟수가 1번 늘어난 것이므로, 부분문제의 k-1 부분에서 찾아야 하며, 그 부분문제의 어떤 j도 참조할 수 있다. 어차피 i분에 게임을 했다면, 그 전에 마지막으로 게임을 언제 하든 답의 후보가 될 수 있기 때문이다. 즉 이 경우는 min(j’:1->i-1, DP[i-1][j’][k-1]) //j’ 0부터 i-1까지 순회할 때 최소값)이 된다.

모든 경우에, 엔트리가 j-i과 같지 않다면, 그 엔트리를 변경하는데 1만큼의 값이 들기 때문에, DP값에 그 만큼 더해줘야 한다.

j<i인 경우 i,j,k를 순회하므로 O(n^3)이고,

j==i인 경우는 k를 순회하되, i==j인 제한적인 경우인 O(n^2)인데, 최소값을 구하기 위해 j’를 순회하므로, O(n^3)이다. 결론적으로 O(n^3)이다.

정답은 DP의 정의에 따라, k번째 줄에 min( j’:1->i-1, DP[N][j’][k])을 찾아 출력하면 된다. 우리나라말로 풀어 쓰자면, N까지 엔트리를 봤을 때, 마지막에 게임을 한게 j’이고 k번 게임을 한 경우들을 고려한 것이다.

 


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.