[정보처리기사도전기]#10 제2과목 소프트웨어 개발

Ben·2021년 7월 28일
0

정보처리기사도전기

목록 보기
11/16

제2과목 소프트웨어 개발

제1장 데이터 입출력 구현

제1절 논리 데이터저장소 확인

1. 자료구조

(1) 자료구조

1) 자료구조의 정의

[1] 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 말한다.
[2] 모든 해결을 위해 데이터 값들을 연산자들이 효율적으로 접근하여 처리할 수 있도록 체계적으로 조직하여 표현하는 것을 말한다.

2) 자료구조의 구성

⭐️
[1] 선형구조 : 데이터 항목 사이의 관계가 1:1이며, 선후 관계가 명확하게 한개의 선의 형태를 갖는 리스트 구조이다. (배열, 리스트, 스택, 큐, 데크)
[2] 비선형구조 : 데이터 항목 사이의 관계가 1:n(혹은 n:m)인 그래프적 특성을 갖는 형태이다. (트리, 그래프)

3) 배열

  • 순차적 메모리 할당 방식에다 <인덱스, 원소>쌍의 집합으로, 각 쌍은 어느 한 인덱스가 주어지면 그와 연관된 원소 값이 결정되는 대응 관계를 나타내는 것이다.

4) 연결리스트의 개요

  • 연결리스트는 다음 데이터를 포인터를 이용하여 찾아내며, 노드는 자기참조구조체(데이터필드, 포인터 필드)이다.

5) 스택 (LIFO)

  • 보통 제한된 구조로 원소의 삽입과 삭제가 한 쪽(top)에서만 이루어지는 유한 순서 리스트이다.
  • 스택의 응용 : 수식계산, 복귀주소관리, 순환식, 퀵 정렬, 깊이 우선 탐색, 이진트리 운행

6) 큐 (FIFO)

  • 한쪽 끝(rear)에서는 원소의 삽입만, 다른 쪽 끝(front)에서는 원소의 삭제만 허용하는 자료구조이다. 양 끝을 제외한 나머지 모든 위치에서의 삽입과 삭제를 허용하지 않는다.
  • 큐의 응용 : ⭐️작업스케줄링, 너비 우선 탐색, 트리의 Level 순회

7) 트리

  • 계층형 자료구조(hierarchical data structure)의 나무 형태로 노드들을 간선으로 연결한다.
  • 이진트리의 종류 : 편향 이진 트리, 포화 이진 트리(full binary tree), 완전 이진트리(complete binary tree), 이진 탐색 트리

※ 트리의 용어

[1] 노드(node) : 데이터와 링크를 통합적으로 표현한다.
[2] 노드의 차수(degree) : 한 노드가 가지고 있는 서브 트리의 수이다.
(A의 차수 : 3, B의 차수 : 2, C의 차수 : 0)
[3] 형제 (siblings) : 한 부모의 자식들이다.
(노드 G, H, I는 형제들)
[4] 트리의 차수 : 그 트리에 있는 노드의 최대차수이다.
(트리 T의 높이 : 3)
[5] 트리의 높이(height) 또는 깊이(depth) : 그 트리의 최대 레벨이다.
(트리 T의 높이 : 3)

단말트리 : 서브트리가 없는 노드

※ 트리의 순회 (운행)
[1] 전위 순회 (preorder traversal) - 전위 순회 방법의 순환식 기술
[ㄱ] 루트 노드 (root node)를 방문한다.
[ㄴ] 왼편 서브 트리(left subtree)를 전위 순회한다.
[ㄷ] 오른편 서브 트리(right subtree)를 전위 순회한다.

[2] 중위 순회 (inodrder traversal) - 중위 순회 방법의 순환식 기술
[ㄱ] 왼편 서브 트리(left subtree)를 중위 순회한다.
[ㄷ] 루트 노트(root node)를 방문한다.
[ㄷ] 오른편 서브 트리(right subtree)를 중위 순회한다.

[3] 후위 순회 (postorder traversal) - 후위 순회 방법의 순환식 기술
[ㄱ] 왼편 서브 트리(left subtree)를 후위 순회한다.
[ㄴ] 오른편 서브 트리(right subtree)를 후위 순회한다.
[ㄷ] 루트 노드(root node)FMF 방문한다.

8) 그래프

  • G = (V, E) : 그래프 G는 2개의 집합 V와 E로 구성된다.
    (V : 공백이 아닌 노드 또는 정점(vertex)의 유한집합(V만 표현 : V(G)로 표기))
    (E : 상이한 두 정점을 잇는 간선(edge)의 유한집합(E만 표현 : E(G)로 표기))
  • 그래프 순회 : 깊이 우선탐색(DFS : Depth First Search), 너비 우선 탐색(BFS : Breadth First Search)

깊이우선탐색 : 스택
너비우선탐색 : 큐

profile
프로그램을 만드는것을 업으로 삼은 사람입니다

0개의 댓글