- 선형자료구조
: 현재 데이터와 다음 데이터가 1:1로 구성된 자료 구조
- 배열: Linkedlist - 데이터 하나가 하나를 link
=> 배열 ,Linkedlist로 만들 수 있는 자료 구조 Stack (LIFO) , Queue
-비선형 자료구조
✔Graph
- 그래프는 정점 와 간선로 이루어진 자료구조
각 정점(Vertex)들이 간선(Edge)들로 연결되어, 연결된 정점 간의 관계를 표현할 수 있는 자료구조
-방향성
양방향 그래프
방향 그래프
-사이클
nocycle
cycle
nocycle 이면서 방향이 있는 구조 ( 1: N) => Tree
- 그래프 구현 (인접 행렬)
2차원 배열을 이용한다.
노드수가 N개 일때, N x N의 int 행렬 또는 boolean 행렬을 만들어서, 연결 상태 값을 설정한다.
matrix[ i ][ j ] == true 라면 i -> j로의 간선이 있다는 뜻이다. (int 행렬의 경우 1 = true, 0 = false)
- 그래프에서 9*9는 / 원소 *인접정보
행을 의미 하는 것: 원소
열이 의미 하는 것: 인접정보
Bollean으로
True면 인접(연결) 됐다! => 1
False면 비인접(비연결) 됐다! => 비용0
- 그래프 탐색
1. DFS : 깊이 우선 탐색 (Depth First Search)
그래프의 모든 노드를 방문하는 완전 탐색 방식이다.
임의의 시작노드에서 출발하여 한쪽 분기를 정해서 최대 깊이까지 탐색을 마친 후,
다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
꺼내오면서 방문처리가 된다.
- 재귀함수 또는 Stack 자료구조를 이용한다.
*Stack 자료구조
// 깊이 우선 탐색 (DFS)
public static void DFS(int node) {
// 깊이 우선 탐색을 위한 스택을 선언한다.
Stack<Integer> stack = new Stack<Integer>();
// 스택에 탐색할 노드를 추가한다.
stack.push(node);
// 스택에 더 이상 탐색할 노드가 없을 때까지 탐색하기
while (!stack.isEmpty()) {
// 탐색할 노드를 스택에서 추출
int current = stack.pop();
// 방문하지 않은 노드라면
if (!visited[current]) {
// 방문 처리하고
visited[current] = true;
// 추출한 노드에 대한 처리
System.out.printf(" %c", current + 65);
// 현재 노드의 인접된 노드에 대한 방문 시도
for (int adj = N - 1; adj >= 0; adj--) { // 끝에서부터 처음까지 방문 시도 (재귀와 같게 하기 위해)
// 방문한 적이 없고 인접되어 있다면
if (!visited[adj] && map[current][adj]) {
// 스택에 추가하기
stack.push(adj);
}
}
}
}
}
*재귀 함수를 이용한 DFS
- stack을 이용하여 함수 콜에 대한 관리를 하기 때문에
* 재귀 함수를 이용하면 stack 객체를 생성할 필요가 없다.
=> 재귀 호출 자체가 스택의 역할
-기저 조건
* DFS 에서 기저 조건은 따로 필요하지 않으며,
for 문을 통해 모든 인접 노드를 방문하고 재귀적으로 처리하는 방식으로 작동
=> stack에서 바로 넣고 빼는 효과를 가지고 있음
private static void DFS(int cur) {
// 인자로 전달된 cur 노드가 stack에서 꺼내온 효과이므로
// 방문 처리
visit[cur] = true;
// 현재 노드에 대한 처리
System.out.printf("%c->", cur + 'A');
// 현재 노드의 인접된 노드에 대한 방문 시도
for (int ad = 0; ad < N; ad++) {
// 방문한 적이 없고 인접되어 있다면
if (!visit[ad] && map[cur][ad]) {
// 스택에 추가하기 (재귀 호출)
DFS(ad);
}
}
}
2. 너비 우선 탐색(BFS, Breadth-First Search)
먼저들어온걸 먼저 처리하기 때문에 Queue를 이용하여 탐색
순서대로 넣기 때문에 넣을 때 방문처리가 진행된다. (DFS 보다 속도가 빠름)
- BFS 구현 알고리즘
- 루트노드에서 시작한다.
- 루트노드와 인접하고 방문된적 없고, 큐에 저장되지 않은 노드를 Queue에 넣는다.
- Queue에서 dequeue하여 가장 먼저 큐에 저장한 노드를 방문한다.
* 너비 우선 탐색 (BFS) 코드
/**
* 너비 우선 탐색 (BFS)
*/
private static void BFS(int cur) {
// 너비 우선 탐색을 위한 큐 선언
Queue<Integer> q = new ArrayDeque<>();
// 첫 노드 방문 처리
visited[cur] = true;
// 큐에 첫 노드 추가
q.offer(cur);
// 큐에 더 이상 노드가 없을 때까지 탐색
while (!q.isEmpty()) {
// 탐색할 노드를 큐에서 추출
cur = q.poll();
// 노드에 대한 처리 (노드 출력)
System.out.printf("%c->", cur + 'A');
// 현재 노드의 인접한 모든 노드들에 대해 방문 시도
for (int ad = 0; ad < N; ad++) {
// 인접하고, 방문한 적이 없으면
if (map[cur][ad] && !visited[ad]) {
// 방문 처리하고 큐에 추가
visited[ad] = true;
q.offer(ad);
}
}
}
}✔ Tree
: 비선형(non-linear), 계층적 자료구조
그래프의 탐색 방법을 알고 => 일부 그래프의 특성을 가진 것을 빼면 트리
- nocycle 이면서 방향이 있는 구조 ( 1: N) => Tree
1:N 관계에 부모에서 자식으로 내려가는 방향이 있음 위에서 아래로 내려오는 구조
- 최고 레벨을 알면 공간 크기를 알수 있다
- 차수가 여러개인 경우 Linkedlist로 표현
용어
루트(root) : 트리 구조 중 최상위에 존재하는 노드 (1을 가리킴)
노드(node) : 트리에서 각각의 구성 요소
레벨(level) : 트리에서 각각의 층을 나타내는 단어(루트 노드 : 0)
형제 노드(sibling) : 같은 레벨의 노드
간선(edge) : 노드와 노드를 연결하는 선
부모 노드(parent node) : 한 노드를 기준으로 바로 상위에 존재하는 노드
자식 노드(child node) : 한 노드를 기준으로 바로 하위에 존재하는 노드
높이(heigh) : 트리 중 최고 레벨
리프노드: 자식이 없는 노드 마지막 레벨의 노드
- 이진트리
: 각 노드가 최대 2명의 자식을 가지는 트리이다.
노드 하나가 최대 2개의 노드를 갖는다.
-> 최대 2개라는 것은 자식이 없을 수도(0개) 있고 1개만 있을 수도 있다는 것
최대 두개이기 때문에 1번부터 차례로 저장할 때
✅ 왼쪽은 항상 * 2 / 오른쪽은 * 2+1 !!!!
- 완전 이진 트리(Complete Binary Tree)
: 각 노드가 최대 2개의 자식 노드를 갖는 이진 트리로
마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.
- 또한, 최하단 레벨의 노드는 좌측만 채워져 있거나, 좌측 우측이 모두 채워진 상태
- heap, 세그먼트 트리는 완전 이진 트리를 이용해서 구현
- 이진 트리 순회
트리를 탐색할 때 끝까지 갔다가 다시 돌아오고 stack으로
DFS Depth First Search
1. 전위 순회 (Preorder)
루트 노드를 먼저 방문하고, 왼쪽 자식 트리를 전위 순회하고, 오른쪽 자식 트리를 전위 순회
NLR (Node, Left, Right) : 루트-왼쪽-오른쪽 순서
100 - 200 - 400 - 800 - 500 - 300 - 600 - 700
// 전위 순회 (Pre-order Traversal) - 자기 자신을 먼저 처리
public void preOrder(int current) {
// current가 마지막 인덱스 이하일 때만 실행
if (current <= lastIndex) {
// 현재 노드 방문 처리
System.out.print(nodes[current] + " ");
// 왼쪽 자식 노드 방문 처리
preOrder(current * 2);
// 오른쪽 자식 노드 방문 처리
preOrder(current * 2 + 1);
}
}
2. 중위 순회 (Inorder)
왼쪽 자식 트리를 중위 순회하고, 루트 노드를 방문하고, 오른쪽 자식 트리를 중위 순회
LNR (Left, Node, Right) : 왼쪽 자식 노드 → 현재 노드 → 오른쪽 자식 노드
800 - 400 - 200 - 500 - 100 - 600 - 300 - 700
public void inOrder(int current) {
if (current <= lastIndex) {
// 왼쪽 자식노드 방문처리
inOrder(current * 2);
// 현재 노드 방문처리
System.out.print(nodes[current] + " ");
// 오른쪽 자식노드 방문처리
inOrder(current * 2 + 1);
}
}
3. 후위 순회 (Postorder)
왼쪽 자식 트리를 후위 순회하고, 오른쪽 자식 트리를 후위 순회하고, 루트 노드를 방문
LRN (Left, Right, Node) : 왼쪽 자식 노드 → 오른쪽 자식 노드 → 현재 노드
800 - 400 - 500 - 200 - 600 - 700 - 300 - 100
// 후위 순회 (Post-order Traversal) - 왼쪽 자식 → 오른쪽 자식 → 자기 자신 순으로 처리
public void postOrder(int current) {
// current가 마지막 인덱스 이하일 때만 실행
if (current <= lastIndex) {
// 왼쪽 자식 노드 방문 처리
postOrder(current * 2);
// 오른쪽 자식 노드 방문 처리
postOrder(current * 2 + 1);
// 현재 노드 방문 처리
System.out.print(nodes[current] + " ");
}
}
자료구조를 이용한 문제 풀이 ❗❗❗
BFS
- 가중치가 없는 map에서 s ->e 최소 비용(최소거리)를 구할 때 o(n)
- 특정 위치에서 점진적으로 퍼져나가는 문제
DFS
- S->E가는 모든 방법의 수를 구할 때 /최대
다익스트라
- 가중치가 있는 map에서 s ->e 최소 비용(최소거리)를 구할 때 o(n)
프로이드워셜
- 모든 노드들의 최소 비용 구할 때 O(N^3)
- 시작 좌표에서 끝좌표까지 가는 최소거리 비용을 찾고 싶음
A->B까지 최소비용을 구하는 문제
- BFS O(N) -
: 인접된 곳을 쭉 따라가다 먼저 도착한 것이 최소 비용
- DFS O(N^2)
:재귀로 쭉 진행 1번째가 최소비용이 아님 => 정보 저장 후 다음 번 => 최소비용을 찾을 때까지 다가봄
가중치 없이 최소비용 => BFS!!!!!!!!
가중치 있을 때는 다익스트라 // 가중치 있을 때 BFS, DFS 시간 복잡도는 3^98^98 ⬆⬆⬆⬆
Start에서 end까지 모든 가지수를 구하는 것은?
둘다 가지수는 갖지만
- DFS가 가장 빠름 / 재귀로 해서 인자를 만들 필요가 없다
- BFS는 객체를 만들었다 빼는 비용이 듦
- 완전탐색
-search
Squencial Search
=> 이진 탐색 (정렬된 데이터만) / Sliding Window , Two Pointer
- 경우의 수
순열, 조합, 부분집합
=> 재귀 (BackTracking)
=>그래도 시간이 터진다면 DP: 경우의 수 , count세기
조합 이항계수
- 그래프.트리
DFS => 재귀 (BackTracking)
BFS
'Cs기본지식 > 알고리즘' 카테고리의 다른 글
| 자바 알고리즘 신장 트리(Spanning Tree) 알아보기 (1) | 2025.02.25 |
|---|---|
| 자바 알고리즘 Graph 추가 이해하기 (1) | 2025.02.21 |
| 자바 알고리즘 Subset 알아보기 (0) | 2025.02.18 |
| 자바 알고리즘 /순열과 조합 (0) | 2025.02.17 |
| 정렬 알고리즘 이해하기 : 기본 구조 및 종류 (0) | 2025.02.17 |