[정보처리산업기사] 63강 자료 구조

1. 자료 구조의 정의

프로그램에서 사용하기 위한 자료를 기억장치의 공장 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.

• 자료의 표현과 관련된 연산이다.
• 일련의 자료들을 조직하고 구조화하는 것이다.
• 어떠한 자료 구조에서도 필요한 모든 연산들을 처리할 수 있다.
• 자료 구조에 따라 프로그램 실행시간이 달라진다.

---

2. 자료구조의 분류

• 선형 구조: 배열, 선형리스트(연속리스트, 연결리스트) 스택, 큐, 데크
• 비선형 구조: 트리, 그래프

---

3. 배열 (Array)

동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖는 집합이다.

• 배열은 첨자를 이용하여 데이터에 접근한다.
• 반복적인 데이터 처리 작업에 적합한 구조다.
• 데이터 삭제 시 메모리 낭비 발생
• 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편하다.
• 사용한 첨자의 개수에 따라 n차원 배열이라고 부른다.

4. 선형리스트 (Linear List)

선형리스트는 일정한 순서에 의해 나열된 자료 구조이다.

• 선형리스트는 배열을 이용하는 연속리스트와 포인터를 이용하는 연결 리스트로 구분된다.

연속 리스트(Contiguous List)

• 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
• 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하고, 삽입 및 삭제 시 자료의 이동이 필요하다.

연결 리스트(Linked List)

• 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
• 연결 리스트는 노드의 삽입, 삭제 작업이 용이하다.
• 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.

---

5. 스택(Stack)

리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.

• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출 방식으로 자료를 처리한다.
• 스택의 용도: 재귀 호출, 후위 표기법, 서브루틴 호출, 인터럽트 처리, 깊이 우선 탐색 등과 같이 왔던 길을 되돌아 가는 경우에 사용된다.
• 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생한다.

• 삽입 (Push) : 그림과 같이 물건을 집어 넣는 것을 Push라 합니다. Push는 스택의 구조상 마지막 데이터 위치에 삽입이 됩니다. 나중에 코딩 할 때, 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 만듭니다. 삽입을 한다면 top은 +1이 되겠죠?
• 삭제 (Pop) : Push와 반대로 물건을 빼는 것을 Pop이라 합니다. Pop도 Push와 마찬가지로 마지막 데이터 위치에서 삭제가 됩니다. Pop을 하게 된다면 top의 위치는 -1이 됩니다.
• 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.

---

6. 큐(Queue)

리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다.

• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출 방식으로 처리한다.

• Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부
• Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제
• Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인
• front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호
• rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

---

7. 그래프(Graph)

그래프 G는 점점 v와 간선 e의 집합으로 이루어진다.

• 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식에 등에 이용된다.
• 트리는 사이클이 없는 그래프 이다.
• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
  • 무방향 그래프 : 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.
    
  • 방향 그래프 : 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프입니다. 간선의 방향으로만 이동할 수 있습니다.