정보처리기사 실기(데이터 입·출력 구현) 자료 구조

※본 내용은 스스로 공부하며 중요하다고 생각하는 부분만 정리한 내용입니다. 

---

공부 서적(시나공 정보처리기사 필기책)

시나공 정보처리기사 실기

출처: 시나공 정보처리기사 실기

저자: 김정준,강윤석,김용갑,김우경

출판사 : 길벗

---

자료 구조

---

 

자료 구조

• 기억장치의 공간 내에서 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것
• 저장공간 효율성과 실행시간 단축을 위해 사용
• 선형 구조 : 배열, 연결리스트, 연속리스트, 데크, 큐, 스택
• 비선형 구조 : 그래프, 트리

배열

• 크기와 형이 동일한 자료들이 순서대로 나열된 자료의 집합
• 정적인 자료 구조, 기억장소 추가 어렵움, 메모리 낭비 발생 가능, 반복적인 데이터 처리 작업에 적합

연속 리스트

• 연속되는 기억장소에 저장되는 자료 구조
• 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 존재해야 한다.
• 삽입·삭제시 자료의 이동 필요

연결 리스트

• 자료들을 임의 기억공간에 기억시기되 노드의 포인터부분을 이용하여 서로 연결시킨 구조
• 포인터 부분이 필요하여 기억공간 효율이 안 좋음, 접근 속도 느리고 끊어지면 다음 노드 찾기 어려움

스택

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
• LIFO(후입선출) 방식 자료 처리
• 기억 공간 없는데 삽입 되면 오버플로, 삭제할 데이터 없는데 삭제하면 언어플로 발생

큐

• 리스트의 한쪽에서는 삽입 작업을 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
• FIFO(선입선출) 방식 자료 처리, 시작과 끝을 표시하는 Front, Rear 포인터가 존재

그래프

• 정점과 간선의 두 집합으로 이루어지는 자료 구조
• 사이클이 없는 그래프를 트리

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

• 방향 그래프 : n(n-1)
• 무방향 그래프 : n(n-1)/2