[정보처리기사] 자료구조 (배열/선형리스트/스택/큐/데크/트리/그래프)

NCS 기반으로 개편된 2020 정보처리기사의 경우 자료구조 파트가 소프트웨어 개발 과목으로 넘어왔다. 확실히 삭제된 부분도 많고, 새로 추가된 부분도 많고 전체적인 구조도 많이 바뀐 것 같다. 

 

 

자료구조의 분류

- 선형 구조: 배열, 선형리스트(연속리스트, 연결리스트) 스택, 큐, 데크

- 비선형 구조: 트리, 그래프

 

배열 (Array)

- 동일한 자료형의 데이터들이 같은 크기로 나열됨

- 순서를 갖고 있는 집합

- 기억장소의 추가가 어려움

- 데이터 삭제 시 메모리 낭비 발생

 

연결리스트 (Linear List)

- 노드의 포인터를 이용해 서로 연결시킨 자료 구조

- 노드의 삽입, 삭제 작업이 용이함

- 링크가 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋치 않음

- 포인터를 찾아야해서 접근 속도가 느림

 

스택 (Stack)

- 리스트의 한쪽 끝으로만 삽입,삭제 작업이 이루어지는 자료 구조

- 가장 나중에 삽입된 자료가 먼저 삭제되는 후입선출(LIFO)

 

큐 (Queue)

- 한쪽에서는 삽입 작업이 이루어지고 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조

- 가장 먼저 삽입된 자료가 먼저 삭제되는 선입선출(FIFO)

- 운영체제의 작업 스케줄링에 사용함

 

데크 (Deque)

- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생 가능

- 스택과 큐의 장점만 따서 구성됨

 

트리 (Tree)

- 노드와 가지를 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

 

 

- 노드: 트리의 기본 요소

- 루트 노드: 트리의 맨 위에 있는 노드

- 디그리(차수): 각 노드에서 뻗어나온 가지의 수 (A=3, B=2)

- 단말 노드(잎노드): 자식이 하나도 없는 노드, 디그리가 0

- 비단말 노드: 자식이 하나라도 있는 노드

- 자식 노드: 어떤 노드에 연결된 다음 레벨의 노드들

- 부모 노드: 어떤 노드에 연결된 이전 레벨의 노드들

- 형제 노드: 동일한 부모를 갖는 노드들