📌 자료 구조와 알고리즘
1️⃣ 자료 구조란?
- 데이터를 효율적으로 저장하고 활용하기 위한 논리적인 구조
- 데이터의 종류와 상황에 맞춰 다양한 자료 구조 선택
2️⃣ 자료 구조의 특징
- 같은 데이터라도 구조에 따라 성능 차이 발생
- 효율적인 구조일수록 실행 속도가 빠르고 메모리 사용이 적음
- 데이터 추가, 삭제, 탐색을 효율적으로 설계 가능
📌 자료 구조의 종류
1️⃣ 단순 구조
- 기본 데이터 타입(정수, 실수, 문자 등)으로 구성됨
- 데이터를 확장하여 더 복잡한 구조를 만들 수 있음
2️⃣ 선형 구조
- 데이터들이 1:1 관계로 연결됨
주요 종류
- 순차(Sequential) 구조 → 데이터 탐색 속도가 빠름, 데이터가 순서대로 저장되어 있음
- 연결(Linked) 구조 → 데이터 추가/삭제가 유리함, 데이터들이 서로 연결되어 있어서 이동이나 삭제가 쉬움
대표적인 예시
- 스택(Stack), 큐(Queue), 데크(Deque), 선형 리스트, 연결 리스트
3️⃣ 비선형 구조
- 데이터 간 1:N(일대다), N:M(다대다) 관계로 연결되는 구조
대표적인 예시
- 트리(Tree), 그래프(Graph)
4️⃣ 파일 구조
- 데이터를 보조 기억 장치에 저장하는 구조
대표적인 종류
- 순차 파일 (차례대로 저장)
- 직접 파일 (바로 접근 가능)
- 색인 순차 파일 (색인을 사용해 빠르게 검색)
🛠 알고리즘 (Algorithm)
1️⃣ 알고리즘이란?
- 문제 해결을 위해 필요한 동작들을 순서대로 나열한 방법
- 자료 구조와 함께 프로그램의 핵심
2️⃣ 알고리즘의 원칙
- 입력이 없어도 출력은 반드시 1개 이상 존재
- 명확한 의미와 완벽한 구성을 가져야 함
- 반복 실행 가능해야 실제 연산 가능
3️⃣ 알고리즘 평가 기준
- 정확성: 입력에 대해 항상 올바른 결과를 출력하는가?
- 명확성: 알고리즘이 이해하고 변경하기 쉬운가?
- 수행량: 주요 연산(비교, 연산)의 실행 횟수, 얼마나 빨리 실행되는지
- 메모리 사용량: 문제 해결에 사용된 메모리 공간, 얼마나 효율적으로 메모리를 사용하는지
4️⃣ 알고리즘의 표현 방법
- 순서도(Flow Chart)
- 약속된 도형과 기호로 알고리즘을 시각적으로 표현
- 프로그램의 흐름을 한눈에 이해하기 쉬움
2. 의사코드(Pseudo Code)
- 일반적인 언어로 코드와 유사하게 표현
- 실제 프로그래밍 언어보다 이해하기 쉬움
📌 알고리즘 설계 기법 정리
1️⃣ 동적 계획법 (Dynamic Programming)
- 작은 문제를 해결한 뒤, 이를 활용해 큰 문제를 해결하는 방식
- Bottom-up(작은 문제 → 큰 문제 해결) 방식
- 예시: 피보나치 수열 (반복문 + 메모이제이션 활용)
2️⃣ 탐욕적 알고리즘 (Greedy Algorithm)
- 매 순간 가장 좋은 선택을 반복하여 최적의 결과를 도출하는 방식
- 항상 최적의 해를 보장하지는 않음
- 예시: 거스름돈 문제 (가장 큰 화폐 단위부터 차감)
3️⃣ 재귀적 알고리즘 (Recursive Algorithm)
- 자기 자신을 계속 호출하는 방식 (풀이 과정에서 같은 풀이 반복)
- 역순으로 결과가 출력됨
- 예시: 하노이의 탑, 팩토리얼 계산
4️⃣ 근사 알고리즘 (Approximation Algorithm)
- 최적의 답을 구하기 어려울 때, 빠르게 근사 해법을 찾아내는 방식
- 시간 복잡도를 낮추면서 가능한 최적의 해를 구함
- 예시: 외판원 문제(TSP)의 근사 해법
5️⃣ 분할 정복법 (Divide and Conquer)
- 큰 문제를 작은 문제로 나눠 해결 후, 다시 합치는 방식
- Top-down(큰 문제 → 작은 문제로 나눠 해결) 접근
- 예시: 퀵 정렬, 병합 정렬
6️⃣ 되돌아가기, 퇴각 검색법, 되추적 기법(Backtracking)
- 해결책을 찾아가다가 막히면 이전 단계로 돌아가서 다시 시도
- 새로운 탐색이 가능할 때까지 반복 (DFS 기반=깊이 우선 탐색 알고리즘)
- 예시: 미로 찾기, N-Queens 문제
📌선형 구조
1️⃣ 스택이란?
- 데이터를 한쪽에서만 삽입/삭제하는 구조
- TOP (스택 포인터): 가장 마지막에 삽입된 데이터의 위치 저장
- PUSH: 데이터 삽입 (TOP 1씩 증가)
- POP: 데이터 삭제 (TOP 1씩 감소)
- 오버플로우(Overflow): 스택이 가득 차서 더 이상 PUSH 불가능할 때 발생
- 언더플로우(Underflow): 스택이 비어 있어 POP이 불가능할 때 발생
2️⃣ 스택의 특징
- LIFO (Last In First Out, 후입선출) 구조 → 가장 나중에 삽입된 데이터가 가장 먼저 제거됨
주요 활용 예시
- 함수 호출 (서브 루틴)
- 깊이 우선 탐색 (DFS)
- 재귀 호출
- Linear List
- 수식 계산 (Post-fix 표현)
- 0-주소 명령어 방식에서 사용됨
3️⃣ 수식 표기법
- 연산자의 위치에 따라 3가지 방식으로 나뉨:
- 전위식 (Pre-fix): 연산자가 피연산자의 앞(왼쪽)에 위치 = 폴란드(Polish)표기법
- 중위식 (In-fix): 연산자가 피연산자의 중간에 위치 (일반적인 수식)
- 후위식 (Post-fix): 연산자가 피연산자의 뒤(오른쪽)에 위치 = 역 폴란드 표기법
📌 수식 표기법 변환 정리
수식을 변환하는 3가지 방법:
- 중위식(In-fix) → 전위식(Pre-fix)
- 중위식(In-fix) → 후위식(Post-fix)
- 전위식(Pre-fix) → 중위식(In-fix)
1️⃣ 중위식을 전위식으로 변환 - 괄호 제거
✔ 방법
- 연산 우선순위가 높은 연산자부터 변환
- 변환된 연산을 왼쪽(앞) 에 배치
- 괄호를 제거하여 최종 표현
2️⃣ 중위식을 후위식으로 변환 - 괄호 제거
✔ 방법
- 연산 우선순위가 높은 연산자부터 변환
- 변환된 연산을 오른쪽(뒤) 에 배치
- 괄호를 제거하여 최종 표현
3️⃣ 전위식을 중위식으로 변환 - 괄호 추가
✔ 방법
- 연산 우선순위가 높은 연산자부터 변환
- 연산자가 중간 위치에 오도록 배치
- 연산 순서가 바뀌지 않도록 괄호 추가
4️⃣ 후위식을 중위식으로 변환 - 괄호 추가
✔ 방법
- 후위식에서 연산자가 나오면, 바로 앞의 두 개 피연산자를 중위식 형태로 감싸기
- 연산 순서가 변하지 않도록 괄호를 적절히 추가해야 함
4️⃣ 큐(Queue) 정리
💡 큐(Queue)란?
- 데이터를 한쪽에서 삽입(Rear), 반대쪽에서 삭제(Front) 하는 자료구조
- 선입선출(FIFO, First In First Out) 방식→ 먼저 들어온 데이터가 먼저 나감
🔍 큐의 구조
- 삽입 포인터(Rear): 데이터가 추가될 때 위치를 가리킴
- 삭제 포인터(Front): 데이터가 제거될 때 위치를 가리킴
- 두 값이 같을 때는 큐에 데이터가 비어있는 경우임
🔍 큐 vs 스택 비교
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 2열 선택2열 다음에 열 추가
- 3열 선택3열 다음에 열 추가
- 4열 선택4열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
|
자료구조
|
동작 방식
|
삽입 방향
|
삭제 방향
|
활용 예시
|
|
스택 (Stack)
|
후입선출 (LIFO)
|
한쪽(TOP)
|
한쪽(TOP)
|
함수 호출, 실행 취소(Undo)
|
|
큐 (Queue)
|
선입선출 (FIFO)
|
뒤쪽(Rear)
|
앞쪽(Front)
|
프린터 대기열, 프로세스 스케줄링
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
✔ 스택은 나중에 들어온 게 먼저 나감
✔ 큐는 먼저 들어온 게 먼저 나감
5️⃣ 데크(Deque)란?
💡 양쪽에서 삽입/삭제가 가능한 큐
- 일반적인 큐(Queue)는 한쪽에서 삽입하고, 반대쪽에서 삭제하지만 데크(Deque)는 양쪽에서 삽입/삭제가 가능함!
✔ Left(왼쪽)과 Right(오른쪽) 포인터를 사용해 데이터를 추가/삭제
✔ 양방향 큐라고도 불림
🔍 데크의 특징
- 삽입과 삭제가 자주 일어나는 경우에 유리
- 입출력 제한에 따라 두 가지 방식으로 나뉨
- 입력 제한(Scroll) 데크: 양쪽에서 출력 가능, 삽입은 한쪽에서만 가능
- 출력 제한(Shelf) 데크: 양쪽에서 삽입 가능, 출력은 한쪽에서만 가능
📌 즉, 원하는 방식에 맞춰서 삽입/삭제를 조절할 수 있음! 🎯
6️⃣선형 리스트(Linear List)란?
💡 데이터가 연속된 공간에 저장되는 자료구조
- 대표적인 형태가 배열(Array)
- 데이터가 연속된 메모리 공간에 배치됨
✔ 배열(Array)은 가장 단순한 형태의 선형 리스트
✔ 접근(읽기)은 빠르지만, 삽입/삭제 시 이동이 필요해 성능이 떨어질 수 있음
🔍 배열(Array)의 특징
- 같은 크기 & 같은 타입의 데이터를 연속적으로 저장
- 인덱스(Index)로 접근이 가능
- 하지만 중간에 데이터를 추가/삭제할 경우, 이동이 필요해 성능 저하 발생
🔍 배열에서 삽입 & 삭제 시 이동 과정
🟢 배열 중간에 데이터 삽입 - 모든 요소가 한 칸씩 오른쪽으로 이동!
🔴 배열 중간에 데이터 삭제 - 모든 요소가 한 칸씩 왼쪽으로 이동!
6️⃣ 연결 리스트(Linked List)란?
💡 배열의 단점을 보완한 자료구조
- 배열(Array): 메모리가 연속적으로 배치됨 → 삽입/삭제 시 데이터 이동 필요 (비효율적)
- 연결 리스트(Linked List): 각 노드(Node)가 포인터(위치값을 저장하는 변수)로 연결됨 → 삽입/삭제가 빠름
✔ 각 노드는 데이터 + 다음 노드를 가리키는 포인터로 구성됨
✔ 데이터가 연속적으로 저장되지 않아도 됨 (메모리 활용 효율적)
🔍 연결 리스트의 종류
🟢 1. 단일(Single) 연결 리스트
- 각 노드가 다음 노드만 가리킴
- 마지막 노드의 포인터는 NULL 값을 가짐
- 탐색은 항상 첫 노드(Head)부터 시작
[ 20 | → ] → [ 56 | → ] → [ 25 | → ] → [ 17 | NULL ]
🔵 2. 단일 원형(Circular) 연결 리스트
- 단일 연결 리스트와 유사하지만 마지막 노드가 첫 노드를 가리킴
- NULL이 없음 → 반복 탐색 가능!
- 끝에서 다시 처음으로 돌아갈 수 있음
[ 20 | → ] → [ 56 | → ] → [ 25 | → ] → [ 17 | → (다시 첫 노드 20) ]🟠 3. 이중(Double) 연결 리스트
- 각 노드가 앞(Prev)과 뒤(Next) 노드를 가리킴
- 양방향 탐색 가능
- 포인터가 2개 필요해 메모리 사용량 증가
NULL ← [ 20 | ↔ ] ↔ [ 56 | ↔ ] ↔ [ 25 | ↔ ] ↔ [ 17 | NULL ]🟣 4. 이중 원형(Double Circular) 연결 리스트
- 이중 연결 리스트와 원형 리스트의 결합
- 첫 노드의 Prev 포인터가 마지막 노드를 가리킴
- 마지막 노드의 Next 포인터가 첫 노드를 가리킴
- 양방향 탐색 & 순환 가능
[ 20 | ↔ ] ↔ [ 56 | ↔ ] ↔ [ 25 | ↔ ] ↔ [ 17 | ↔ (다시 첫 노드 20) ]📌비선형 구조
✅ 트리(Tree)란?
💡 데이터를 계층 구조(1:N 관계)로 표현하는 자료구조
- 각 노드는 간선(Edge, branch)으로 연결됨
- 방향성이 있는 그래프의 한 종류
- 트리의 간선 개수 = 노드 개수 - 1
✅ 트리는 종류가 많지만, 기본적으로 부모-자식 관계로 구성됨!
🔍 트리의 기본 용어
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
- 3행 선택3행 다음에 행 추가
- 4행 선택4행 다음에 행 추가
- 5행 선택5행 다음에 행 추가
- 6행 선택6행 다음에 행 추가
- 7행 선택7행 다음에 행 추가
- 8행 선택8행 다음에 행 추가
- 9행 선택9행 다음에 행 추가
- 10행 선택10행 다음에 행 추가
|
용어
|
설명
|
|
루트=근 (Root) 노드
|
최상위 노드 (부모 없음)
|
|
단말(Leaf) 노드
|
자식이 없는 노드
|
|
내부(Internal) 노드
|
부모이면서 자식이 있는 노드
|
|
형제(Sibling) 노드
|
같은 부모를 가진 노드
|
|
노드의 크기(Size)
|
해당 노드를 포함한 자식 노드 개수
|
|
노드의 깊이(Depth)
|
루트 노드부터 해당 노드까지의 거리
|
|
노드의 높이(Height)
|
해당 노드에서 가장 깊은 단말 노드까지의 거리
|
|
레벨(Level)
|
같은 깊이를 가지는 노드의 집합
|
|
노드의 차수(Degree)
|
해당 노드가 가진 자식 노드 개수
|
|
트리의 차수
|
최대 차수를 가진 노드의 차수
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
A (Root)
/ \
B C (Internal Nodes)
/ \ \
D E F (Leaf Nodes)
📌 A는 루트, B와 C는 내부 노드, D/E/F는 단말 노드!
✅ 이진 트리(Binary Tree)
💡 각 노드가 최대 2개의 자식을 가질 수 있는 트리
🔍 이진 트리의 종류
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
- 3행 선택3행 다음에 행 추가
|
유형
|
설명
|
|
전(Full) 이진 트리
|
모든 노드가 0개 또는 2개의 자식 노드를 가짐
|
|
완전(Complete) 이진 트리
|
마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 채워짐
|
|
포화(Perfect) 이진 트리
|
모든 레벨이 꽉 차 있으며, 모든 노드가 2개의 자식 노드를 가짐
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
📌 완전 이진 트리는 왼쪽부터 차례로 채워지는 특징이 있음!
✅ 트리 순회(Tree Traversal)
💡 트리의 모든 노드를 방문하는 방법
- 중위 순회 (In-Order): 왼쪽 → 부모 → 오른쪽
- 전위 순회 (Pre-Order): 부모 → 왼쪽 → 오른쪽
- 후위 순회 (Post-Order): 왼쪽 → 오른쪽 → 부모
✅ 예제 트리
A
/ \
B C
/ \ \
D E F
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 2열 선택2열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
- 3행 선택3행 다음에 행 추가
|
순회 방법
|
방문 순서
|
|
|
중위 순회 - 좌측의 자식 노드부터 시작
|
D → B → E → A → C → F
|
왼쪽 자식 → 부모 → 오른쪽 자식
|
|
전위 순회 - 부모 노드로 시작
|
A → B → D → E → C → F
|
부모 → 왼쪽 자식 → 오른쪽 자식
|
|
후위 순회 - 좌측의 자식 노드부터 시작
|
D → E → B → F → C → A
|
왼쪽 자식 → 오른쪽 자식 → 부모
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
✅ 그래프(Graph)란?
💡 노드(정점)와 간선(연결선)으로 이루어진 자료구조
- 트리(Tree)와 다르게 순환(Cycle)이 존재 가능
- N:M 관계를 표현하는 데 적합한 자료구조
📌 그래프는 트리보다 더 복잡한 관계를 표현할 수 있음!
✅그래프의 주요 개념
- 0열 선택0열 다음에 열 추가
- 1열 선택1열 다음에 열 추가
- 0행 선택0행 다음에 행 추가
- 1행 선택1행 다음에 행 추가
- 2행 선택2행 다음에 행 추가
- 3행 선택3행 다음에 행 추가
- 4행 선택4행 다음에 행 추가
- 5행 선택5행 다음에 행 추가
- 6행 선택6행 다음에 행 추가
- 7행 선택7행 다음에 행 추가
|
개념
|
설명
|
|
정점(Vertex)
|
그래프에서 데이터를 저장하는 노드
|
|
간선(Edge, Branch)
|
정점 간 연결 관계
|
|
인접 정점(Adjacent Vertex)
|
간선으로 직접 연결된 정점
|
|
사이클(Cycle)
|
시작과 종료가 동일한 경로
|
|
단순 경로(Simple Path)
|
중복 없이 연결된 경로
|
|
진입 차수(In-Degree)
|
정점으로 들어오는 간선 개수
|
|
진출 차수(Out-Degree)
|
정점에서 나가는 간선 개수
|
- 셀 병합
- 행 분할
- 열 분할
- 너비 맞춤
- 삭제
✅ 예제 그래프
A --- B
| |
C --- D --- E
📌 A와 B는 인접 정점, A→B→D→E는 하나의 경로!
✅ 그래프의 종류
💡 그래프는 여러 가지 기준으로 분류됨!
🔍 1. 방향 그래프(Directed Graph)
- 간선에 방향성이 있음
- A → B와 B → A는 다름
- 방향 그래프의 최대 간선 수 = n(n-1)
A → B
↓ ↓
C → D → E
📌 방향이 있는 화살표를 따라 이동 가능!
🔍 2. 무방향 그래프(Undirected Graph)
- 간선에 방향성이 없음 (양방향)
- A - B와 B - A가 동일
- 무방향 그래프의 최대 간선 수 = n(n-1)/2
A --- B
| |
C --- D --- E
📌 어느 방향으로든 이동 가능!
총정리
1️⃣ 자료 구조 (Data Structure)
🔹 자료 구조란?
- 데이터를 효율적으로 저장하고 활용하기 위한 구조
- 데이터의 종류와 목적에 따라 적절한 자료 구조 선택
🔹 자료 구조의 종류
- 단순 구조: 정수, 실수, 문자 등 기본 데이터 타입
2. 선형 구조: 데이터가 순서대로 배치됨
- 배열(Array): 인덱스를 이용해 빠르게 접근 가능
- 스택(Stack): LIFO(후입선출), 함수 호출, DFS
- 큐(Queue): FIFO(선입선출), 프로세스 스케줄링
- 데크(Deque): 양쪽 삽입/삭제 가능
- 연결 리스트(Linked List): 데이터 삽입/삭제 용이
3. 비선형 구조: 데이터가 1:N, N:M 관계로 연결됨
- 트리(Tree): 계층 구조 표현 (예: 파일 시스템)
- 그래프(Graph): 복잡한 관계 표현 (예: SNS)
4. 파일 구조: 데이터를 보조 기억 장치에 저장하는 방식
2️⃣ 알고리즘 (Algorithm)
🔹 알고리즘이란?
- 문제 해결을 위한 절차나 방법
- 자료 구조와 함께 프로그램의 핵심 요소
🔹 알고리즘 평가 기준
- 정확성: 올바른 결과 도출
- 명확성: 이해하고 수정하기 쉬운가
- 수행량: 연산 횟수(시간 복잡도)
- 메모리 사용량: 공간 복잡도 고려
🔹 주요 알고리즘 설계 기법
- 동적 계획법 (DP): 작은 문제 해결 후 결과를 재활용
2. 탐욕적 알고리즘 (Greedy): 현재 최선 선택 반복
3. 분할 정복 (Divide & Conquer): 문제를 작은 단위로 나눠 해결
4. 재귀 (Recursion): 자기 자신을 호출하는 방식
5. 백트래킹 (Backtracking): 가능한 모든 경우를 탐색하며 해답 찾기
3️⃣ 자료 구조 상세 정리
🔹 스택(Stack)
- 후입선출 (LIFO): 마지막에 들어온 데이터가 먼저 나감
- 활용: 함수 호출, DFS, 재귀, 수식 계산
🔹 큐(Queue)
- 선입선출 (FIFO): 먼저 들어온 데이터가 먼저 나감
- 활용: 프로세스 스케줄링, 프린터 대기열
🔹 데크(Deque)
- 양쪽에서 삽입/삭제 가능
- 활용: 브라우저 히스토리, 캐시
🔹 연결 리스트(Linked List)
- 연속된 메모리 공간이 필요 없음 → 삽입/삭제 용이
종류
- 단일 연결 리스트: 한 방향으로만 연결
- 이중 연결 리스트: 양방향 탐색 가능
- 원형 연결 리스트: 마지막 노드가 첫 노드를 가리킴
4️⃣ 트리(Tree) & 그래프(Graph)
🔹 트리(Tree)
- 계층 구조를 표현하는 비선형 자료 구조
- 이진 트리: 각 노드가 최대 2개의 자식 노드 가짐
트리 순회 방식
- 중위 순회 (In-Order): 왼쪽 → 부모 → 오른쪽
- 전위 순회 (Pre-Order): 부모 → 왼쪽 → 오른쪽
- 후위 순회 (Post-Order): 왼쪽 → 오른쪽 → 부모
🔹 그래프(Graph)
- 노드(정점)와 간선(연결선)으로 이루어진 구조
종류
- 방향 그래프: 간선에 방향이 있음
- 무방향 그래프: 간선이 양방향
- 가중 그래프: 간선에 가중치가 있음
탐색 알고리즘
- DFS (깊이 우선 탐색): 스택 사용, 백트래킹
- BFS (너비 우선 탐색): 큐 사용, 최단 경로 탐색
5️⃣ 정렬 알고리즘 (Sorting Algorithm)
- 선택 정렬: 가장 작은 요소를 선택해 정렬
- 버블 정렬: 인접한 두 개를 비교해 자리 교환
- 삽입 정렬: 이미 정렬된 부분에 새 요소를 삽입
- 퀵 정렬: 기준 값(Pivot) 기준으로 정렬 (분할 정복)
- 병합 정렬: 리스트를 반씩 나누어 정렬 후 병합