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

✅ 1. 기본 개념

(1) 자료구조의 개념

[ 추상화 ]

• 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것을 의미함.
• 다양한 객체의 예시는 버스가 될 수 있고, 버스에는 광역, 고속, 시외 등 다양한 종류의 버스가 존재하지만 공통적인 개념을 뽑아서 이미지화를 통해 추상화를 시킬 수 있음. 즉, "버스 타러 가자" 만으로도 이해가 충분할 수 있음.
• 예를 들면 수식, 프로그램 언어 등이 있음

[ 자료(데이터) 추상화 ]

• 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 데이터의 구조에 대해서 공통의 특징만 뽑아 정의 한 것을 의미함.
• 자료구조는 종류가 다양하다. 즉, 배열만 봐도 여러 배열이 존재 할 수 있기 때문에 배열 자체의 공통적인 특징을 뽑아서 자료 를 추상화 할 수 있음. 이유는 의사소통을 하기 위해서 공통으로 이해시키기 위해 추상화를 하는 것임.
• 즉, 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요함
• 자료구조: 추상화를 통해 자료의 논리적 관계를 구조화한 것을 의미함.

(2) 자료구조의 종류와 관계

[ 미리 정의 된 자료구조 ]

• 프로그래밍 언어에서 미리 만들어서 제공을 해줌
• 프로그래밍 설계나 컴파일러 구현 단계에서 정의되어 개발자에게 제공되는 자료구조를 의미함.

[ 사용자 정의 자료구조 ]

• 개발자가 정의하여 사용함
• 소프트웨어 개발 중에 개발자에 의해 만들어지는 자료구조를 의미(리스트, 스택, 큐, 트리, 그래프 등)

---

✅ 2. 배열

• 배열은 변수 하나와 인덱스(첨자) 로 이루어진 자료구조로 볼 수 있다.
• 동일한 자료형을 갖는 여러 개의 데이터를 동일한 변수 이름의 방에 일렬로 저장하는 자료 집합체이다. ( 원소 + 인덱스 )
• 원소: 자료 집찹헤에서 각 원소의 항목값을 의미함. 즉, 데이터
• 인덱스: 자료 집합체에서 각 원소가 저장된 방을 접근하기 위한 방 번호에 해당하는 번호로 볼 수 있음.

• 왼쪽 컴퓨터는 메모리 주소를 의미하며, 일반적으로 물리주소라고 말함.
• 메모리에는 실제로 메모리에 주소가 넘버링 되어잇고 그걸 가지고 데이터 접근을 하게 됨.
• 오른쪽은 논리 주소이며, 이러한 논리 주소는 물리 주소와 1:1로 매칭이 되어 메모리에서도 배열의 연속적인 특징이 동일하게 적용이 되어, 메모리에 연속적으로 저장이 된다. 즉, 원시적인 이유가 물리적인 주소와 1:1로 매칭이 되기 때문임.

(1) 1차원 배열

• 가장 간단한 형태의 배열이며, 한 개의 인덱스를 사용해서 원소에 직접 접근을 함.
• 배열의 원소들은 컴퓨터 메모리의 연속적인 기억장소에 할당되어 순차적으로 저장이 된다.

(2) 2차원 배열

• 두 개의 첨자를 가지는 배열이며, 동일한 크기의 1차원 배열을 모아 놓고, 바둑판 형태로 만든 배열이다.
• 하나의 원소는 두 개의 첨자 i와 j의 쌍으로 구분이 된다. A[i][j]

[ 열 우선 순서 저장 ]

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

[ 행 우선 순서 저장 ]

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

(3) 3차원 배열

• 3개의 첨자들을 가지는 배열이다.

(4) 희소 행렬

• 원소 값이 0 인 원소가 그렇지 않은 원소보다 상대적으로 많은 행렬을 의미함.

• 사진과 같이 희소 행렬은 2차원 배열로 표현이 가능하다. 즉, 메모리셀에 데이터를 삽입하는 구조를 만들 수 있음.
• 이렇게 저장을 하게 되면, 문제는 0과 같이 의미 없는 값이 메모리 공간을 너무 많이 차지하게 됨.

• 희소 행렬 즉, 0이 과반수를 넘어가는 경우 위의 배열처럼 저장을 하게 되면 메모리 효율이 올라 갈 수 있음.
• 즉, 메모리 낭비를 막을 수 있게 됨.
• 자료구조를 어떻게 만드느냐에 따라서 메모리를 절약 할 수 있음을 나타내는 하나의 사례로 볼 수 있음.
• 자료구조를 잘 이용하면 프로그래밍 컴퓨팅 리소스를 잘 활용 할 수 있게 됨. 똑같은 데이터를 달리 표현도 가능해짐.

---

✅ 3. 리스트

• 순서 리스트 라고도 하며, 1개 이상의 원소들이 순서를 가지고 구성이 되어있음.
• 단순히 순서가 있는 데이터의 나열이라고 보면 된다.
• 이러한 리스트를 어떤 방식으로 구현하느냐에 따라 방식이 달라지지만 순서 리스트라는 점은 변하지 않음.
• 리스트라고 볼 수 있는 최소 필수 연산은 삽입, 삭제, 접근, 길이 확인 정도가 있음.

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

• 선형 리스트와 1차원 배열은 순차적인 구조를 가지고 있으므로 1차원 배열로 간단하게 표현할 수 있음.

• 하지만, 원소를 삽입하기 위해서는 삽입될 위치 이후의 원소들의 순서를 그대로 유지하면서 원소를 삽입해야 함.
• 삽입할 위치에 있는 원소와 그 다음의 원소들을 모두 한 칸 씩 뒤로 이동시켜야 함.
• 또한, 원소를 삭제하는 경우에도 삭제할 원소를 찾아 삭제한 후, 그 뒤에 있는 모든 원소들을 한 칸 씩 앞으로 이동시켜야함.
• 삽입과 삭제가 일어나면 배열을 활용 했기에 물리적인 순서에도 반영이 되어야 함.
• 하지만, 배열의 방식은 데이터 이동이 너무 잦아져 성능적으로 떨어지게 되며, 비효율적이게 됨.

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

• 배열의 방식과 다르게 각 노드마다 링크를 넣어 포인터 연결을 통해서 삽입과 삭제의 대한 효율성을 가지게 됨.
• 각 노드는 적어도 두 종류의 필드, 원소 값을 저장하는 데이터 필드와 노드 연결을 위한 링크 필드를 가진다.
• 선형 리스트의 논리적 순서만을 지원함. 즉, 각 노드 간의 포인터 연결을 통해서 구현된 리스트라고 보면 됨.

• 한 노드에 데이터와 링크를 같이 저장하여 노드의 링크는 다음 노드의 메모리 주소를 가지고 있음.

[ 단일 연결 리스트 ]

• 특정 노드의 링크 필드를 사용해서 후행 노드를 가리킴
• 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드에 대한 접근은 헤드 노드부터 새로 시작해야 한다는 단점이있음.
• 쉽게말해, 한 방향으로 링크가 되어있다고 보면 됨.

[ 이중 연결 리스트 ]

• 단일 연결 리스트의 단점을 보완하고자 나온듯
• 특정 노드의 첫번째 링크는 후행 노드를 가리키고 두번째 링크는 선행 노드를 가리킴
• 특정 노드에서 후행 노드 뿐만 아니라 선행 노드에 대한 접근을 쉽게 제공하기 위한 것임.
• 쉽게말해, 양 방향으로 링크가 되어있다고 보면 됨.

(3) 정리

• 정리하면, 배열 방식은 삽입과 삭제에 데이터 이동이 필수고 연결 리스트 방식은 삽입과 삭제에 데이터 이동이 필요없음.
• 즉, 어떤 경우에 어떤 자료구조를 쓸 것인가에 대한 결정을 위한 내용이라 보면 됨.

---

✅ 4. 스택과 큐

(1) 스택

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

[ 스택 오버플로 ]

• 삽입 연산을 수행할 때 발생하며, 스택을 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상임

[ 스택 언더플로 ]

• 삭제 연산을 수행할 때 발생하며, 스택에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상

[ 스택의 동작 과정 ]

(2) 큐

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

[ 큐 오버플로 ]

• 삽입 연산을 수행할 때 발생하며, 큐를 위해 할당된 저장 공간을 초과해서 더 이상 데이터를 삽입할 수 없는 현상이다.

[ 큐 언더플로 ]

• 삭제 연산을 수행할 때 발생하며, 큐에 데이터가 존재하지 않으면 삭제가 일어나지 않는 현상이다.

[ 큐의 동작 원리 ]

[ 큐의 만원 상태 ]

• 배열로 구현된 큐에서는 데이터가 큐에 삽입됨에 따라 rear 변수 값이 증가하다가 n-1이 되면 더 이상 데이터가 삽입될 수 없는 상태가 됨. 즉, 배열의 공간이 할당 받은 만큼의 한정되어 있음.
• 그리고 배열의 길이가 길다고 해도 front 가 앞으로 이동하면서 앞의 빈 배열의 공간이 메모리 낭비로 직결 될 수 있음.
• 해결하기 위해서 연결 리스트 또는 원형 큐 방식을 보통 사용한다?