본 게시물은 자료구조 총 정리로 각 주차별 핵심 내용을 다루고 있습니다. 복습하거나 놓친 부분이 있는지, 어떤 부분은 놓쳤는지 해당 부분만 빠르게 점검하는 용도로 활용하시면 좋을 거 같습니다. 이를 위해 본 게시글은 핵심만 정리하고, 각 주차별로 세부 내용을 볼 수 있게 링크를 남겨 놓겠습니다.
1~7주차까지 중간고사, 9~14주차까지 기말고사 범위입니다. 8주차와 15주차는 각각 중간고사와 기말고사이기에 포함되지 않았습니다.
목차는 1. 각 주차별 핵심 요점 2. 각 주차별 반드시 알아야 하는 내용 3. 각 주차별 핵심 요약입니다. 링크는 3번째 각 주차별 핵심 요약쪽에 있습니다.
1. 각 주차별 핵심 요점
| 주차 | 주제 | 핵심 요점 |
|---|---|---|
| 1주차 | 자료구조 개요 | 자료형, ADT, 알고리즘 성능분석, Big-O, 순환과 반복 |
| 2주차 | 배열과 리스트 | 배열과 연결리스트 구조 및 차이, 리스트 ADT |
| 3주차 | 스택 | LIFO, push/pop/peek, 괄호검사, 후위표기 계산 |
| 4주차 | 큐 | FIFO, enqueue/dequeue, 원형큐, 덱, 우선순위 큐 |
| 5주차 | 재귀와 분할정복 | 재귀 함수, 합병정렬, 이진탐색 |
| 6주차 | 정렬 알고리즘 | 버블/선택/삽입/퀵/합병/힙 정렬, 시간복잡도 |
| 7주차 | 탐색 알고리즘 | 순차/이진 탐색, 조건 및 복잡도 비교 |
| 9주차 | 트리 | 트리 기본구조, 이진트리, 순회방식(전중후위) |
| 10주차 | 이진 탐색 트리 | BST 삽입/삭제/탐색, 시간복잡도 |
| 11주차 | AVL 트리 | 균형 인수 ±1, LL/LR/RR/RL 회전 |
| 12주차 | 힙과 우선순위 큐 | 완전 이진트리, Heap 정렬, Min/Max Heap |
| 13주차 | 그래프 | 정점/간선, 인접행렬/리스트, DFS/BFS |
| 14주차 | 최단 경로/MST | Dijkstra, Kruskal, Prim, Union-Find |
2. 각 주차별 반드시 알아야 하는 내용
1주차: 자료구조 개요
- 자료구조(Data Structure): 데이터를 효율적으로 저장, 처리, 관리하는 방법
- 자료형(Data Type): 기본형(정수, 실수 등)과 참조형(클래스 등)
- 추상 자료형(ADT): List, Stack, Queue 등 인터페이스 정의
- 알고리즘 성능: 시간복잡도와 공간복잡도, Big-O 표기법
2주차: 배열과 리스트
- 배열: 고정 크기, 연속 메모리, 인덱스 접근 빠름
- 리스트: 연결리스트(단일, 이중, 원형), 삽입/삭제가 빠름
- 배열 vs 연결리스트 장단점 비교
3주차: 스택 (Stack)
- LIFO 구조, 삽입(Push)/삭제(Pop)
- 주요 연산: isEmpty, isFull, peek
- 응용: 괄호 검사, 후위 표기법 계산, 함수 호출 스택 등
4주차: 큐 (Queue)
- FIFO 구조, 삽입(Enqueue)/삭제(Dequeue)
- 선형 큐 vs 원형 큐
- 덱(Deque), 우선순위 큐(Priority Queue)
5주차: 재귀와 분할 정복
- 재귀 호출과 스택의 관계
- 분할정복 예시: 합병 정렬(Merge Sort), 이진 탐색(Binary Search)
- 재귀의 장단점
6주차: 정렬 알고리즘
- 버블 정렬, 선택 정렬, 삽입 정렬 (단순 O(n²))
- 퀵 정렬, 합병 정렬, 힙 정렬 (효율적 O(n log n))
- 안정성(Stable Sort) 개념
7주차: 탐색 알고리즘
- 순차 탐색(Linear Search), 이진 탐색(Binary Search)
- 이진 탐색 조건: 정렬된 배열
- 시간복잡도: O(n), O(log n)
9주차: 트리 기초
- 트리 구조: 루트, 부모/자식 노드, 리프 노드
- 이진 트리(Binary Tree), 순회: 전위/중위/후위
- 포화/완전/불완전 이진트리 정의
10주차: 이진 탐색 트리(BST)
- 왼쪽 < 루트 < 오른쪽 조건 만족
- 탐색, 삽입, 삭제 알고리즘
- 시간복잡도 평균 O(log n), 최악 O(n)
11주차: AVL 트리 (균형 이진탐색트리)
- 균형 인수(Balance Factor) = 왼쪽 높이 - 오른쪽 높이 (±1)
- LL, RR, LR, RL 회전을 통해 균형 유지
- 삽입/삭제 시 자동 균형 조정
12주차: 힙과 우선순위 큐
- 최대 힙(Max-Heap), 최소 힙(Min-Heap)
- 완전 이진 트리 기반
- 힙 정렬(Heap Sort), 시간복잡도 O(n log n)
13주차: 그래프 기초
- 정점(Vertex)과 간선(Edge), 방향성 유무
- 인접 행렬 / 인접 리스트 표현
- DFS, BFS 알고리즘
14주차: 최단 경로 및 최소 신장 트리(MST)
- Dijkstra 알고리즘: 음의 가중치 X
- Kruskal, Prim 알고리즘: MST 구성
- Union-Find 알고리즘 활용 (Kruskal)
3. 각 주차별 핵심 요약
1주차 - 1주차 요약본
항목 - 요점 정리
| 자료구조 | 데이터를 효율적으로 저장하고 사용하는 방식 |
| 알고리즘 | 문제를 해결하는 절차, 명확하고 유한해야 함 |
| ADT | 구현은 숨기고 기능만 정의한 구조 |
| 시간복잡도 | 알고리즘의 효율성을 수치적으로 표현 (O(n), O(n²) 등) |
| 재귀 vs 반복 | 대부분의 재귀는 반복으로 변경 가능, 반복이 빠름 |
2주차
항목 - 핵심 내용 요약
| 파이썬 자료형 | int, float, str, list, tuple, dict, set 등 |
| 컬렉션 사용법 | 리스트, 튜플, 집합, 딕셔너리 |
| 제어문 | if, elif, else, for, while |
| 함수 정의 | 기본 인자, 반환값, 스코프 구분 |
| 클래스 개념 | 생성자, 멤버변수, 연산자 중복, 상속, 재정의 등 |
3주차
항목 - 핵심 내용 요약
| 리스트 구조 | 순서 있음, 중복 허용, ADT 기반 다양한 연산 정의 |
| 구현 방식 비교 | 배열 vs 연결 리스트 (접근/삽입 효율 차이) |
| 리스트 성능 | append는 빠름, insert/pop은 중간 위치일 때 느림 |
| 집합의 특성 | 순서 없음, 중복 없음, 연산 중심 구조 |
| 집합 ADT | 삽입, 삭제, 포함 검사, 합/교/차집합 제공 |
4주차
항목 - 요약 설명
| 스택 구조 | 후입선출(LIFO), top에서 삽입/삭제 |
| 스택 연산 | push, pop, peek, isEmpty, size, clear |
| 괄호 검사 | 짝 검사 조건 3가지, 스택으로 괄호 순서 체크 |
| 후위 수식 | 피연산자 출력, 연산자는 우선순위 고려하여 스택 |
| 중위→후위 변환 | 연산자 우선순위와 괄호 처리 필요 |
| DFS 응용 | 그래프 탐색 시 스택을 활용하는 대표적 알고리즘 |
5주차
항목 - 핵심 요약 설명
| 큐(Queue) | FIFO 구조, front에서 꺼내고 rear에 삽입 |
| 선형 큐 문제 | 삭제 시 O(n), 비효율적 |
| 원형 큐 | 선형 큐의 공간 낭비 해결, 삽입/삭제 O(1) |
| 덱(Deque) | 앞뒤 양쪽에서 삽입/삭제 가능 |
| 우선순위 큐 | 우선순위 높은 항목이 먼저 나감, 힙 사용 시 효율적 |
6주차
항목 - 설명 요약
| 연결 리스트 개념 | 포인터 기반 동적 자료구조, 유연한 삽입/삭제 지원 |
| 단일 연결 리스트 | 노드가 다음 노드만 가리킴, 단방향 순회 |
| 이중 연결 리스트 | 노드가 앞/뒤 모두 가리킴, 양방향 순회 |
| 원형 연결 리스트 | 마지막 노드가 처음 노드를 가리킴, 무한 루프 가능 |
| 배열과의 차이점 | 배열은 접근이 빠르고 고정 크기, 리스트는 유연하고 동적 |
7주차
항목 - 설명 요약
| 다항식 연결 리스트 | 항(term)을 노드로 구성, 계수/지수/링크로 표현 |
| 다항식 덧셈 알고리즘 | 지수 비교 → 더하거나 그대로 추가, 연결 리스트 병합과 유사 |
| 다중 연결 리스트 | 하나의 노드가 2개 이상의 방향으로 연결됨 |
| 희소 행렬 표현 | 행과 열 방향 포인터로 0이 아닌 데이터만 저장 |
8주차 - 중간고사
9주차
항목 - 설명 요약
| 트리(Tree) | 비선형 자료구조, 계층 구조 표현에 적합 |
| 노드 용어 | 루트, 자식, 부모, 리프, 서브트리, 레벨, 높이 등 |
| 이진 트리 | 각 노드가 최대 2개의 자식을 가짐 |
| 전위 순회 | 부모 → 왼쪽 → 오른쪽 |
| 중위 순회 | 왼쪽 → 부모 → 오른쪽 (BST에서 정렬됨) |
| 후위 순회 | 왼쪽 → 오른쪽 → 부모 |
| 레벨 순회 | BFS 방식, 큐를 활용 |
10주차
항목 - 설명 요약
| 이진 탐색 트리 | 왼쪽 < 루트 < 오른쪽, 이진 탐색이 가능한 트리 구조 |
| 탐색 연산 | 작으면 왼쪽, 크면 오른쪽으로 재귀 |
| 삽입 연산 | 탐색과 같은 방식으로 빈 자리에 삽입 |
| 삭제 연산 | 리프, 자식 1개, 자식 2개 경우로 분리하여 처리 |
| 시간복잡도 | 평균 O(log n), 최악 O(n) (편향 트리일 경우) |
| 중위 순회 활용 | BST의 정렬된 데이터를 출력할 수 있음 |
11주차
항목 - 요약 설명
| AVL 트리 | 높이 균형 이진 탐색 트리, 삽입/삭제 시 회전으로 균형 유지 |
| 회전 종류 | LL, RR, LR, RL 회전 |
| 힙(Heap) | 완전 이진 트리, 부모 ≥/≤ 자식. 우선순위 구조에 적합 |
| 최소/최대 힙 | 루트가 가장 작은/큰 값을 가지는 힙 |
| 우선순위 큐 | 우선순위가 높은 항목 먼저 처리. 힙으로 효율적으로 구현 |
12주차
항목 - 설명 요약
| 그래프 정의 | 정점과 간선의 집합, 다양한 관계 구조 표현 가능 |
| 그래프 종류 | 방향성/무방향, 가중치/무가중치, 순환/비순환 등 |
| 인접 행렬 | 2차원 배열, O(n²) 공간, 간선 탐색 빠름 |
| 인접 리스트 | 연결 리스트, O(n+e) 공간, 공간 효율적 |
| 선택 기준 | 밀집 그래프→행렬 / 희소 그래프→리스트 |
13주차
항목 - 설명 요약
| 그래프 탐색 | 모든 정점을 순서대로 방문하는 과정 |
| DFS (깊이 우선 탐색) | 스택 구조, 깊이 우선 접근, 재귀 구현 가능 |
| BFS (너비 우선 탐색) | 큐 구조, 레벨 순으로 탐색, 최단 거리 탐색에 유리 |
| 구현 방식 비교 | DFS → 재귀/스택 / BFS → 큐 |
| 시간복잡도 | O(n + e) → 간선 수에 따라 결정 |
14주차
항목 - 설명 요약
| MST 정의 | 모든 정점을 연결하고 가중치 총합이 최소인 트리 |
| MST 조건 | 사이클 없음, 정점 수 – 1개의 간선으로 구성 |
| Prim 알고리즘 | 한 정점에서 확장, 최소 간선 반복 선택 |
| Kruskal 알고리즘 | 간선 오름차순 정렬 후 사이클 없는 간선 선택 |
| Union-Find 사용 | Kruskal에서 사이클 여부 판단용 |
| 활용 사례 | 네트워크 설계, 도로 연결, 비용 최소 경로 구성 등 |
15주차 - 기말고사
작성하다보니 말투가 다소 딱딱하네요. 공부하는데 제 게시글이 도움이 되었으면 좋겠습니다. 응원하겠습니다.
반응형