반응형
원당이는 보물지도를 가지고 보물을 찾기 위해 탐험을 떠났습니다.

보물지도에 표시된 곳에는 동굴이 있었으며 동굴의 문은 굳게 잠겨 있습니다.

이 문에는 다음과 같은 표시의 구멍이 있었고 그 아래에는 숫자가 적힌 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)과 같은 자료구조나 구간트리와 같은 탐색 알고리즘에서 자주 사용되고 있는 중요한 자료구조입니다. 

 

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

 

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

 

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

 

 

 

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. 핑구야날자 2021.06.08 06:40

    학생들이 정말 재미있게 문제를 풀 수 있겠네요

  2. Favicon of https://xuronghao.tistory.com BlogIcon 空空(공공) 2021.06.08 08:10 신고

    논리적인 사고를 할수 있을듯 합니다^^

  3. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2021.06.08 11:25 신고

    다소 어려워보이네요ㅎ
    즐거운 하루 보내세요.

  4. Favicon of https://lsmpkt.tistory.com BlogIcon 가족바라기 2021.06.08 20:12 신고

    사고력을 요해 흥미있을것 같습니다

+ Recent posts