[2과목 소프트웨어 개발] 데이터 입·출력 구현 - 036. ⭐ 자료구조

• 자료의 표현과 관련된 연산
• 자료들을 조직하고 구조화 하는 것
• 모든 연산 처리 가능
• 자료구조에 따라 프로그램 실행시간이 달라짐

1. 자료구조의 분류

1) 선형 구조(Linear Structure)

• 배열(Array)
• 선형 리스트(Linear List)
  • 연속 리스트(Contiguous List)
  • 연결 리스트(Linked List)
• 스택(Stack)
• 큐(Queue)
• 데크(Deque)

2) 비선형 구조(Non-Linear Structure)

• 트리(Tree)
• 그래프(Graph)

2.  배열 (Array)

• 동일한 자료형 데이터들이 같은 크기로 나열되어 순서를 갖는 집합
• 정적 자료구조
• 기억장소 추가 어려움. 데이터 삭제 시 빈공간으로 남아있어 메모리 낭비 발생
• 첨자를 이용해 데이터 접근
• 반복적인 데이터 처리 작업에 적합한 구조
• 첨자 개수에 따라 n차원 배열이라 칭함

3. 선형 리스트 (Linear List)

• 일정한 순서에 의해 나열된 자료구조
• 배열을 이용한 연속 리스트 / 포인터를 이용한 연결 리스트

1) 연속 리스트 (Contiguour List)

• 배열과 같이 연속되는 기억장소에 저장되는 자료구조
• 저장장소 이용 효율은 밀도가 1
• 중간에 데이터 삽입 시, 연속된 빈공간이 존재해야함
• 삽입 · 삭제 시 자료 이동 필요

2) 연결 리스트 (Linked List)

• 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키되, 자료 항목 순서에 따라 노드의 포인터 부분을 이용해 서로 연결시킨 자료구조
• 삽입 · 삭제 작업에 용이
• 연속적으로 놓여있지 않아도 저장 가능
• 연결을 위한 링크(포인터) 부분이 필요하기 때문에 이용 효율이 좋지 않음
• 포인터를 찾는시간이 필요하기 때문에 접근 속도가 느림
• 중간 노드 연결이 끊어지면 다음 노드 찾기 힘듦

4. 스택 (Stack)

• 한쪽으로만 삽입 · 삭제 작업이 이루어지는 자료구조
• 후입선출(LIFO; Last In First Out)
• 스택 응용분야
  • 함수 호출 순서 제어
  • 인터럽트 처리
  • 수식 계산 및 수식 표기법
  • 컴파일러를 이용한 언어 번역
  • 부 프로그램 호출 시 복귀주소 저장
  • 서브루틴 호출 및 복귀 주소 저장
  • 재귀함수
  • DFS(Depth First Search) : 깊이 우선 탐색
• 오버플로(Overflow) : 공간이 꽉 채워져 있는 상태에서 데이터가 삽입
• 언더플로(Underflow) : 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제
• Top : 가장 마지막으로 삽입된 자료가 기억된 위치 가리킴
• Bottom : 스택의 가장 밑바닥
• Push : 자료 삽입 (Overflow 체크)
• Pop : 자료 삭제 (Underflow 체크)

5. 큐 (Queue)

• 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지는 자료구조
• 선입선출(FIFO; First In First Out)
• 시작과 끝을 표시하는 두개 포인터 존재
• Front 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터 (삭제 작업 시 사용)
• Rear 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터 (삽입 작업 시 사용)
• 큐 응용분야
  • 운영체제 작업 스케줄링
  • BFS(Breadth First Search) : 너비 우선 탐색

6. 그래프 (Graph)

• 그래프(G)는 Vertex(V)와 Edge(E:간선)의 두 집합
• 간선의 방양성 유무에 따라 방향 그래프 / 무방향 그래프 구분
• 그래프 응용분야
  • 통신망(Network)
  • 교통망
  • 이항관계
  • 연립방정식
  • 유기화학 구조식
  • 무향선분 해법
• 트리(Tree)는 사이클이 없는 그래프(Graph)

💡 방향/무방향 그래프 최대 간선 수

• 무방향 그래프 최대 간선 수 : n(n-1)/2
• 방향 그래프 최대 간선 수 : n(n-1)

 

 

📖 Reference

2023 시나공 정보처리기사 필기 : 네이버 도서