[정보처리기사 필기] 2과목 소프트웨어 개발 - 1

자료구조

 - 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말함

---

배열(Array)

 - 배열은 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합

 - 반복적인 데이터 처리 작업에 적합

a[0]

a[1]

a[2]

a[3]

· · ·

a[n-1]

 - 크기가 n인 1차원 배열 a

a[0][0]	a[0][1]	a[0][2]	· · ·	a[0][n-1]
a[1][0]	a[1][1]	a[1][2]	· · ·	a[1][n-1]
a[2][0]	a[1][2]	a[2][2]	· · ·	a[2][n-1]
· · ·	· · ·	· · ·	· · ·	· · ·
a[n-1][0]	a[n-1][1]	a[n-1][2]	· · ·	a[n-1][n-1]

 - 크기가 nxn인 2차원 배열 a

---

선형 리스트(Linear List)

 - 일정한 순서에 의해 나열된 자료 구조

 - 배열을 이용하는 연속리스트와 포인터를 이용하는 연결 리스트로 구분

연속 리스트(Contiguous List)

 - 연결 리스트(Linked List)

    - 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조

---

스택(Stack)

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

 - 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO Last In First Out) 방식으로 자료를 처리

 - 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로우가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생

---

큐(Queue)

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

 - 큐는 선입선출(FIFO First In First Out) 방식으로 자료를 처리

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

---

트리(Tree)

 - 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

 - 노드(Node) : 트리의 기본 요소

   - A, B, C, D, E, F, G, H, I, J, K, L, M

 - 근 노드(Root Node) : 트리의 맨 위에 있는 노드

   - A

 - 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수

   - A=3, B=2, C=1, D=3

 - 단말 노드(Terminal Node) : 자식이 하나도 없는 노드. 즉 디그리가 0인 노드

   - K, L, F, G, M, I, J

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

   - D의 자식 노드 : H, I, J

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

   - E, F의 부모 노드 : B

 - 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

   - H의 형제 노드 : I, J

 - 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

   - 노드 A나 D가 3개의 디그리를 가지므로 트리의 디그리는 3이다.

 - 전위 순회(Pre-order)

   - 루트 -> 왼쪽 -> 오른쪽(A->B->E->K->L->F->C->G->D->H->M->I->J)

 - 중위 순회(In-order)

   - 왼쪽 -> 루트 -> 오른쪽(K->E->L->B->F->A->G->C->M->H->D->I->J)

 - 후위 순회(Post-order)

   - 왼쪽 -> 오른쪽 -> 루트(K->L->E->F->B->G->C->M->H->I->J->D->A)