dev-waterparsley

1. 기본 개념

• 자료구조(data structure): 추상화를 통해 자료의 논리적 관계를 구조화한 것
• 추상화: 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것 예) 수식, 프로그램 언어 등
• 자료(데이터)의 추상화: 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 데이터의 구조에 대해서 공통의 특징만을 뽑아 정의한 것

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

🔸자료구조의 종류와 관계

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

2. 배열

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

🔸1차원 배열

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

🔸다차원 배열

2차원 배열

다차원 배열: 두개 이상의 첨자들을 가지는 배열을 총칭함

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

🔸2차원 배열 저장 순서

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

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

🔸희소행렬(spare matrix)

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

3. 리스트

✅ 선형 리스트(linear list)

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

🔸선형 리스트의 구현1(배열을 통한 구현)

• 선형 리스트와 1차원 배열은 순차적인 구조를 가지고 있으므로 1차원 배열로 간단하게 표현할 수 있음
• 원소 삽입
  • 삽입될 위치 이후의 원소들의 순서를 그대로 유지하면서 원소를 삽입해야 함
  • 그래서 삽입할 위치에 있는 원소와 그  다음에 위치한 원소들을 모두 한 칸 씩 뒤로 이동시킴
• 원소 삭제
  • 삭제할 원소를 찾아 삭제한 후, 그 뒤에 있는 모든 원소들을 한 칸 씩 앞으로 이동시킴

🔸선형 리스트의 구현2(연결 리스트(linked list))

• 노드 간의 포인터 연결을 통해서 구현됨
• 각 노드는 적어도 두 종류의 필드(원소 값을 저장하는 데이터 필드/노드 연결을 위한 링크 필드)를 가짐
• 선형 리스트의 논리적 순서만을 지원함
• 포인터만 변경 시키면 되기 때문에 쉽게 연산 가능

🔸연결 리스트 종류

• 단일 연결 리스트(singly linked list)
  • 특정 노드의 링크 필드를 사용해서 후행 노드를 가리킴
  • 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드에 대한 접근은 헤드노드부터 새로 시작해야 함
• 이중 연결 리스트(doubly linked list)
  • 첫번째 링크는 후행 노드를 가리키고 두번째 링크는 선행 노드를 가리킴
  • 특정 노드에서 후행 노드 뿐만 아니라 선행 노드에 대한 접근을 쉽게 제공하기 위한 것
  • 메모리 추가적으로 들겠지만 연산은 조금 더 빨라짐

4. 스택과 큐

✅ 스택(Stack)

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

🔸스택의 연산

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

✅ 큐(Queue)

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

🔸큐의 연산

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

🔸큐의 만원 상태

• 만원 상태
  • 데이터가 큐에 삽입됨에 따라 rear 변수 값이 증가하다가 n-1이 되면 더 이상 데이터가 삽입될 수 없는 상태가 됨. 하지만 이 경우가 반드시 큐에 n개의 항목이 가득 차 있다는 것을 의미하는 것은 아님

=> 큐가 가득 채워진 상태를 결정하기 위한 다른 방법이 필요함