[컴퓨터과학 개론] 3강 - 자료 구조

💡해당 게시글은 방송통신대학교 이관용, 정광식 교수님의 '컴퓨터과학 개론' 강의를 개인 공부 목적으로 메모하였습니다.

학습 개요

---

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

학습 목표

---

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

강의록

---

자료 구조 기본 개념

자료 구조의 개념

추상화

추상화와 구조화

• 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 개발되거나 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생기거나 소프트웨어의 유지 보수에 문제가 생기거나 할 수 있음

추상화

• 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것
  • 수식, 프로그램 언어 등

자료(데이터) 추상화

• 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 데이터의 구조에 대해서 공통의 특징만을 뽑아 정의한 것

자료의 추상화

• 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요함
  • 자료 구조(data structure)
    • 추상화를 통해 자료의 논리적 관계를 구조화한 것
• 자료가 복잡해지거나 소프트웨어가 복잡해질 수록 자료 구조의 중요성이 강조됨

자료 구조의 종류와 관계

• 미리 정의 된 자료 구조
  • 프로그래밍 언어에서 제공함
  • 프로그래밍 설계나 컴파일러 구현 단계에서 정의되어 개발자에게 제공되는 자료 구조
• 사용자 정의 자료 구조
  • 개발자가 정의하여 사용함
  • 소프트웨어 개발 중에 개발자에 의해 만들어지는 자료 구조
    • 리스트, 스택, 큐, 트리, 그래프 등

배열

배열의 개념

• 배열(array)

  

  • 동일한 자료형을 갖는 여러 개의 데이터를 동일한 변수 이름의 방에 일렬로 저장하는 자료 집합체(원소 + 인덱스)
• 원소(요소)
  • 자료 집합체에서 각 원소의 항목 값
  • 데이터
• 인덱스(첨자)
  • 자료 집합체에서 각 원소가 저장 된 방을 접근하기 위한 방 번호에 해당하는 것
  • 번호

1차원 배열에서의 주소 계산

1차원 배열

• 개념
  • 가장 간단한 형태의 배열임
  • 한 개의 인덱스(첨자)를 사용해서 원소에 직접 접근함
  • 배열의 원소들은 컴퓨터 메모리의 연속적인 기억 장소에 할당 되어 순차적으로 저장 됨
  • 배열 A의 크기를 k라고 가정하고 시작 주소를 a라고 가정하면, A[i]의 저장 주소는 a + i * k 가 됨

1차원 배열에서의 주소 계산

다차원 배열

• 2차원 배열
  • 두 개의 첨자를 가지는 배열
  • 동일한 크기의 1차원 배열을 모아 놓아 바둑판 형태로 만든 배열
  • 하나의 원소는 두 개의 첨자 i와 j의 쌍으로 구분 됨
    • A[i][j]
  • 행(row)
    • 첨자 i에 해당하는 것
  • 열(column)
    • 첨자 j에 해당하는 것

  

• 3차원 배열
  • 세 개의 첨자들을 가지는 배열

  

2차원 배열 저장 순서

• 열 우선 순서 저장

  • 첫 열에 있는 각 행의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음 열로 이동하여 각 행에 있는 원소를 차례대로 컴퓨터 메모리에 저장하는 방법

    

• 행 우선 순서 저장

  • 첫 행에 있는 각 열의 원소를 차례대로 컴퓨터 메모리에 저장하고 다음 행으로 이동하여 각 열에 있는 원소부터 차례대로 컴퓨터 메모리에 저장하는 방법

    

희소 행렬(spare matrix)

• 개념

  

  • 원소 값이 0인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬
  • 0 값을 저장하기 위해 컴퓨터 메모리의 낭비를 막고 처리의 효율성을 높이기 위해 사용 됨
  • 희소 행렬의 0인 원소는 저장하지 않고 0이 아닌 값 만을 따로 모아서 저장하는 방법
  • 0이 아닌 각 원소를 (행 번호, 열 번호, 원소 값)의 형태로 나타내면 2차원 배열로 표현 가능함

희소 행렬의 일반적인 2차원 배열 표현

희소 행렬의 효율적 표현

리스트

선형 리스트(linear list)

• 개념
  • 순서 리스트(ordered list)라고도 함
  • 1개 이상의 원소들이 순서를 가지고 구성됨
  • A = (a₁, a₂, …, aᵢ, aₙ)과 같이 표시하며 aᵢ는 i번째 원소를 나타내고 aₙ의 n은 리스트의 크기가 됨
  • ex) 요일 리스트
    • (월, 화, 수, 목, 금, 토, 일)
  • ex) 전쟁 리스트
    • ((황산벌 전투, 660), (임진왜란, 1592), (세계 1차 대전, 1914), (세계 2차 대전, 1939))

선형 리스트의 구현(배열)

• 개념
  • 선형 리스트와 1차원 배열은 순차적인 구조를 가지고 있으므로 1차원 배열로 간단하게 표현할 수 있음
• 삽입
  • 원소를 삽입하기 위해서는 삽입 될 위치 이후의 원소들의 순서를 그대로 유지하면서 원소를 삽입해야 함

  • 삽입할 위치에 있는 원소와 그 다음의 원소들은 모두 한 칸씩 뒤로 이동 시켜야 함

    

• 삭제

  • 원소 삭제의 경우에도 삭제할 원소를 찾아 삭제한 후, 그 뒤에 있는 모든 원소들을 한 칸씩 앞으로 이동 시켜야 함

    

선형 리스트의 구현(연결 리스트)

• 개념
  • 노드 간의 포인터 연결을 통해서 구현 됨
  • 각 노드는 적어도 두 종류의 필드, 원소 값을 저장하는 데이터 필드와 노드 연결을 위한 링크 필드를 가짐
  • 선형 리스트의 논리적 순서만을 지원함

  

  

연결 리스트 종류

• 단일 연결 리스트(singly linked list)
  • 특정 노드의 링크 필드를 사용해서 후행 노드를 가리킴
  • 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드에 대한 접근은 헤드 노드부터 새로 시작해야 함

  

• 이중 연결 리스트(doubly linked list)
  • 특정 노드의 첫 번째 링크는 후행 노드를 가리키고 두 번째 링크는 선행 노드를 가리킴
  • 특정 노드에서 후행 노드 뿐만 아니라 선행 노드에 대한 접근을 쉽게 제공하기 위한 것

  

스택과 큐

스택(Stack)

• 개념
  • 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료 구조
  • 가장 먼저 입력 된 데이터가 가장 나중에 제거 되는 선입 후출(FILO, First-In-Last-out) 특징을 가짐

스택의 연산

• 스택 오버플로(overflow)
  • 삽입 연산을 수행할 때 발생함
  • 스택을 위해 할당 된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
• 스택 언더플로(underflow)
  • 삭제 연산을 수행할 때 발생 함
  • 스택에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

스택의 동작

큐(Queue)

• 개념
  • 선형 리스트의 한쪽 끝에서는 데이터의 삭제만 이루어지고 다른 한쪽 끝에서는 데이터의 삽입만 이루어지는 자료 구조
  • 가장 먼저 입력 된 데이터가 가장 먼저 제거 되는 선입 선출(FIFO, First-In-First-out) 특징 가짐

큐의 연산

• 오버플로(overflow)
  • 삽입 연산을 수행할 때 발생함
  • 큐를 위해 할당 된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상
• 언더플로(underflow)
  • 삭제 연산을 수행할 때 발생함
  • 큐에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

큐의 동작

연산 후의 큐의 상태(만원 상태)

• 만원 상태
  • 데이터가 큐에 삽입 됨에 따라 rear 변수 값이 증가하다가 n-1이 되면 더 이상 데이터가 삽입될 수 없는 상태가 됨
  • 하지만, 이 경우가 반드시 큐에 n개의 항목이 가득 차 있다는 것을 의미하는 것을 아님
  • 큐가 가득 채워진 상태를 결정하기 위한 다른 방법이 필요함

정리 하기

• 자료 구조
  • 자료 사이의 논리적 관계를 컴퓨터나 프로그램이 보다 쉽게 이해하고 다룰 수 있도록 구성한 것
• 배열
  • 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수로 묶어 놓은 데이터의 집합체이며 각 원소를 구분하기 위해 인덱스와 데이터 값의 쌍으로 이루어짐
• 연결 리스트
  • 노드들을 연결하여 구성하는 것으로 한 노드는 데이터 필드와 링크 필드로 구성 됨
• 스택
  • 리스트의 한쪽 끝에서만 삽입과 삭제가 이루어지는 후입 선출(LIFO) 구조
• 큐
  • 리스트의 한쪽 끝에서는 삽입, 다른 한쪽 끝에서는 삭제가 이루어지는 선입 선출(FIFO) 구조

연습 문제

---

1. 자료들 사이의 논리적인 인접 구조에 따라 자료 구조를 구분할 때 비선형 자료 구조에 속하는 것은 어느 것인가?

   a. 트리

   • 선형 구조는 일렬의 원소의 나열(1:1 대응 관계)을 의미하며 비선형은 원소의 나열이 일렬로 이루어지지 않은 구조(1:n/n:m 대응 관계)를 의미함
     • 배열, 리스트, 큐에서 원소들은 하나의 일렬 구조를 이루고 있으며, 이를 선형 자료 구조라 함
     • 트리는 일렬 구조를 따르지 않으므로 비선형 자료 구조라 함

2. 배열에 대한 설명으로 올바른 것은?

   a. 삽입과 삭제 연산 수행 시 추가적인 연산으로 인해 오버 헤드가 발생하는 정적 구조를 갖는다.

   • 두 개 이상의 서로 다른 구조를 가진 데이터 항목을 하나의 변수 이름으로 묶고 인덱스를 사용해서 구분하는 자료 구조는 레코드 자료 구조
     • 배열의 기억 공간은 정적으로 할당이 이루어지며 선언문을 통해 정의
     • 배열에서 각 원소에 대한 접근 시간은 인덱스를 통해 접근 되기 때문에 모든 원소의 접근 시간은 동일함
     • 원소가 어느 위치에 저장 되어 있느냐에 따라 차이가 발생하는 자료 구조로는 리스트가 대표적인 예임

3. 한쪽 끝에서 모든 삽입을 수행하고 다른 쪽 끝에서 모든 삭제를 수행하는 구조의 리스트 자료 구조를 무엇이라 하는가?

   a. 큐

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

정리 하기

---

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