DFS (깊이우선 탐색) 문제를 풀다보면, 재귀함수와 스택을사용해 문제를 많이 풀게됩니다.
그렇다면, 재귀함수와 스택의 차이점은 무엇일까??
결론부터 말하자면 둘다 결과물은 같습니다. 하지만 돌아가는 방식이 조금 다를뿐이죠
재귀함수의 작동원리
먼저 재귀함수란, 자기 자신을 호출하는겁니다. Alg함수안에 Alg함수를 무한으로 호출하는것이죠.
무한으로 호출하기때문에 반드시, 탈출 조건을 쓰셔야합니다.
재귀함수는 먼저들어온 함수의 명령을 실행하기에, 맨 앞번호부터 수직탐색을합니다
|
1
2
3
4
5
6
7
|
public void Algorism (int a){
if(a==0) return 0;
.
.
.
return Algorism(a-1);
}
|
cs |
이렇게 말이죠
맨 앞에있는것부터 수직 탐색합니다. 만약 푸는 문제가 4번을 찾는거라면 꽤나 이득을보겟죠?
스택의 작동원리
스택은 나중에 들어온 함수부터 먼저 처리합니다. 즉 뒷 번호부터 수직 탐색을합니다.
음식찌꺼기가 있는 접시들이 쌓여잇는걸 설거지 하려면 윗접시부터 닦지않습니까?
같은 원리입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public void Algorithm (int a){
Stack<Integer> stack = new Stack<>();
.
.
.
while(!stack.empty()){
.
.
.
}
return;
}
|
cs |
스택으로 dfs 문제를 풀때는 while을 사용하니, 탈출조건을 꼭 쓰셔야합니다.
작동은 아래 그림처럼 합니다.
만약 3번 위치를 찾는다고하면 연산을 덜하니 이득을 보겟죠?
그래서 무엇을 쓰나?
만약 DFS문제를 풀때는 둘중 아무거나 써도 상관이없습니다. 다루기 쉬운걸 쓰시는게 맞습니다.
DFS는 어쨋든 완전탐색이라서 탐색하고싶은 목표가 앞에나올수 있고 뒤에 나올수있기때문에
둘중 무엇이 속도가 빠른가는 따지는건 그냥 '운'입니다.
다만, 가독성은 재귀가 좀 더 좋다고 생각합니다.
그렇다고, 스택과 재귀함수가 같다 라고 생각하는 위험한 생각은 금물!
스택의 특징을 써서 스택을 쓰는게 더 좋은 문제가있고, 재귀를 써서 풀면 더 쉽고 가독성이 좋은 문제가 있으니
둘 다 아시는게 좋습니다. 사실 프로그래밍할때 몰라도 대는건 하나도없습니다. 많이 아는게 좋죠
'알고리즘 > 알고리즘 지식' 카테고리의 다른 글
| 자료구조: PriorityQueue(Heap) (0) | 2021.09.27 |
|---|