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



정올소식

커뮤니티

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

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

페이지 정보

작성자 kimdongkyoo 작성일18-06-20 19:48 조회376회 댓글0건

본문

이번주도 중고등부 같은 문제로 실시하였습니다.

수상자는 다음과 같습니다.

 

초등부 - 이승호

중고등부 - 송준혁, 반딧불

 

풀이

 

고장난 시계

 

학원에서 돌아온 원래 시간인 (h1+k)m1분을 분 단위로 환산하고

 

시계가 고장한 시간인 h2m2분을 분 단위로 환산해서 서로 빼주면 시계가 얼마나 느린지 답이 나옴.

 

팀 빙고게임

 

개인전: 가로 세로 대각선에 대해서 다 같은 알파벳인 개수를 세면 정답. (단 같은 알파벳이 여러 개의 선을 지배할 수도 있으므로, 한번 셌던 알파벳은 체크배열을 이용해서 다시 안 세도록 해야 함)

 

팀 전: 가로 세로 대각선에 대해서 알파벳이 두 개만 나오는 개수를 세면 정답.(, 같은 알파벳 쌍이 여러 개의 선을 지배할 수도 있으므로, 한번 썼던 알파벳 쌍은 체크배열을 이용해서 다시 안 세도록 해야함)

 

함수를 적절하게 활용하여 이용하여 코드를 간단히 하는 연습을 하는 것이 좋다.

 

 

 

음식 저장하기

 

어차피 모든 음식은 어느 냉장고에는 넣어야 한다.

 

키워드는 어차피”: 이런 말이 나오면 일단 욕심쟁이(그리디) 알고리즘으로 접근한다.

 

그냥 무작정 냉장고에 넣다가, 두 개 이상의 냉장고 중 어디엔가 넣어야 한다면,

 

넣을 수 있는 냉장고 중 이미 있던 음식을 덮었을 때 가장 손해가 없는 냉장고, 즉 가장 작은 수가 위에 있는 냉장고를 고른다.

 

첫 예제인 4 3 5 1 2를 예로 들면,

 

가격 4짜리 음식을 일단 냉장고에 넣는다.

 

가격 3짜리 음식을 같은 냉장고에 넣는다.

 

가격 5짜리 음식을 넣을 냉장고가 없으므로, 하나 더 구해와서 넣는다.

 

가격 1짜리 음식을 두 냉장고 중 하나에 넣을 건데

 

가격 3짜리 음식을 덮어버리는게 더 높은 가격을 커버할 수 있는 5짜리 음식을 덮어버리는 것보다 이득이므로 첫 번째 냉장고에 넣는다.

 

가격 2짜리 음식을 두 번째 냉장고에 넣는다. (1 위에 넣을 수는 없으므로 두 번째 냉장고만 넣는다.)

 

, 냉장고의 필요한 수는 2대이다.

 

동맹

 

우선, Union-find, disjoint-set(서로소 집합) 에 대해 알 필요가 있다.

 

이 문제의 1 x y 형태의 지시처럼, 서로 다른 집합의 원소인 두 x y가 연결되어 한 집합이 되는 경우 사용한다. 이 자료구조의 특성 상 경로압축을 통하여 O(1)만에 Union(x,y) : xy를 연결시키는 것, 그리고 Find(x,y): xy가 같은 집합원인지 다른 집합원인지 찾아주는 것을 할 수 있다. 자세한 사항은 알고리즘에서 공부하도록 한다.

 

2 c의 쿼리를 대답하는 경우

 

가장 단순한 방법: 집합을 합칠 때 크기를 업데이트시킨 배열을 저장해 놓는다. 처음엔 {1,1,1,…,1} 인 배열이 union(x,y) 연산을 하면서 {1,1,..,1,2} 이 되고이런 식의 배열이다. 이 때, 불공정 상수 c를 넘는 집합 쌍의 수는, 배열의 가장 앞을 가리키는 인덱스 i, 그 인덱스의 원소보다 c만큼 큰 원소를 가리키는 j를 움직여가면서 O(n)만에 답을 찾을 수 있다. 쿼리가 q개이기 떄문에, O(nq)로 조금 모자라다.

 

그거보다 조금 단순한데 쉬운 방법: 집합 크기의 개수를 저장해 놓은 배열을 만든다.

 

즉 초기에는 A[1]=N, A[2]=0, A[3]=0 이런 식인 배열이다.

 

이 배열의 크기를 d라고 하면, dA[1]=1, A[2]=1, A[3]=1…A[d]=1, 즉 크기 1짜리 집합이 하나, 크기 2짜리가 하나, 3짜리가 하나…… d짜리가 하나인 경우가 최악의 경우로, 가장 d가 큰 경우이다.

 

이 때, 모든 크기를 다 합쳐봤자 N이므로, d(d+1)/2 =N 이다.

 

d가 양수이므로 부등식 d^2 / 2<= d(d+1)/2 = N 가 성립한다.

 

dsqrt(2n)보다 작다. 배열의 크기가 아무리 최악이어도 n의 제곱근 수준밖에 안된다는 뜻이다. 이 배열에서 두 개의 인덱스를 움직이는 위와 같은 방법을 사용하면, O(sqrt(n))만에 답을 낼 수 있다. 쿼리가 q개이기 때문에 시간복잡도 O(q*sqrt(n))이므로, 충분히 시간 내에 답을 출력하는 것이 가능하다.

 

점퍼

 

가장 단순한 방법: 모든 지도상의 1이 써 있는 좌표를 다 고려해서 모든 순서를 고려하는 방법.

 

O((지도상의 1의 개수)!)이다.

 

그리디 접근법: 한쪽 구석에서 시작해서 가까운 1로만 이동하는 것은 WA판정이라는 결과를 얻는다. 그러나 부분점수를 노린다면 이것이라도 해 보는게 좋겠다.

 

다이나믹 프로그래밍 접근: 어떤 직사각형 내의 최적해를 구한 DP값이 있다고 생각할 때, 그 직사각형을 작은 직사각형부터 전체 지도의 직사각형 까지 확장해 나가는 접근법. 직사각형을 좌표에 나타낼 때, 왼쪽 위 좌표와 오른쪽 아래 좌표만 필요하므로, 4개의 수로 상태를 정의할 수 있다.

 

def) DP[i][j][k][l]를 지도상의 (i,j)를 왼쪽 위, (k,l)를 오른쪽 아래 점으로 하는 직사각형 내 만 봤을때, 그 직사각형 내의 답의 최소값.

 

이 때, 직사각형을 확장해나가면서, DP값을 업데이트시키면 된다.

 

본 문제의 제한 내에서는 이 풀이로도 AC판정을 받는 것이 가능하다.

 

더 나은 풀이

 

직사각형 내의 최적해를 구할 거면, 어차피 긴 길이만 답에 영향을 주므로, 정사각형만 고려하면 된다. 그래서 정사각형의 길이인 ki,j만 고려하여 O(nm(n+m))만에 답을 내는 것이 가능하다.

 


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.