[컴퓨팅 사고력] 보물찾기

원당이는 보물지도를 가지고 보물을 찾기 위해 탐험을 떠났습니다. 보물지도에 표시된 곳에는 동굴이 있었으며 동굴의 문은 굳게 잠겨 있습니다. 이 문에는 다음과 같은 표시의 구멍이 있었고 그 아래에는 숫자가 적힌 9개의 돌이 있습니다. 문 아래에는 다음과 같이 문을 여는 방법이 적혀 있습니다. 1단계) 맨위의 원에는 첫번째 수가 적힌 돌을 놓는다. 2단계) 자신의 왼쪽 아래에는 자신의 수보다 2배가 큰 수를 놓는다. 3단계) 자신의 오른쪽 아래에는 자신의 수보다 2배 큰 수 보다 1이 더 큰 수를 놓는다. 4단계) 하위 원의 규칙도 동일한 규칙을 갖게 된다. 원당이를 위해 여러분이 돌의 위치를 찾아서 원당이가 보물을 찾도록 도와 주세요.

 

정답)

 

컴퓨팅 사고력

이 문제는 컴퓨터과학에서 사용하는 트리에 관한 문제입니다.

트리는 나무를 뒤집어 놓은 모습으로 계층구조를 표현하기에 적합한 데이터 구조입니다.

위의 문제에서 하나의 구멍을 의미하는 원은 트리에서 노드(node)라고 하며 노드와 노드를 연결하는 선을 간선(edge)라고 합니다.

또한 가장 상위단에 위치한(1번 위치)를 루트노드(Root node)라고 하며 루트노드는 한개만 있어야 합니다.

그리고 해당 노드의 하위노드를 자식노드(child node)라고 하며 자식노드가 없는 8,9,5,6,7 과 같은 노드를 단말노드(terminal node) 또는 리프노드(leaf node) 라고 합니다.

또한 임의의 노드를 선택하면 이 노드를 루트로 하는 트리구조가 되는데 이러한 구조를 서브트리(subtree)라고 하며, 루트노드에서 임의의 노드까지 방문한 노드의 수를 레벨이라고 하는데 위의 그림에서 루트를 레벨1로 시작해서 자식노드로 가면서 레벨이 하나씩 증가 됩니다.

그리고 부모 노드 밑의 자식의 노드 개수를 차수(degree)라고 하며 노드의 갯수를 최대 2개로 제한하는 트리를 이진트리라고 하는데~

이진트리는 컴퓨터과학에서 힙(heap)과 같은 자료구조나 구간트리와 같은 탐색 알고리즘에서 자주 사용되고 있는 중요한 자료구조입니다. 

 

보물 찾기 문제는 이진트리를 사용할때 배열의 위치에 기록하는 순서를 나타낸 문제입니다.

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

 

인천 서구 검단신도시 원당컴퓨터학원