3강. 자료구조 (1)

by

학습개요

컴퓨터에서 다루고자 하는 데이터를 추상적인 개념으로 정의하고, 각각의 자료구조에 대한 특징과 장단점에 대해서 알아본다. 특히, 자료구조의 기본 개념과 가장 기본적인 자료구조인 배열과 리스트를 살펴본다. 그리고, 데이터에 대한 연산과 자료구조와의 정의를 통해 자료의 시간적 관계가 표현되는 스택과 큐에 대해서 알아본다.

학습목표

  1. 자료 구조와 추상화에 대해서 이해할 수 있다.
  2. 배열의 의미와 주기억장치 내에서의 저장 위치를 이해할 수 있다.
  3. 스택과 큐의 자료구조의 의미를 이해할 수 있다.

연습문제

  1. 자료들 사이의 논리적인 인접 구조에 따라 자료 구조를 구분할 때 비선형 자료 구조에 속하는 것은 어느 것인가?
    1. 배열
    2. 리스트
    3. 트리
    4. 큐
      정답 : 3

      ❒ 선형 구조는 일렬의 원소의 나열(1:1 대응 관계)을 의미하며, 비선형은 원소의 나열이 일렬로 이루어지지 않은 구조(1:n/n:m 대응 관계)를 의미합니다. 따라서 배열, 리스트, 큐에서 원소들은 하나의 일렬 구조를 이루고 있으며, 이를 선형 자료 구조라 합니다. 그리고 트리는 일렬 구조를 따르지 않으므로 비선형 자료 구조라 한다.
  2. 배열에 대한 설명으로 올바른 것은?
    1. 삽입과 삭제 연산 수행 시 추가적인 연산으로 인해 오버헤드가 발생하는 정적구조를 갖는다.
    2. 두 개 이상의 서로 다른 구조를 가진 데이터항목을 하나의 변수이름으로 묶고 인덱스를 사용해서 구분하는 자료구조이다.
    3. 배열의 기억공간은 포트란과 코볼에서처럼 항상 동적으로 할당이 이루어진다.
    4. 배열에서 각 원소에 대한 접근시간은 원소가 어느 위치에 저장되어 있느냐에 따라 차이가 발생한다.
      ❒ 두 개 이상의 서로 다른 구조를 가진 데이터항목을 하나의 변수이름으로 묶고 인덱스를 사용해서 구분하는 자료구조는 레코드 자료 구조

      ● 배열의 기억공간은 정적으로 할당이 이루어지며, 선언문을 통해 정의
      ● 배열에서 각 원소에 대한 접근시간은 인덱스를 통해 접근되기 때문에 모든 원소의 접근 시간은 동일함
      ● 원소가 어느 위치에 저장되어 있느냐에 따라 차이가 발생하는 자료구조로는 리스트가 대표적인 예임
  3. 한쪽 끝에서 모든 삽입을 수행하고 다른 쪽 끝에서 모든 삭제를 수행하는 구조의 리스트 자료 구조를 무엇이라 하는가?
    1. 큐
    2.  스택
    3. 이중 연결 리스트
    4. 배
      정답 : 1

      ● 뷔페식당에서 빈 접시들이 가지런히 쌓여져 있는 상황에서 가장 위의 접시를 가져가거나 책상 위에 쌓여진 책 위에 책을 하나 올려놓는 것과 같은 일이 이루어지는 접시 더미나 쌓여있는 책 더미를 스택이라고 합니다. 배열이란 똑같이 생긴 방을 연속해서 만들고, 그 방안에 같은 종류의 자료를 저장하는 것입니다. 마지막으로 역에서 기차표를 구입하기 위해서 줄 선 사람들은 매표창구에서 표를 사서 가고 새로 온 사람들은 줄의 맨 끝에 서게 되는 일이 발생되는 사람들의 줄을 큐라고 합니다. 따라서 답은 큐입니다.

정리하기

  1. 자료구조
    • 자료 사이의 논리적 관계를 컴퓨터나 프로그램이 보다 쉽게 이해하고 다룰 수 있도록 구성한 것
      .
  2. 배열
    • 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 묶어놓은 데이터의 집합체이며, 각 원소를 구분하기 위해 인덱스(또는 첨자)와 데이터 값의 쌍으로 이루어짐
    • 배열의 원소들은 연속적인 기억장소에 저장되어 순차적으로 저장되기 때문에 배열의 시작주소와 각 자료형의 크기를 알면 i번째 원소의 주소를 알면, 직접 접근이 가능함
    • 다차원 배열이 저장되는 방식으로는 열 우선 순서와 행 우선 순서가 있음
      .
  3. 연결 리스트
    • 노드들을 연결하여 구성하는 것으로, 한 노드는 데이터 필드와 링크 필드로 구성됨
    • 단일 연결 리스트 : 링크 필드가 하나이고, 한 방향으로만 검색이 가능함
    • 이중 연결 리스트 : 2개의 링크 필드를 사용해서 양방향(선행 노드 방향, 후행 노드 방향)의 검색이 가능함
    • 원형 연결 리스트 : 마지막 노드의 링크 필드가 첫 번째 노드에 연결되어, 한 방향이지만 전체 연결리스트를 원형으로 연결함
      .
  4. 스택
    • 리스트의 한쪽 끝에서만 삽입과 삭제가 이루어지는 후입선출(LIFO) 구조
    • pop연산과 push 연산이 가장 중요한 연산임
      .
  5. 큐
    • 리스트의 한쪽 끝에서는 삽입, 다른 한쪽 끝에서는 삭제가 이루어지는 선입선출(FIFO) 구조
    • insert 연산과 delete 연산이 가장 중요한 연산임

Leave a Comment