스택
- 박스 쌓기에 비유
- 선입후출 구조 혹은 후입 선출 구조
큐
- 놀이공원 줄서기 비유
- 선입선출 구조
queue 보다는 deque 구조 사용
스택과 큐의 장점을 택한것이고 데이터를 넣고 뺴는 속도가 리스트 자료형에 디배 효율적이며 queue라이브러리를 사용하는 것 보다 간단하다
재귀함수
- 자기자신을 호출하는 함수
- 재귀함수 사용시 스택 자료 구조 이용
- 함수를 계속 호출했을 때 가장 마지막에 호출함 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨
재귀 함수 사용시 재귀함수가 언제 끝나고, 종료할지 꼭 명시
팩토리얼 예제
#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
int answer = 0;
int factorial(int n) {
// n = 1 인경우 재귀함수 멈춤
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int num;
cin >> num;
cout<<factorial(num);
}
DFS 스택 자료구조
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드를 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리,
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 - 2번 과정을 더이상 수행할 수 없을 때까지 반복
cf ) 방문 처리 - 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것
BFS
- 너비 우선 탐색
- 가까운 노드부터 탐색하는 알고리즘
- 선입선출 방식인 큐 자료구조 사용
- 인접한 노드를 반복적으로 큐에 놓도록 알고리즘 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게됨
- 탐색 시작 노드를 큐에 삽입하고 방문 처리함
- 큐에서 노드를 꺼내 해당 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
- 2번 과정을 더이상 수행할 수 없을 때까지 반복
너비 우선 탐색은 DFS보다 수행시간이 좋음
'Algorithm > C++' 카테고리의 다른 글
[개념] 최단 경로 구하기 (0) | 2020.10.13 |
---|---|
[개념] 다이나믹 프로그래밍(동적계획법) (0) | 2020.10.11 |
[개념] 이진탐색 (0) | 2020.10.09 |
[개념] 정렬 알고리즘 (0) | 2020.10.01 |