1. 자료 구조의 정의
- 저장 공간의 효율성과 실행시간의 신속성을 위해 자료를 체계적으로 구조
- 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에서 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것
- 자료 구조의 분류
2. 배열
- 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
- 정적인 자료 구조로 기억 장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생
- 첨자를 이용하여 데이터에 접근
- 반복적인 데이터 처리 작업에 적합한 구조
- 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편
- 사용한 첨자의 개수에 따라 n차원 배열이라고 부름
3. 선형 리스트
- 일정한 순서에 의해 나열된 자료 구조
- 선형 리스트의 종류
- 연속 리스트 Contiguous List
- 배열과 같이 연속되는 기억장소에 저장되는 자료 구조
- 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋음
- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입, 삭제 시 자료의 이동이 필요
- 연결 리스트 Linked List
- 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조
- 노드의 삽입, 삭제 작업이 용이
- 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있음
- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않음
- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느림
- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦
- 노드 Node : 자료를 저장하는 데이터 부분과 다른 노드를 가리키는 포인터인 링크 부분으로 구성된 기억 공간
- 포인터 Pointer : 현재의 위치에서 다음 노드의 위치를 알려주는 요소
- 프런트 포인터 : 리스트를 구성하는 최초의 노드 위치를 가리키는 요소
- 닐 포인터 : 다음 노드가 없음을 나타내는 포인터
- 연속 리스트 Contiguous List
4. 스택
- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리
- 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언터플로가 발생
- Stack의 응용 분야 : 함수 호출의 순서 제어, 인터럽트의 처리, 수식 계산 및 수식 표기법, 컴파일러를 이용한 언어 번역, 부 프로그램 호출 시 복귀 주소 저장, 서브 루틴 호출 및 복귀 주소 저장
- 스택의 주성
- TOP : 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
- Bottom : 스택의 가장 밑바닥
- Push 자료의 삽입
Top = Top + 1
If Top > M Then
Overflow
Else
X(Top) <- Item스택 포인터 (Top)를 1 증가시킴
스택 포인터가 스택의 크기보다 크면, 더이상 자료를 삽입할 수 없으므로
Overflow를 처리
그렇지 않으면
Item이 가지고 있는 값을 스택의 Top 위치에 삽입- M : 스택의 크기
- Top : 스택 포인터
- X : 스택의 이름
- Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킴
- Pop Up 자료의 삭제
If Top = 0 Then
Underflow
Else
Item <- X(Top)
Top = Top - 1스택 포인터가 0이면, 스택의 바닥이므로 더 이상 삭제할 자료가 없으므로
Underflow를 처리
그렇지 않으면
Top 위치에 있는 값을 Item으로 옮기고
스택 포인터를 1 감소시킴- Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시
5. 큐
- 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조
- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO) 방식으로 처리
- 시작과 끝을 표시하는 두 개의 포인터가 있음
- 프런트 포인터 : 삭제 작업을 할 때 사용, 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터
- 리어 포인터 : 삽입 작업을 할 때 사용, 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터
- 운영체제의 작업 스케줄링에 사용
6. 데크
- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조
- Stack과 Queue의 장점만 따서 구성한 것
- 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과, 입력은 양쪽에서 일어나고 출력은 한 곳에서만 이루어지는 출력 제한이 있음
- 입력 제한 데크 : Scroll
- 출력 제한 데크 : Shelf
7. 그래프
- 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어짐
- 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됨
- 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식,무향선분 배법 등에 응용
- 트리는 사이클이 없는 그래프
8. 인접행렬을 이용한 그래프의 표현 방법
- V₁V₁ 관계를 나타내는 행렬의 원소를 P라 할 때
- 방향 그래프
- 방향 간선이 있으면 행렬의 Pᵥ = 1
- 방향 간선이 없으면 행렬의 Pᵥ = 0
- 무방향 그래프
- V₁와 V가 서로 인접하면 Pᵥ = 1
- V₁와 V₁가 서로 인접하지 않으면 Pᵥ = 0
9. 방향 / 무방향 그래프의 최대 단선 수
- n개의 정점으로 구성
- 무방향 그래프 : n(n-1) / 2
- 방향 그래프 : n(n-1)
'Study > EIP' 카테고리의 다른 글
[정보처리기사 필기] 데이터 입출력 구현 - 030. 정렬 Sort (0) | 2025.01.23 |
---|---|
[정보처리기사 필기] 데이터 입출력 구현 - 029. 트리 Tree (0) | 2025.01.23 |
[정보처리기사 필기] 인터페이스 설계 - 027. 미들웨어 솔루션 명세 (1) | 2025.01.23 |
[정보처리기사 필기] 인터페이스 설계 - 026. 인터페이스 방법 명세화 (0) | 2025.01.23 |
[정보처리기사 필기] 인터페이스 설계 - 025. 인터페이스 요구사항 검증 (1) | 2025.01.23 |