정보처리기사 2과목 소프트웨어 개발 (선형 구조(Linear Structure) / 비선형 구조 (Non-Linear Structure))

자료 구조의 분류

선형 구조 (Linear Structure)
배열 (Array)	- 정적인 자료 구조로 기억장소의 추가가 어렵고 메모리 낭비 발생 - 첨자를 이용 - 반복적인 데이터 처리 작업에 적합한 구조 - 데이터마다 동일한 이름의 변수를 사용해 처리가 간편
스택 (Stack)	- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이뤄지는 자료 구조 - LIFO (Last In First Out) / FILO (First In Last Out) 순서 완전히 꽉 찼을 때 Overflow 상태 완전히 비어 있으면 Underflow 상태 삽입(Push)과 제거(Pop) 모두 Top라는 스택의 한쪽 끝에서만 발생 LIFO : 마지막으로 들어온 값이 처음으로 나가는 것 FILO : 처음 들어온 값이 마지막에 나가는 것
큐 (Queue)	- 리스트의 한쪽에서는 삽입 작업, 다른 한쪽에서는 삭제 작업이 이뤄지는 자료 구조 - 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 선형 자료구조
데크 (Deque)	리스트 양쪽 끝에서 삽입과 삭제 작업을 할 수 있는 자료 구조
선형 리스트 (Linear List) = 연속 리스트(순차적), 연결 리스트(순차적이지 않음)

 

 

 

 

 

비선형 구조 (Non-Linear Structure)
트리 (Tree)	정점(Node)과 선분(Branch)을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수 형태 노드(Node) : 트리의 기본 요소, 자료 항목과 다른 항목에 대한 Branch를 합친 것 Root Node : 트리의 맨 위에 있는 노드 차수(Degree) : 각 노드에서 뻗어 나온 Branch 수 (가장 차수가 많은 노드의 차수) 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수  단말 노드(Terminal Node) : 자식이 하나도 없는 노드 (Degree가 0인 노드) 자식 노드 : 어떤 노드에 연결된 다음 레벨의 노드들 부모 노드 : 어떤 노드에 연결된 이전 레벨의 노드들 형제 노드 : 동일한 부모를 갖는 노드들
그래프 (Graph)	방향그래프 - 정점을 연결하는 선에 방향이 있는 그래프 - n개의 정점으로 구성된 방향 그래프의 최대 간선 수 =n(n-1) 무방향 그래프 - 정점을 연결하는 선에 방향이 없는 그래프 - n개의 정점으로 구성된 무방향 그래프의 최대 간선 수 =n(n-1)/2