1. 연결 리스트(Linked List)와 트리(Tree)의 기본 구조
이번 학기 3, 4강에서 배우는 AVL 트리, Red-Black 트리, 2-3 트리는 모두 작년에 배운 '이진 탐색 트리'의 업그레이드 버전입니다.
- 복습 포인트: 노드(Node)와 포인터(Link)의 개념, 이진 탐색 트리(BST)에서 데이터를 찾고 삽입하는 기본 원리.
2. 재귀(Recursion)와 분할 정복
9강의 QuickSort나 11강의 동적 프로그래밍(DP)을 이해하려면 재귀 함수에 익숙해야 합니다.
- 복습 포인트: 작년에 배운 DFS(깊이 우선 탐색)나 이진 트리 순회 코드를 보면서, 함수가 자기 자신을 호출할 때 스택에 어떻게 쌓이는지 흐름을 다시 보세요
1순위: 트리(Tree)의 기본 개념과 구현 (자료구조 9, 10주차)
알고리즘 수업의 초반부(3~5주차)와 후반부(12주차)가 모두 트리를 기반으로 합니다.
- 복습 내용: 이진 트리(Binary Tree)의 정의, 순회(Traversal: Pre/In/Post-order), 이진 탐색 트리(BST)의 삽입/삭제 원리.
- 연결되는 알고리즘 주제: AVL 트리, 2-3 트리, Red-Black 트리(4주차), Tries(12주차).
- 이유: 기본적인 이진 탐색 트리의 동작 원리를 모르면 성능이 개선된 AVL이나 Red-Black 트리의 회전(Rotation) 개념을 이해하기 매우 어렵습니다.
2순위: 그래프(Graph)의 표현과 탐색 (자료구조 11, 12주차)
알고리즘 중반부(10~11주차)의 핵심인 Greedy와 Dynamic Programming의 사례가 대부분 그래프 문제입니다.
- 복습 내용: 그래프의 표현 방식(인접 행렬 vs 인접 리스트), DFS(깊이 우선 탐색), BFS(너비 우선 탐색).
- 연결되는 알고리즘 주제: Shortest Path(Dijkstra), MST, NP-완전 문제.
- 이유: 알고리즘 수업에서 Dijkstra나 Floyd 알고리즘을 배울 때 그래프 구현 자체가 막히면 알고리즘 논리를 따라갈 수 없습니다.
3순위: 기본 정렬 알고리즘과 시간 복잡도 (자료구조 2, 13, 14주차)
알고리즘 수업의 시작(1~2주차)이 정렬이며, 9주차 분할정복에서도 다시 등장합니다.
- 복습 내용: 선택/삽입 정렬(기초), **퀵 정렬(Quick), 합병 정렬(Merge), 힙 정렬(Heap)**의 원리와 시간 복잡도(Big-O).
- 연결되는 알고리즘 주제: Shell sort, Radix sort(1주차), 분할정복(9주차).
- 이유: 알고리즘 수업은 "어떻게 정렬하는가"를 넘어 "왜 이 정렬이 더 효율적인가"를 증명하고 비교하는 데 집중합니다. 기초 정렬의 메커니즘을 미리 숙지해야 합니다.
4순위: 재귀(Recursion)와 스택/큐 (자료구조 4, 5주차)
알고리즘의 핵심 기법인 분할 정복과 동적 프로그래밍의 기초가 됩니다.
- 복습 내용: 재귀 호출의 작동 원리, 스택(Stack)의 구조.
- 연결되는 알고리즘 주제: 분할정복(9주차), 동적 프로그래밍(11주차).
- 이유: 대부분의 심화 알고리즘은 재귀적으로 설계됩니다. 자료구조에서 배웠던 '미로찾기'나 '수식 계산' 등에서 재귀가 어떻게 쓰였는지 다시 확인해보세요.
굳이 ㄴㄴ
- 희소행렬/다항식 관련 계산 로직
- 마방진/미로찾기의 구체적인 구현 코드
- 선택 정렬/삽입 정렬의 단순 구현 (개념만 알면 됨)
- 스택/큐를 배열로 직접 만드는 코드 (Java Collection 사용법이 더 중요)
1. 기본 구조: Node 클래스
먼저 데이터를 담을 노드가 필요합니다. 왼쪽 자식과 오른쪽 자식을 가리키는 참조 변수가 핵심이에요.
Java
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
2. 핵심 로직: BST 클래스
재귀(Recursion)를 사용하면 코드가 훨씬 깔끔해집니다.
Java
class BinarySearchTree {
Node root;
// 1. 삽입 (Insert)
public void insert(int data) {
root = insertRec(root, data);
}
private Node insertRec(Node root, int data) {
// 비어있으면 새 노드 생성
if (root == null) {
root = new Node(data);
return root;
}
// 기준보다 작으면 왼쪽으로, 크면 오른쪽으로!
if (data < root.data)
root.left = insertRec(root.left, data);
else if (data > root.data)
root.right = insertRec(root.right, data);
return root;
}
// 2. 탐색 (Search)
public boolean search(int data) {
return searchRec(root, data);
}
private boolean searchRec(Node root, int data) {
// 못 찾았거나 끝까지 간 경우
if (root == null) return false;
// 찾았을 때
if (root.data == data) return true;
// 크기 비교해서 재귀 호출
return data < root.data
? searchRec(root.left, data)
: searchRec(root.right, data);
}
}
1. 순회 (Traversal): 모든 노드 방문하기
트리에 있는 데이터를 어떤 순서로 읽을 것인가 하는 문제입니다. 특히 **중위 순회(In-order)**가 제일 중요해요.
- 전위 (Pre-order): 나 → 왼쪽 → 오른쪽 (복사할 때 유용)
- 중위 (In-order): 왼쪽 → 나 → 오른쪽 (정렬된 결과를 얻을 때 사용!)
- 후위 (Post-order): 왼쪽 → 오른쪽 → 나 (삭제할 때 유용)
2. 삭제 (Delete): 가장 까다로운 놈
삽입은 그냥 빈자리 찾아가면 끝인데, 삭제는 빈자리를 메꿔야 해서 복잡했죠.
- 자식이 없을 때: 그냥 지우면 끝.
- 자식이 하나일 때: 자식을 내 위치로 올리고 지우면 끝.
- 자식이 둘일 때 (핵심): 내 오른쪽 서브트리에서 **가장 작은 값(Successor)**을 찾아 내 자리로 복사한 뒤, 그 노드를 지웁니다.
1. 그래프 저장하기 (인접 리스트)
배열 안에 ArrayList를 넣어서 "내 옆에 누가 있는지" 목록을 만드는 방식입니다. 메모리 효율이 좋아서 실무나 코딩 테스트에서 가장 선호됩니다.
Java
import java.util.*;
class Graph {
private int V; // 정점의 개수
private LinkedList<Integer> adj[]; // 인접 리스트
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 간선 추가 (무방향 그래프 기준)
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
}
2. 그래프 탐색: DFS vs BFS
이번 학기 10~11강에서 배울 **Greedy(Dijkstra)**나 DP 알고리즘의 뼈대가 되는 아주 중요한 부분입니다.
① DFS (깊이 우선 탐색)
한 놈만 끝까지 패는 스타일입니다. **재귀(Recursion)**나 Stack을 사용합니다.
- 용도: 경로의 특징을 저장해야 할 때, 모든 노드를 방문할 때.
Java
void DFS(int v, boolean visited[]) {
visited[v] = true; // 현재 노드 방문 처리
System.out.print(v + " ");
for (int n : adj[v]) {
if (!visited[n])
DFS(n, visited); // 재귀 호출!
}
}
② BFS (너비 우선 탐색)
내 주변 친구들부터 다 확인하는 스타일입니다. Queue를 사용합니다.
- 용도: 최단 거리 찾기 (작년 12강 Dijkstra의 기초가 됨).
Java
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll(); // 큐에서 꺼내기
System.out.print(s + " ");
for (int n : adj[s]) {
if (!visited[n]) {
visited[n] = true;
queue.add(n); // 인접한 노드 큐에 넣기
}
}
}
}
💡 이번 학기 알고리즘 수업과의 연결점
- 10강 Shortest Path (Dijkstra): 위 BFS 코드에 "가중치(비용)" 개념이 들어간 버전이라고 보시면 됩니다.
- 11강 Dynamic Programming: 그래프에서 중복되는 경로 계산을 어떻게 줄일지 고민하게 될 거예요.
- 12강 Tries: 문자열을 그래프(트리) 형태로 저장하는 특수 구조를 배웁니다.
1. 그래프 저장하기 (인접 리스트)
배열 안에 ArrayList를 넣어서 "내 옆에 누가 있는지" 목록을 만드는 방식입니다. 메모리 효율이 좋아서 실무나 코딩 테스트에서 가장 선호됩니다.
Java
import java.util.*;
class Graph {
private int V; // 정점의 개수
private LinkedList<Integer> adj[]; // 인접 리스트
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 간선 추가 (무방향 그래프 기준)
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
}
2. 그래프 탐색: DFS vs BFS
이번 학기 10~11강에서 배울 **Greedy(Dijkstra)**나 DP 알고리즘의 뼈대가 되는 아주 중요한 부분입니다.
① DFS (깊이 우선 탐색)
한 놈만 끝까지 패는 스타일입니다. **재귀(Recursion)**나 Stack을 사용합니다.
- 용도: 경로의 특징을 저장해야 할 때, 모든 노드를 방문할 때.
Java
void DFS(int v, boolean visited[]) {
visited[v] = true; // 현재 노드 방문 처리
System.out.print(v + " ");
for (int n : adj[v]) {
if (!visited[n])
DFS(n, visited); // 재귀 호출!
}
}
② BFS (너비 우선 탐색)
내 주변 친구들부터 다 확인하는 스타일입니다. Queue를 사용합니다.
- 용도: 최단 거리 찾기 (작년 12강 Dijkstra의 기초가 됨).
Java
void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll(); // 큐에서 꺼내기
System.out.print(s + " ");
for (int n : adj[s]) {
if (!visited[n]) {
visited[n] = true;
queue.add(n); // 인접한 노드 큐에 넣기
}
}
}
}
💡 이번 학기 알고리즘 수업과의 연결점
- 10강 Shortest Path (Dijkstra): 위 BFS 코드에 "가중치(비용)" 개념이 들어간 버전이라고 보시면 됩니다.
- 11강 Dynamic Programming: 그래프에서 중복되는 경로 계산을 어떻게 줄일지 고민하게 될 거예요.
- 12강 Tries: 문자열을 그래프(트리) 형태로 저장하는 특수 구조를 배웁니다.
왜 int[] arr이런것처럼
아 형태는 같나
list<리스트는 제네틱쓰니깐>[배열임을 알려줌]
1. 재귀(Recursion) 방식
가장 코드가 깔끔하고 직관적이라 많이 쓰입니다. "방문하고 -> 자식 있으면 바로 파고들기" 구조예요.
Java
void DFS_Recursive(int v, boolean[] visited) {
visited[v] = true; // 1. 현재 노드 방문 도장 쾅!
System.out.print(v + " ");
// 2. 내 옆집(인접 리스트)들 하나씩 확인
for (int next : adj[v]) {
if (!visited[next]) { // 방문 안 한 곳이면
DFS_Recursive(next, visited); // 3. 바로 그 집으로 들어감 (재귀)
}
}
}
2. 스택(Stack) + 반복문 방식
재귀가 너무 깊어져서 에러(StackOverflow)가 날 것 같을 때 사용하는 안전한 방식입니다.
Java
void DFS_Stack(int start) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(start); // 시작 노드 넣기
while (!stack.isEmpty()) {
int v = stack.pop(); // 하나 꺼내서
if (!visited[v]) {
visited[v] = true; // 방문 처리
System.out.print(v + " ");
// 꺼낸 노드의 이웃들을 스택에 담기
for (int next : adj[v]) {
if (!visited[next]) {
stack.push(next);
}
}
}
}
}
💡 이번 학기 시험용 꿀팁!
- 순서의 차이: 재귀는 인접 리스트의 앞부터 방문하지만, 스택 방식은 스택에 차곡차곡 쌓았다가 위에서부터 꺼내기 때문에 인접 리스트의 뒤부터 방문하게 될 수도 있습니다 (코드 구현에 따라 다름).
1. 재귀(Recursion) → '시스템 스택' 사용
재귀 함수를 호출하면, 자바 가상 머신(JVM)이 내부적으로 관리하는 **시스템 스택(Call Stack)**에 정보를 쌓습니다.
- 특징: 이 영역은 크기가 매우 작게 고정되어 있습니다 (보통 1MB 내외).
- 문제: 미로가 너무 깊거나 그래프 노드가 수만 개라면, 이 작은 공간이 금방 꽉 차버립니다. 이게 바로 그 유명한 StackOverflowError입니다.
2. 직접 만든 Stack 객체 → '힙(Heap)' 사용
우리가 Stack<Integer> stack = new Stack<>()라고 코드로 직접 만든 스택은 힙(Heap) 메모리에 저장됩니다.
- 특징: 힙 영역은 시스템 스택보다 훨씬 크고 유연합니다. 컴퓨터 전체 메모리(RAM)를 거의 다 끌어다 쓸 수 있을 정도죠.
- 장점: 데이터가 수백만 개여도 램 용량만 충분하다면 에러 없이 버팁니다.
1. 스택(Stack) 영역: "지금 당장 하는 일"
- 성격: 아주 좁지만, 넣고 빼는 게 빛의 속도입니다.
- 용도: 현재 실행 중인 함수, 그 안의 잠깐 쓰고 버릴 숫자(지역 변수)들을 보관합니다.
- 특징: 함수가 끝나면 거기 있던 데이터는 마법처럼 사라집니다.
- 위험: 공간이 작아서, 재귀 함수가 너무 깊게 파고들면 금방 꽉 차서 터져버립니다. (StackOverflow)
2. 힙(Heap) 영역: "덩치 큰 데이터 창고"
- 성격: 아주 넓고 자유롭지만, 물건을 찾거나 정리하는 데 시간이 좀 걸립니다.
- 용도: 우리가 new 키워드로 만든 것들(new int[], new LinkedList(), new Stack())은 다 여기에 저장됩니다.
- 특징: 우리가 직접 만든 **스택(자료구조)**이나 **그래프(인접 리스트)**도 다 이 넓은 창고에 자리를 잡습니다.
- 장점: 창고가 워낙 커서 웬만해서는 터지지 않습니다.
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘) 26.3.16 (0) | 2026.03.16 |
|---|---|
| 알고리즘) 병합정렬 구현 (0) | 2026.03.15 |
| 알고리즘) 계수,기수 정렬 구현/복잡한 증감연산자 (0) | 2026.03.14 |
| 알고리즘)26.3.11 (1) | 2026.03.11 |
| 알고리즘)26.3.9 (4) | 2026.03.09 |