36. 자료구조 (⭐️⭐️⭐️⭐️)
1) 정의
효율적 프로그램 고려사항 1순위 - 저장공간의 효율성, 실행시간의 신속성
자료구조는 데이터를 기억장치 공간 내에 효율적으로 저장하고 자료간 처리방법을 연구 분석하는 것
- 어떠한 자료구조에서도 필요한 모든 연산 처리가 가능하나,
- 처리할 문제에 어울리는 적절한 자료구조 선택해야 한다.
2) 분류
- 선형구조 - 배열, 선형리스트, 스택, 큐, 데크
- 비선형 구조 - 트리, 그래프
3) 배열(Array)
동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖는 집합
-
정적 자료구조로 기억장소 추가 어려움
-
데이터 삭제시 껍데기 빈공간으로 남아있어 메모리 낭비 발생
-
배열 첨자 (subscript)를 통해 인덱싱
-
사용되는 첨자의 개수에 따라 n차원 배열이라 부름
-
데이터마다 동일한 변수 사용하여 처리가 간편
다음의 경우에서 a는 변수, [숫자]는 첨자
- a[0], a[1], a[2] -> 1차원 배열, 0~n-1까지 총 n개의 기억장소 존재
- a[0][0], a[0][1], a[0][2]
a[1][0], a[1][1], a[1][2] -> 2차원 배열, 총 n*n 개의 기억장소 존재
-
반복적 데이터 처리작업에 적합
4) 선형 리스트 (Linear List)
일정한 순서에 의해 나열된 자료구조
👉🏻 배열 이용하는 연속 리스트와 포인터 이용하는 연결 리스트로 구분
✓ 포인터: 현재의 위치에서 다음 노드 위치를 알려주는 요소
✓ 노드: 데이터와 링크(포인터) 부분으로 구성된 기억공간
연속 리스트
- 배열과 같이 연속되는 기억장소에 저장되는 자료구조
- 이용 효율 밀도가 1로서 가장 좋다
- 데이터를 중간에 삽입, 삭제 시 자료의 이동이 필요함
연결 리스트
- 자료를 반드시 연속적 배열하지는 않고 임의의 기억공간에 기억시키되, 순서에 따라 노드 포인터 부분 이용해 서로 연결시킨 자료구조
- 노드의 삽입, 삭제 작업 용이
- 기억공간이 연속적으로 놓여있지 않아도 저장 가능
- 순차리스트에 비해 기억공간 이용효율이 좋지는 않음
- 포인터 찾는 시간 필요하기 때문에 접근속도 느림
- 중간 노드연결 끊어지면 다음노드 찾기 힘듦
5) 스택 (Stack)
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조
- LIFO 방식의 자료처리
- 용도: 재귀 호출, 후위(Postfix)표기법, 서브로틴 호출, 인터럽트 처리, 깊이 우선 탐색 등과 같이 왔던 길을 되돌아가는 경우에 사용
- 스택 여유공간이 없는 상태에서 데이터 삽입시 오버플로(Overflow)발생, 데이터가 없는데 삭제 시 언더플로(Underflow)발생
- Top: 스택에 가장 마지막으로 삽입된 자료가 기억된 위치
- Bottom: 스택의 가장 밑바닥
- 자료의 삽입 (Push)
Top = Top + 1 //Top: 스택 포인터
If Top > M Then
Overflow
Else
X(Top) <- Item- 자료의 삭제 (Pop up)
If Top = 0 Then
Underflow
Else
Item <- X(Top)
Top = Top-1
//Stack에서 자료 삭제시킬 때 삭제 자료 있는지 없는지부터 확인6) 큐(Queue)
리스트의 한쪽에서는 삽입, 한쪽에서는 삭제
- 선입선출(FIFO) 방식의 자료처리
- 포인터 두개 (F, R)
- F 포인터: 가장 먼저 삽입된 자료의 위치, 삭제작업시 사용
- R 포인터: 가장 마지막에 삽입된 자료의 위치, 삽입작업시 사용
- 운영체제의 작업 스케줄링에 사용
7) 그래프(Graph)
그래프 G는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어짐
- 방향성 유무에 따라 방향그래프, 무방향 그래프로 구분
- 통신망, 교통망, 이항관계, 연립방정식, 유기화학구조식 등에 응용
- 트리(Tree)는 사이클이 없는 그래프
참고도서 📚
2022 시나공 정보처리기사 필기
정체되지 않는 성장