5장. 자료구조와 알고리즘
정보처리기사 필기 개념서 · 2과목. 소프트웨어 개발 · 절 7개
이 장에서 배우는 것
5-1. 자료구조의 분류
선형 구조(일렬 1:1): 배열, 연결 리스트, 스택, 큐, 데크 / 비선형 구조: 트리(1:N), 그래프(N:M)
5-2. 트리와 이진 트리
노드의 차수(자식 수): A=2, B=2, C=1, E=1 → 트리의 차수(최댓값) = 2
5-3. 트리 순회 (Traversal)
예제 5-2. 5-2절의 트리를 전위·중위·후위로 순회한 결과는? 풀이
5-4. 수식 표기법 변환
전위식(Prefix) + A B · 중위식(Infix) A + B · 후위식(Postfix) A B + — 연산자의 위치로 구분
5-5. 정렬 (Sort)
예제 5-5. 자료 8, 3, 5, 1, 9, 2를 오름차순 정렬할 때 각 회전(Pass) 결과는? 풀이
5-6. 검색 — 이분 검색과 해싱
순차 검색: 처음부터 하나씩 비교, O(n), 정렬 불필요
5-7. 그래프
정점(Vertex)과 간선(Edge)의 집합 G = (V, E). 방향 그래프 / 무방향 그래프