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



정올소식

커뮤니티

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

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

페이지 정보

작성자 kimdongkyoo 작성일18-07-05 16:29 조회391회 댓글0건

본문

이번주 수상자

초등부 - 최민수

중고등부 - 전정현, 반딧불

 

문제 풀이

#A. 기차표

8좌석마다 같은 패턴이 반복되므로,

입력받은 좌석 번호를 8로 나누었을 때, 나머지가

-       1 또는 4 à LB

-       2 또는 5 à MB

-       3 또는 6 à UB

-       7 à SLB

-       0 à SUB

이다.

만약 이 방법이 떠오르지 않는다면, 각 번호에 따른 if 조건문을 72개 작성해서라도 풀어야 한다.

#B #A. 군대 생활

i번 인덱스에 i번까지의 모든 생활관 인원의 합을 구해놓은 누적 배열을 만든다.

1부터 m까지 누적 배열을 순회하면서, k보다 배열에 저장된 값이 커지는 최초의 인덱스가 답이다.

#C. 숫자 소용돌이

풀이는 간단하나, 구현이 지저분할 수 있는 문제.

부분점수: 1<=r<=1000 인 경우

1초마다 보드판의 상태를 업데이트한다. 문제에서 하란 대로, 각 회로별로 한 칸씩 반시계 방향으로 업데이트 하면 된다. 시간복잡도 : O(nmr)

정해: 1<=r<=10^9인 경우

 

 

 

 

각 회로(순환하는 직사각형)별로 생각한다. 회로를 맨 왼쪽 위 숫자부터 시작해서, 반시계 방향으로 돌면서 배열에 저장한다. 이 배열의 크기는 당연히 회로의 길이가 된다. 이 회로의 길이(=배열의 크기)k라고 하자.

k초마다 숫자들이 한 바퀴를 돌기 때문에, 처음과 같아지게 된다. r초 후의 이 회로의 상태는, r%k초 후의 상태와 같다. 따라서 배열을 r%k번째부터 순회하면서, 다시 왼쪽 위부터 순회하면서 숫자를 배치하면, 답이 된다.

예를 들어보자. 다음과 같은 보드판이 있고, r30이라고 치면

1 2 3 4 5 6

2 3 4 5 6 7

3 4 5 6 7 8

4 5 6 7 8 9

맨 바깥쪽 회로를 왼쪽 위부터 시작해서 반시계 방향으로 돌면서 배열에 저장하면,

배열 a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2], 크기 16짜리 배열이 된다. 즉 이 회로에서는 16초마다 같은 상태가 된다. r%1614번째부터 순회하면서 왼쪽 위부터 채워나가면 된다.

,

a[14]a[13]a[12]a[11]a[10]a[9]

a[15]                         a[8]

a[0]                          a[7]

a[1] a[2] a[3] a[4]  a[5]  a[6]

이 답이 된다.

이 작업을 각 회로별로 반복해주면 된다.

이 외에도 방법은 여러 방법이 있지만, (회로의 길이)초마다 상태가 순회한다는 점을 이용한다는 것은 동일하다.

시간복잡도 = O(nm) (모든 회로를 두 번씩 순회하며, 모든 회로의 길이를 다 합치면 nm이므로, 2nm번 순회함)

#D #B #A. 타임어택

배열 내 몇 개의 숫자는 바꾸고, 몇 개의 숫자는 바꾸지 않을 때,

안 바꿔도 되는 숫자들의 개수를 최대화하면 되는 간단한 문제. (=바꿔야 하는 숫자=N-안 바꿔도 되는 숫자)

각 배열 숫자를 a[1] a[2] … a[n] 이라고 하자.

a[i]를 그대로 내둘 때, a[j]도 그대로 나둬도 된다면, a[i]a[j]가 같은 집합이라고 정의하자.

a[i]a[j]가 같은 집합이라는 것은(i<j라고 가정할 때)

조금 더 수식적으로 말하자면,

a[j]a[i]의 차이가 (j-i)*k 만큼 난다는 것이다. 예를 들어 a[2]를 그대로 내두면, a[5]3칸 뒤이므로, a[5]a[2]+3*k와 같은 값이라면 a[5] 역시 바꿀 필요 없다는 것이다.

부분점수: 명시된 부분점수는 없지만, O(n^2) 해법을 쉽게 생각해낼 수 있다.

i 1번부터 n번까지 순회하면서, a[i]를 그대로 내둔다고 생각하자.

j1번부터 n번까지 순회하면서 a[i]를 그대로 내두어서 a[j]역시 그대로 내두어도 되는 경우를 카운트한다.

이 카운트값이 가장 높은 경우가 답이다.

정해:

사실 부분점수 해법에서, 조금만 더 생각하면 된다.

a[i]a[j]가 같은 집합인 것을 알기 위해서, a[j]-a[i]==(j-i)k인 것을 모든 i,j 쌍에 조사해야 하기 때문에 O(n^2)인 것이었다. 모든 쌍에 대해 a[j]-a[i]를 조사하는 대신, a[i]-ik가 같은 원소들은 모두 같은 집합이다. 따라서 Count[a[i]-i*k]를 증가시키고, 가장 큰 값을 가지는 Count값이 답이 된다(정확히는 가장 N-Max(Count값들)).

a[i]-i*k값은 범위가 음수일 수도 있으며, 양수 범위도 엄청 커질 수 있다. 따라서 일반적으로 사용하는 자료구조인 배열을 이용하면, 메모리 문제가 발생한다. 이럴 때 STL map을 이용하면 Count[-100000]++이나 Count[ 1000000000]++등을 할 수 있다. map을 이용하는데, 자료 크기를 n이라고 하면 log(n) 만큼의 시간복잡도가 들기 때문에, 정해는 O(nlog(n))이라고 할 수 있겠다.

#C #B. 일방통행 시티

원래 그래프에서 최장거리를 구하는 문제는 NP-완전 문제이다.

그러나, 이 그래프는 특수한 형태이므로, 솔루션이 존재한다.

1부터 n까지의 마을을 오리지널 마을이라고 하자.

우선, i번 마을이 오리지널 마을이면,

i번 마을에서 파생된 추가 마을들간의 거리의 최댓값을 depth(i)라고 하자.

depth(i), N개의 max_heap을 만들고, i번째 max_heap에다가 i번 마을에서의 거리를 저장시키는 방법으로 빠르게 찾아낼 수 있다.

두 오리지널 마을 i,j간의 거리를 distance(i,j)라고 하자.

distance(i,j)는 입력값을 누적시킨 배열을 이용하여 O(1)만에 구할 수 있다..

이하 설명에 마을이라 칭함은 모두 오리지널 마을이라고 생각하자. 추가된 마을은 모두 max_heap에 저장되어있기 때문에 크게 생각할 필요 없다.

번호가 높은 마을에서 번호가 낮은 마을을 향해 가는 것을 표현하기 위해, (n+1)번부터 (2n-1)번 마을 까지로 확장한다. i(n+1<=i<=2n-1) 마을은 i-n번 마을과 동일하다. 따라서, 예를 들어 5개의 마을이 있고, 5번 마을부터 3번 마을까지는 5번 마을부터 3+5=8번 마을까지라고 생각하는 것이다. 이로써 고리형 구조가 선형 구조로 바뀐다.

이제 1번부터의 i번까지의(1<=i<=2n-1) distance(1,i) + depth(i)를 구해 저장해놓고, 이를 인덱스트리에 저장한다. 인덱스트리의 특성인 구간 내의 최적값을 빠른 시간(보통 log(n)) 내에 구한다에 착안한다. 저장 해놓으면, 1번부터 n번까지, 2번부터 n+1(=1)번 까지, 3번부터 n+2(=2)번 까지 … n번부터 2n-1(=n-1)번까지의 답의 최대값이 나온다. 물론 인덱스트리에 저장되있는 값은 모두 1번 마을에서 출발하는 것이 기준이기 때문에, i번부터 i+n-1번 까지의 최대값을 구한다면 거기에서 distance(1,i)를 빼주는 것이 정확한 답일 것이다. 4 x 쿼리를 간단하게 답 할 수 있다.

또한, 이 문제에서의 나머지 쿼리들도 정확한 위치를 구하고(1 x w 쿼리와 3 x 쿼리의 경우 구간의 최대값을 가지는 마을의 인덱스를 구하고, 2 x w의 경우 그 자리이므로 간단하다), 그 위치에서 depth만 추가 또는 삭제 해주면서 인덱스트리를 업데이트 시키기만 하면 된다. 주의할 점은 1 x w의 쿼리에서는 “x에서 가장 먼 노드에 추가하는 것이므로 depth(i)+w max_heap에 추가해야 하고, 2 x w“x에 추가하는 것이므로 wmax_heap에 추가해야 한다는 것이다.

#D #C 창고 털기

평면도(위에서 본 전경)를 고려하지 않은 답을 생각해보자. 아주 간단한 문제가 된다.

주어진 상자들 중 가장 높은 높이의 쌀가마 더미의 높이를 H[1]이라고 하자.

H[1]의 높이를 갖는 가로줄 수(좌측면도 기준으로 H[1]높이의 쌀가마 더미 수)R[1],

H[1]의 높이를 갖는 세로줄 수(정면도 기준으로 H[1]높이의 쌀가마 더미 수)C[1]개라고 하면,

어디에 놓던 상관없이, max(R[1],C[1])개의 장소에는 H[1]의 쌀가마 더미가 필요하다. 따라서 H[1]*max(R[1],C[1])만큼의 쌀가마는 남겨놔야 한다.

같은 식으로 H[2], H[1]다음으로 높은 높이를 고려해보자. 이번엔 H[1]H[2]를 가려줄 수 있으므로, R[2] 또는 C[2]0이 될 수도 있지만, 어쨌든 H[2]*max(R[2],C[2])만큼의 쌀가마는 남겨놔야 한다.

일반화시켜서, 답은 간단하게 이 모든 H[i]*max(R[i],C[i])값의 합이다.

자 이제 평면도가 들어온다면 두 가지가 달라진다. 첫 번째는, 쌀가마를 놓은 칸 개수(= max(R[i],C[i])의 합)가 평면도에서 보이는 칸들보다 적을 수 있다는 것이다. 이는 평면도에서 보이는 칸-실제로 놓은 칸 만큼을 더해줌으로써 해결할 수 있다. , 쌀가마가 보여야 하는 빈 칸에 1짜리 쌀가마들을 하나씩 놓은 것이다. 아주 간단하게 해결되었다.

두 번째가 문제인데, R[i]C[i]의 교차점 중 하나가 평면도에서 0이라면 그 칸에는 쌀가마를 못 놓는다는 것이다. 그래서 모든 H[i]에 대해서 단순히 max(R[i],C[i])보다는 더 많은 칸에 쌀가마를 놓아야 되는 경우가 있다는 것이 문제이다. 이는 각 가로줄과 세로줄의 이분 매치 문제가 된다. 가로줄과 세로줄을 양 사이드의 노드들로 보고, 교차점이 평면도에서 보이는 좌표라면 연결시켜놓는다. 가장 많은 매치의 수를 Bipartite(i)라고 할 때, max(R[i],C[i])R[i]+C[i]-Bipartite(i)로 대체된다. 위 식을 알기 쉽게 설명하자면, 가로줄 만큼, 또 세로줄 만큼의 칸을 사용하되, 매치되는 칸인 Bipartite(i) 만큼은 가로 세로를 동시에 커버 가능하므로, 빼준다는 의미이다.

모두 고려해서 답은

H[i]*(R[i]+C[i]-Bipartite(i))의 합 + 평면도의 보이는 칸 개수 - (R[i]+C[i]-Bipartite(i))의 합 이 된다.

#D 화물 트럭

답을 a라고 했을 때, a대의 트럭이 0에서 n-1로 가는 식의 문제. 여기서 네트워크 유량 문제의 냄새를 맡는다면 80%는 성공이다.

냄새를 맡았다면, 다음과 같이 접근한다.

답은 어차피 1부터 (k-1) 사이에 있기 때문에(총 트럭이 k대라면, 한 도로로만 달려도 최대 손상은 k-1밖에 안된다), 이진 탐색을 이용해 그 구간에서의 답이 a라고 가정한다.

우리는 각 간선들을 두 간선으로 쪼갤 것이다. 한 간선은 용량(, 트럭이 통과할 수 있는 최대 수) a이고, cost0(이 간선을 통해서 가면 수리비가 0이다)인 간선이다. 다른 간선은 용량이 무한대(사실 여기서 무한대는 k이면 충분하다 k대 이상은 통과하지 않기 때문에)이고, cost 1인 간선이다(이 간선을 이용하면, 수리비가 1씩 청구된다.) 그렇게 했을 때, mincost-maxflow(최소비용-최대 유량)을 돌려서 나온 cost가 우리가 사용할 수 있는 수리비인 t보다 크다면 답은 a보다 작은 것이고, 반대로 t보다 작다면 답은 a보다 큰 것이다. 이를 통해 다음 이진탐색의 단서를 얻을 수 있다.

Mincost-maxflow가 대중적인 알고리즘이 아니므로, 간단하게 부연설명을 하자면

네트워크 플로우(네트워크 유량) 문제에서 사용하는 알고리즘부터 시작해보자.

최대 유량 문제에서 dfs를 이용해서 Source에서 Sink까지의 경로를 찾는, 시간복잡도 O(E|f|)(f는 최대 유량)의 포드-퍼커슨 알고리즘이나, bfs를 사용하는 시간복잡도 O(VE^2)의 에드몬즈-카프 알고리즘은 모두 경로 선택에 우선순위가 없다는 점에 착안한다. 즉 검색된 경로 어디로든지유량을 흘려보내면, 역방향 간선에 음수 flow를 주는 방식이 잘못 선택한 경로를 잡아주기 때문에, 그 경로를 선택할 수 있다는 것이다.

지금처럼 유량 하나가 흐르는데 cost가 드는 경우, 경로 선택시에 cost가 적은 경로로 우선적으로 가야 한다는 제한이 생긴다. 어디서 많이 본 장면 아닌가? 최단경로에서 가중치가 없다면 bfs를 사용하고, 가중치가 있다면 dijkstra를 사용한 것과 마찬가지이다. minimum-cost의 경로를 우선적으로 찾기 위해 경로 탐색 알고리즘을 bfs 대신 dijkstra로 대체하기만 하면 Mincost-maxflow가 된다.


 


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.