728x90
SMALL
📘 1. 그래프(Graph)
- **노드(정점)와 간선(연결)**으로 구성된 자료구조
- 트리보다 일반적인 연결 구조
- 방향 그래프 / 무방향 그래프, 가중치 그래프로 구분
구성 요소설명
| 정점(Vertex) | 데이터를 담는 점 |
| 간선(Edge) | 정점 간 연결선 |
| 인접(Adjacent) | 연결된 두 정점 관계 |
그래프 표현 방법
- 인접 행렬: 2차원 배열 사용 (공간 낭비 많음)
- 인접 리스트: 연결 리스트 사용 (공간 효율 ↑)
📌 기출 포인트:
- 인접 행렬 vs 인접 리스트 비교
- 방향/무방향 구분 문제 자주 출제
📘 2. 해시(Hash)
- 데이터를 고정된 길이의 값으로 변환하는 방식
- 빠른 탐색, 삽입, 삭제에 유리
구성 요소설명
| 해시 함수(Hash Function) | 키 → 해시 주소로 변환 |
| 해시 테이블 | 실제 데이터 저장소 |
| 충돌(Collision) | 서로 다른 키가 같은 주소로 변환될 때 발생 |
충돌 해결 방법
- 체이닝: 같은 해시 주소에 연결리스트로 저장
- 오픈 주소법: 비어있는 다음 주소에 저장
📌 기출 포인트:
- 충돌(Collision) 개념 꼭 암기
- 충돌 해결 방법 종류와 예시
📘 3. 연결 리스트(Linked List)
- 각 노드가 데이터 + 다음 노드의 주소를 가지는 구조
- 동적 메모리 할당이 가능, 삽입/삭제가 용이
종류설명
| 단일 연결 리스트 | 다음 노드로만 연결 |
| 이중 연결 리스트 | 이전/다음 노드로 양방향 연결 |
| 원형 리스트 | 마지막 노드가 첫 번째 노드와 연결됨 |
📌 배열보다 삽입/삭제가 빠르지만, 탐색은 느림
📘 4. 트리(Tree) 심화
- 이진 탐색 트리(BST) 이외에도 다양한 트리 구조 존재
트리 종류설명
| 힙(Heap) | 완전 이진 트리 기반, 우선순위 큐 구현에 사용 |
| B-트리 | 균형 잡힌 다진 트리, 데이터베이스에서 사용 |
| AVL 트리 | 높이 균형 유지 트리, BST의 성능 개선형 |
📌 기출 포인트:
- 힙 정렬은 최소 힙 또는 최대 힙을 이용
- B-트리/AVL 트리 → 균형 잡힌 트리의 필요성 관련 문제
📘 5. 기출 포인트 요약
- 그래프는 정점 + 간선, 표현 방식(행렬/리스트) 기억
- 해시는 충돌 해결 방식에 집중
- 연결 리스트는 삽입/삭제 유리, 탐색 불리
- 트리 심화 → 힙, AVL, B-트리 기본 구조 암기 필수
📝 기출 예시 문제
다음 중 해시 충돌 해결 방법으로 옳은 것은?
① 다중 스택 사용
② 오픈 주소법
③ 이진 탐색
④ 퀵 정렬✅ 정답: ②
728x90
LIST
'정보처리기사' 카테고리의 다른 글
| ✅ [32일차] 운영체제 기초 – 프로세스, 스레드, CPU 스케줄링 완전 정리 (0) | 2025.05.30 |
|---|---|
| ✅ [31일차] 알고리즘 기초 – 재귀, 분할 정복, 탐욕, 동적 계획법, 백트래킹 (0) | 2025.05.29 |
| ✅ [29일차] 자료구조 기초 – 정렬, 탐색, 스택, 큐, 트리 정리 (0) | 2025.05.26 |
| ✅ [28일차] 전자계산기 구조 – 정보 표현 방식(문자, 음성, 영상) (0) | 2025.05.25 |
| ✅ [27일차] 전자계산기 구조 – 입출력 제어 방식(DMA, 인터럽트, 프로그램 방식) (0) | 2025.05.25 |