6월 2주차 모의고사 결과 > 공지게시판



정올소식

커뮤니티

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

6월 2주차 모의고사 결과

페이지 정보

작성자 운영자 작성일18-06-12 21:06 조회370회 댓글0건

본문

이번 주 모의고사는 중고등부 문제가 동일했으며 홍보부족 및 시험기간 등으로 참여율이 저조하여 3명만 시상합니다.

시상내역 및 간단한 풀이 올려드립니다.

 

시상내역

초등부 이승현

중고등부 송준혁, 반딧불

 

문제풀이

캥거루

v2v1보다 크면 준이 이긴다. (준이 먼저 출발하고 더 빠르면 재호가 따라갈 수 없다.)

그렇지 않을 경우에는 재호(x1)가 작은 동안 계속 둘의 위치를 이동해 본다. (차이가 10000이하이기 때문에 10000번 이내에 같거나 앞서게 된다.)

같아지면 재호가, 같아지지 않고 앞서게 되면 준이 이긴다.

 

패턴세기

“10”인 위치를 찾아서 다음 “1”이 나올 때까지 모두 0이면 count를 늘려준다.

 

봄버맨 게임

1. 짝수번 째에는 항상 모두 폭탄이다.

2. 홀수번 째에는 항상 그전의 상황이 교차되면서 반복된다.

3. 10번까지만 상황을 시물레이션 해보면 간단하게 규칙을 찾을 수 있다.

 

정올전쟁

1. 각 노드를 두 개의 색으로 칠한다고 가정을 하면

2. 단말 노드의 경우 무조건 불완전한 상태로 2가지 색을 칠할 수 있다.

3. 단말 노드의 부모는 단말 노드와 항상 같은 색으로 칠해서 완전한 상태가 된다.

4. 완전한 상태의 노드와 불완전한 상태의 노드가 연결되면 같은 색으로 칠하는 경우와 다른 5. 색으로 칠하는 경우 각각 완전한 상태와 불완전한 상태가 된다.

6. 완전한 상태의 노드끼리 연결되면 곱의 법칙으로 경우의 수를 구할 수 있다.

7. 이러한 원리를 바탕으로 단말 노드부터 올라오면서 다이나믹 알고리즘으로 해결이 가능하다.

 

공항 타이쿤

1. 모든 공항이 다른 어떤 한 개의 공항으로만 이동이 가능하도록 하면 된다.

2. 가장 왼쪽(left) 공항과 오른쪽 공항(right)의 차가 d*2이면 어떤 공항도 이동할 필요가 없다. (어떤 공항이든 left 또는 right로 이동이 가능하다.)

3. left 또는 right로 이동이 가능한 공항은 조건을 충족했으므로 리스트에서 제거한다.

4. 어떤 한 공항에서 left로도 이동가능하게 하고 right로도 이동가능하게 하면 d * 2 (right left)가 된다.

5. 어떤 공항 xright로 이동이 가능하도록 right를 최소로 이동할 경우 x+1번은 left로 이동해야 하므로 xleft로 이동하는 것보다는 두 공항 사이의 차이만큼 적게 이동이 가능하다.

6. 따라서 모든 공항 사이의 거리가 최대인 경우 각각 rightleft로 이동할 수 있도록 leftright를 이동하는 것이 최적이 된다. (모두 left로 이동하는 경우와 모두 right로 이동하는 경우도 고려해야 한다.)

7. 공항이 추가될 때마다 위의 모든 경우를 계산해 볼 경우 부분점수가 가능하다.

8. 공항사이의 거리를 내림차순으로 정렬해 놓고 새로운 공항이 추가될 때마다 변경된 내용만 log N 시간에 갱신할 수 있도록 처리하면 시간내에 모든 데이터를 처리할 수 있다. 


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.