4강. 자료구조 (2)

by

학습개요

『컴퓨터과학개론』의 네 번째 강의로서, 컴퓨터 프로그래밍을 시작하면서 가장 기본이 되는 내용인 자료구조를 살펴본다. 비선형 자료구조인 트리와 그래프에 대해 알아보고, 그래프와 트리의 순회 방법과 표현 방법에 대해서 학습한다. 트리는 계층 구조를 표현하기에 적당하고, 그래프는 현실세계 네트워크나 네비게이션의 목적지와 출발지를 표현하고 계산하는 데 가장 많이 사용되는 자료구조이다.

학습목표

  1. 트리와 그래프와 같은 자료구조에 대해서 이해할 수 있다.
  2. 트리의 노드를 순회할 수 있는 방법에 대해서 이해할 수 있다.
  3. 그래프의 노드를 순회하는 방법에 대해서 이해할 수 있다.

연습문제

  1. 트리의 루트 노드에서 리프 노드에 이르는 가장 긴 경로에 존재하는 노드의 개수를 무엇이라고 하는가?
    1. 가지 수
    2. 차수
    3. 레벨
    4. 깊이

      정답 : 4

      ● 노드를 연결하는 것을 가지(branch, edge)라고 하며, 각 노드에 있는 가지의 수를 차수(degree)라고 합니다. 따라서 두 개는 답이 될 수 없습니다. 마지막으로 루트 노드로부터의 거리(가지의 개수)를 레벨이라고 합니다. 당연히 레벨은 하나의 트리에서도 다를 수 있습니다. 레벨에서 가장 큰 값을 트리의 깊이라고 합니다.
  2. 이진트리에 대한 설명으로 올바른 것은?
    1. 각 노드의 차수 중에서 최소 차수가 2이상이다.
    2. 노드가 하나도 없는 공백트리도 이진트리이다.
    3. 루트레벨이 0이고 깊이가 2인 이진트리의 최대노드의 수는 8개이다.
    4. 한 노드에 대한 서브트리의 순서는 대칭적인 관계를 갖기 때문에 중요하지 않다.
      정답 : 2

      ● 이진트리의 최대 차수는 2입니다. 두 개까지의 자식노드를 가질 수 있습니다. 깊이가 2인 이진트리는 레벨 0에서 루트 노드 하나를 가지며, 레벨 1에서는 루트 노드의 자식 노드 2개를 가집니다. 그리고 레벨 2에서 4개의 노드를 가집니다. 따라서 최대 7개의 노드를 가질 수 있습니다. 서브 트리는 대칭적인 관계를 가지는 것이 아닙니다.
  3. 그래프 관련 용어에 대한 설명으로 틀린 것은?
    1. 간선이 두 정점을 직접적으로 연결시키고 있을 때 두 정점을 인접한 정점이라고 한다.
    2. 각 정점과 인접해 있는 정점들의 나열을 사이클이라고 한다.
    3. 두 정점 사이에 경로가 존재하는 경우를 연결되었다고 한다.
    4. 방향 그래프에서 적어도 두 정점이 연결되어 있지 않을 때 약하게 연결되었다고 한다.
      => 방향 그래프에서 적어도 두 정점사이에 어느 한쪽으로만 경로가 존재할 때, 약하게 연결되었다고 한다.

      정답 : 2

      ● 세 개 이상의 정점을 가진 경로 중에서 시작 정점과 끝 정점이 같은 경로를 사이클(cycle)이라고 합니다. 따라서 2번이 틀렸습니다.

정리하기

  1. 트리 : 노드와 가지로 구성되어 나무 뿌리 모양의 데이터의 계층 관계를 나타내는 자료구조
    • 트리(tree) : 데이터간의 관계를 나타내는 비선형 자료구조로서 노드(node)라고 불리는 부분과 노드를 연결하는 가지(branch, edge)로 구분됨
    • 잎 노드(leaf node) : 단말 노드(terminal node)라고도 하며, 노드의 차수가 0인 노드
    • 내부 노드(internal node) : 비단말 노드(non-terminal node)라고도 하며, 루트 노드와 단말 노드를 제외한 나머지 노드
    • 이진트리 (binary tree) : 트리 중에서 차수가 2인 트리를 의미하고, 모든 노드의 차수는 최대 2를 넘지 않으며 모든 노드는 최대 2개의 서브 트리를 가짐
    • 이진트리의 순회 : 일정한 순서에 따라 트리에 있는 각 노드를 한 번씩 방문하는 것
    • 포화이진트리 : 이진트리 중에서도 깊이가 k인 이진트리가 가질 수 있는 최대 노드의 개수(-1)를 가진 이진트리
    • 완전이진트리 : 총 노드의 개수가 (-1)을 초과하지 않으면서 포화이진트리의 번호와 일치하는 이진트리
    • 경사 이진트리 : 한쪽 방향으로 치우친 트리
      .
  2. 트리 순회 방법으로 전위 순회, 중위 순회, 후위 순회가 있음
    .
  3. 그래프 : 정점들의 유한 집합과 정점들의 쌍을 연결하는 간선의 유한집합
    • 그래프(graph) : 정점(vertex)들의 유한 집합 V와 두 개의 정점을 연결하는 간선(edge)들의 유한 집합 E로 정의되며, G=(V,E)로 표시됨
    • 무방향 그래프(undirected graph) : 간선이 방향성이 없는 간선으로 연결된 그래프
    • 방향 그래프(directed graph, digraph) : 두 정점을 연결하는 간선이 방향성을 가지는 간선으로 연결된 그래프
    • 그래프의 표현 : 인접행렬, 인접 리스트
    • 그래프 순회 방식 : 깊이 우선 탐색, 너비우선 탐색

Leave a Comment