2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

비버챌린지 2014 문제중 Ceremony 문제를 풀어 보겠습니다.

원당컴퓨터학원 2019. 3. 16. 10:37

문제출처 : http://www.bebras.uk/answer-booklets.html


비버 마을에서 축제를 하기 위해서 많은 이벤트가 필요합니다.

어떤 특별한 이벤트는 다른 이벤트를 수행 후에 발생합니다..

다음 그림에는 모든 이벤트가 표시 되어 있습니다. 

화살표는 이벤트가 일어 났을 때 다음 이벤트를 할 수 있음을 나타냅니다.

예를 들어 Musical Intermezzo는 Choir Singing 과 Drum Roffle,Boring Speeches 이 끝난 상태에서 이벤트를 진행 할 수 있습니다.


문제는 다음과 같습니다.

아래 상자에 나오는 이벤트들을 위의 그림에 표시된 규칙을 따르는 순서로 나열하세요




정답은 다음과 같습니다.


Choir Singing

Drum Roffle

Boring Speeches

Musical Intermezzo

Fanfare

Lottery

Fireworks

Thank you


또는

Choir Singing

Boring Speeches

Drum Roffle

Musical Intermezzo

Fanfare

Lottery

Fireworks

Thank you


문제를 풀어 나가는 방법은 맨 아래 부터 순차적으로 화살표를 따라 가면서 선택해 주면 되겠죠.

만약 Musical Intermezzo 이벤트를 선택하기 위해서는 Boring Speeches 와 Drum Roffle 이벤트가 발생한 이후에만 가능합니다.

Boring Speeches 와 Drum Roffle 는 Choir Singing 이벤트가 발생한 이후에만 가능한 것 처럼 찾아 가면 되겠지만 마지막 부터 찾아 가는 것이 훨씬 더 쉬울 수 있겠네요.



여기서 나오는 컴퓨팅 과학자에게 필요한 원리는 다음과 같습니다.

컴퓨터 알고리즘 중에 토폴로지 정렬(위상정렬) 이라는 알고리즘이 있는데...
이러한 알고리즘은 선행 되어야 할 이벤트를 순서를 정해 놓고 반드시 선행 된 후에 그 이벤트를 발생 할 수 있도록 작업을 수행하는 것을 의미합니다.
이때 선행 되어야 할 이벤트들의 순서를 정해 주는 알고리즘을 위상정렬 알고리즘이라고 하는데.
이렇게 사람이 문제를 풀때는 쉬운것 같은데...
이것을 컴퓨터 프로그램으로 구현하려고 하면 까다로운 부분이 있습니다.

이러한 작업들은 자료구조 중에 스택과 기법중에 재귀 함수를 이용하여 풀어 나갈 수 있습니다.

토폴로지 정렬을 구현하는 방법에 대해서는 다음에 다시 다루도록 하겠습니다.

당분간은 비버 챌린지 문제 위주로 블로그를 작성해 나갈 예정입니다.

비버챌린지 문제가 쉬워 보이는데..

그 속에 숨어 있는 컴퓨팅 과학적인 원리가 심오해서...

이 문제를 풀다 보니 우리 학생들이 이러한 문제에 많이 노출이 되어 있으면 좋을것 같다는 생각을 하게 되네요.


비버챌린지 2014 Traffic in the city - https://wondangcom.com/776
비버챌린지 2014 Ceremony - https://wondangcom.com/777
비버챌린지 2014 Right rectangle - https://wondangcom.com/778
비버챌린지 2014 보트의 창문 - https://wondangcom.com/787
비버챌린지 2014 아이스크림 - https://wondangcom.com/793




사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기