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

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

1번

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

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

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

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

2022년도 정보올림피아드 1차대회 필기 초등부 6번부터 10번까지 문제 풀이 입니다. 이전 문제는 아래 링크 확인 바랍니다. 2024.04.03 - [알고리즘 설명] - 2022년 정보올림피아드 필기 초등부(1 ~ 5) 6번

davincicoding.co.kr

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

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

davincicoding.co.kr

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

01. 크루스칼 알고리즘

# 크루스칼 알고리즘 크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보겠습니다. 이 알고리즘은 모든 정점을 포함하고, 사이클이 없는 연결 선을 그렸을 때, 가중치…

wikidocs.net

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

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

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

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

따라서 정답은 20입니다.