2022년 정보올림피아드 필기 중등부(1 ~ 5)

2022년도 정보올림피아드 1차대회 필기 중등부 1번부터 5번까지 문제 풀이 입니다.

 

1번

전위 순회(preorder) 한다면 트리의 루트(root) 노드를 먼저 방문 한다는 소리 입니다. 즉 3이 루트노드가 됩니다. 1과 4가 가장 먼 이진 트리를 그려보면 다음과 같은 트리를 얻을 수 있습니다.

위 그림을 통해 거리의 최댓값은 3임을 알 수 있습니다.

 

2번

초등부 6번 문제와 같습니다. 아래 링크를 통해 6번 문제 확인 바랍니다.

https://davincicoding.tistory.com/132#6%EB%B2%88

2022년 정보올림피아드 필기 초등부(6 ~ 10)

 

3번

초등부 7번 문제와 같습니다. 아래 링크를 통해 7번 문제 확인 바랍니다.

https://davincicoding.tistory.com/132#7%EB%B2%88

2022년 정보올림피아드 필기 초등부(6 ~ 10)

 

4번

최소신장트리 문제 입니다. 크루스칼 알고리즘으로 문제를 해결할 수 있습니다. 크루스칼 알고리즘에 대해 알고 싶으면 아래 링크 확인 바랍니다.

https://wikidocs.net/207012

01. 크루스칼 알고리즘

위 그림에서 가장 짧은 노드들을 선택합니다. 만약 사이클이 발생한다면 그 노드는 선택하지 않습니다.

1. 가장 짧은 2를 가진 노드 2개를 모두 선택합니다. 2 + 2 = 4
2. 하단 아래는 사이클이 발생하기 때문에 넘어갑니다. 다음 우측 3을 선택 합니다. 4 + 3 = 7
3. 4를 선택 합니다. 7 + 4 = 11
4. 5는 사이클이 발생합니다. 가운데와 상단 강아지를 잇는 6을 선택합니다. 11 + 6 = 17
5. 모든 강아지가 연결되었으니 종료 합니다.

위 알고리즘을 통해 얻은 최소값은 17입니다.

 

5번

조합문제 입니다. 8명중 A, B를 제외하고 6명을 3명씩 팀으로 나누면 됩니다. 한쪽에 3명을 선택하면 자연스럽게 나머지 팀이 완성 됩니다.

$$ _6C_3 = \frac{6 * 5 * 4}{3 * 2 * 1}= 20 $$

따라서 정답은 20입니다.