스택의 구현
스택을 구현하기 위해서 필요한 자료구조 - 자료를 선형으로 저장할 저장소. 배열을 이용하여 스택 구현이 가능하다
스택의 연산
삽입(push) - 저장소에 자료를 저장한다
삭제(pop) - 저장소에서 자료를 꺼낸다
isEmpty - 스택이 공백인지 아닌지를 확인한다
peek - 스택이 top에 있는 item을 반환한다
static int st[] = new int [10];
int top = -1; // 스택에 마지막 삽입된 원소의 위치를 가리킴
st[++top] = 1; // 단순하게 구현한push
st[top--] // 단순하게 구현한 pop
// 간단하게 push 구현
void push(int x) {
if (++top > st.length) {
// overflow
} else {
st[top] = x;
}
}
// 간단하게 pop 구현
int pop() {
if (top < 0) {
// underflow
return -1;
} else {
return st[top--];
}
}
스택의 응용: 괄호 검사
괄호의 짝이 맞는지 검사해보는 코드를 스택으로 구현해보는 예제이다
괄호를 검사하는 알고리즘은
- 문자열을 조사하면서 왼쪽 괄호를 만나면 push하고 오른쪽 괄호를 만나면 pop하여 짝이 맞는지 확인한다
- 마지막까지 조사 후 스택에 괄호가 남아있으면 안 된다
다음은 스택을 이용하여 간단하게 '(', ')'에 대해서만 괄호검사를 구현해보았다
괄호의 짝이 맞는지 아닌지 검사하는 코드이다
// "( )( )((( )))"에 대하여 괄호의 짝이 맞는지 검사
char stack[] = new char[100];
int top = -1;
char[] arr = "( )( )((( )))".toCharArray();
// 검사를 하는 함수
boolean check_matcharrg(char arr[])
{
for (intt i = 0; i < arr.length; i++)
{
switch (arr[i])
{
case '(': // 열린 괄호는 push
stack[++top] = arr[i];
break;
case ')': // 닫힌 괄호인 경우 빈 스택인지 확인 후 pop
if (top == -1) return false;
top--;
break;
}
}
if (top != -1) return false; // 스택이 비어있는지 확인
return true;
}
관련 문제 - swea1218 괄호 짝짓기
스택의 응용: DFS(깊이 우선 탐색)
시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정범으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법이다
가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 LIFO 구조의 스택 사용한다
DFS 방식
- 시작 정점 v를 결정하여 방문한다
- 정점 v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 정점 w를 방문한다
- 방문하지 않은 정점이 없으면 탐색의 방향을 바꾸기 위해 스택을 pop하여 가장 마지막 방문 정점 v로 반복한다
- 스택이 공백이 될 때까지 위의 과정 반복한다
재귀를 이용한 DFS
함수의 재귀 호출을 이용하여 DFS를 구현한 예제이다
int[][] G = new int[10][10]; // 인접 행렬
boolean[] visited = new boolean[10]; // 방문한 정점인지 검사하기 위한 배열
void DFS_Recursive(int v) {
if (!visited[v]) {
visited[v] = true; // 방문 안한 경우 방문으로 표시
for (int w = 0; w < G[v].length; w++) {
if (G[v][w] == 1) { // 인접행렬들 중에서
if (!visited[w]) { // 방문 안한 정점 탐색
DFS_Recursive(w);
}
}
}
}
}
반복을 이용한 DFS - 스택
스택을 이용하여 DFS를 구현한 예제이다
int[][] G = new int[10][10]; // 인접 행렬
boolean[] visited = new boolean[10]; // 방문한 정점인지 검사하기 위한 배열
Stack<Integer> st = new Stack<>(); // DFS에 사용할 스택
void DFS_Iterative(int v) {
st.push(v); // 시작 정점
while (!st.isEmpty()) { // 스택이 빌 때까지 반복
v = st.pop(); // 스택에서 item 하나 꺼내서
if (!visited[v]) {
visited[v] = true; // 방문 안한 경우 방문으로 표시
for (int w = 0; w < G[v].length; w++) {
if (G[v][w] == 1) { // 인접행렬들 중에서
if (!visited[w]) { // 방문 안한 정점 탐색
st.push(w);
}
}
}
}
}
}
반복을 이용한 DFS - 배열을 이용한 스택
배열을 이용하여 DFS를 구현한 예제이다
int[][] G = new int[10][10]; // 인접 행렬
boolean[] visited = new boolean[10]; // 방문한 정점인지 검사하기 위한 배열
int[] st = new int[10]; // DFS에 사용할 스택 배열
int top = -1;
void DFS_Iterative(int v) {
st[++top] = v; // 시작 정점
while (top != -1) { // 스택이 빌 때까지 반복
v = st[top--]; // 스택에서 item 하나 꺼내서
if (!visited[v]) {
visited[v] = true; // 방문 안한 경우 방문으로 표시
for (int w = 0; w < G[v].length; w++) {
if (G[v][w] == 1) { // 인접행렬들 중에서
if (!visited[w]) { // 방문 안한 정점 탐색
st[++top] = w;
}
}
}
}
}
}
관련 문제 - swea1219 길찾기
DFS를 개선해보자
위의 방법의 경우 불필요한 탐색이 많다
예를 들어, 그래프가 다음과 같은 경우
인접 행렬은 다음과 같이 나타낼 수 있다
int[][] G = {
{0, 1, 1, 0, 0, 0, 0}, // 1번 정점의 인접정점
{1, 0, 0, 1, 1, 0, 0}, // 2번 정점의 인접정점
{1, 0, 0, 0, 0, 0, 1}, // 3번 정점의 인접정점
{0, 1, 0, 0, 0, 1, 0}, // 4번 정점의 인접정점
{0, 1, 0, 0, 0, 1, 0}, // 5번 정점의 인접정점
{0, 0, 0, 1, 0, 0, 1}, // 6번 정점의 인접정점
{0, 0, 1, 0, 0, 1, 0} // 7번 정점의 인접정점
};
1번 정점의 경우 인접하는 정점은 2번, 3번 정점이 전부이다
하지만 위에서 설명한 예제로 인접하는 정점(G[v][w] == 1)을 찾기 위해서는 처음부터 끝까지 인접 행렬을 탐색해야 한다
차수를 적용한 인접 행렬
기존 인접 행렬에 차수를 저장할 인덱스를 추가한다
0번 인덱스에 각 정점의 인접 정점의 개수를 넣고
차례대로 어느 정점과 인접해 있는지를 넣는다
int G[][] = {
{0, 0, 0, 0, 0, 0, 0, 0},
{2, 2, 3, 0, 0, 0, 0, 0}, // 1번 정점의 인접정점 개수와 인접정점들
{3, 1, 4, 5, 0, 0, 0, 0}, // 2번 정점의 인접정점 개수와 인접정점들
{2, 1, 7, 0, 0, 0, 0, 0}, // 3번 정점의 인접정점 개수와 인접정점들
{2, 2, 6, 0, 0, 0, 0, 0}, // 4번 정점의 인접정점 개수와 인접정점들
{2, 2, 6, 0, 0, 0, 0, 0}, // 5번 정점의 인접정점 개수와 인접정점들
{3, 4, 5, 7, 0, 0, 0, 0}, // 6번 정점의 인접정점 개수와 인접정점들
{2, 3, 6, 0, 0, 0, 0, 0} // 7번 정점의 인접정점 개수와 인접정점들
};
기존 반복 코드
for (int w = 0; w < G[v].length; w++) {
if (G[v][w] == 1) { // 인접행렬들 중에서
if (!visited[w]) { // 방문 안한 노드 탐색
st.push(w);
}
}
}
바뀐 코드
for (int w = 1; w < G[v][0]; w++) { // 차수까지만 반복하면 된다
if (G[v][w] == 1) {
if (!visited[w]) {
st.push(w);
}
}
}
이렇게 하면 모든 행렬을 탐색할 필요 없이
해당 차수만큼만 탐색을 하면 되므로 불필요한 낭비를 줄일 수 있다
'프로그래밍 > 자료구조&알고리즘' 카테고리의 다른 글
위상 정렬을 구하는 두 가지 방법 (0) | 2022.02.08 |
---|---|
스택 - 후위표기식 (0) | 2022.02.07 |
이진 트리의 종류 (0) | 2021.10.12 |
Direct Access Table과 Hash Table (0) | 2021.10.05 |
더블리 링크드 리스트 연산의 시간 복잡도 (0) | 2021.10.02 |