강의실/정보영재

문제출처 : 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




이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
8 0
  • 신기한별 2019.03.16 11:40 신고    

    오늘도 다녀갑니다

  • *저녁노을* 2019.03.16 12:49 신고    

    쉽진 않네요.ㅎㅎ

    잘 보고 갑니다.

    즐거운 주말 되세요

  • 청결원 2019.03.17 07:26 신고    

    포스팅 잘 보고 갑니다
    주말 휴일 잘 보내세요~

  • 핑구야 날자 2019.03.17 07:35 신고    

    자꾸 문제를 풀어 보면 좋은 결과가 있겠지요

  • 평강줌마 2019.03.17 11:17 신고    

    요즘 아이 때문에 코딩에 관심을 가지고 보고 있어요. 재미는 있는데 다소 어려운 부분도 있네요.
    편안한 일요일 보내세요.

  • 휴식같은 친구 2019.03.17 11:57 신고    

    뭔지 잘 모르겠네요.ㅎ 어럽습니다.
    즐거운 휴일 되세요.

  • 버블프라이스 2019.03.18 04:08 신고    

    15일에이은 비버챌린지 2014 문제중 Ceremony 문제를 풀이해주셧군요? 학생분들에게 많은 도움이 될 것 같습니다^^

  • 공수래공수거 2019.03.18 08:05 신고    

    관련공부 하는 학생들은 도움이 될듯 합니다.