탐색(Search)이란?
많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
대표적 그래프 탐색 알고리즘 = DFS/BFS
자료구조
스택
먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)
입구가 출구가 동일한 형태
구현 예제
#include <bits/stdc++.h>
using namespace std;
stack<int> s;
int main(void){
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
// 스택의 최상단 원소부터 출력
while(!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
}실행 결과
1 3 2 5
큐
먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
입구와 출ㄹ구가 모두 뚫려 있는 터널과 같은 형태로 시각화
구현 예제
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(void){
q.push(5);
q.push(2);
q.push(3);
q.push(7);
q.pop();
q.push(1);
q.push(4);
q.pop();
// 스택의 최상단 원소부터 출력
while(!s.empty()) {
cout << s.front() << ' ';
q.pop();
}
}실행 결과
3 7 1 4
재귀 함수(Recursive Function)
자기 자신을 다시 호출하는 함수
단순 구현 예제
#include <iostream>
using namespace std;
void recursive_function(){
cout << "recursive_function ";
recursive_function();
}
int main(){
recursive_function();
}실행 결과
종료 조건
재귀 함수를 문제 풀이에 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
예제
#include <iostream>
using namespace std;
void recursive_function(int i){
if (i==10)
return;
cout << "start " << i << " to " << i+1 << "recursive_function\n";
recursive_function(i+1);
cout << i << "end recursive_function\n";
}
int main(){
recursive_function(1);
}실행 결과
재귀 함수 사용의 유의 사항
-
재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용하기!
-
모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
-
재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
-
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
예제
팩토리얼
- n! = 1 x 2 x 3 x ... x (n-1) x n
- 0! = 1
- 1! = 1
반복문 & 재귀
#include <iostream>
using namespace std;
int factorial_iterative(int n){
int result = 1;
for(int i=1; i<=n; i++)
result *=i;
return result;
}
int factorial_recursive(int n){
if (n<=1) // n이 1이하인 경우 1을 반환
return 1;
// n! = n * (n-1)!
return n * factorial_recursive(n-1);
}
int main(){
cout << factorial_iterative(5) << '\n';
cout << factorial_recursive(5) << '\n';
}- 실행 결과
120
120최대공약수 계산 (유클리드 호제법)
유클리드 호제법
- 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다.
- 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
- 재귀함수로 작성할 수 있다.
#include <iostream>
using namespace std;
int gcd(int a,int b){
if(a%b == 0)
return b;
else
return gcd(b, a%b);
}
int main(){
cout << gcd(192, 162);
}- 실행 결과
`6
DFS(Depth-First Search)
- 깊이 우선 탐색 = 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀 함수) 이용
동작 과정
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고, 방문 처리를 한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. - 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.
DFS 소스 코드 예제
#include <bits/stdc++.h>
using namespace std;
bool visited[9];
vector<int> graph[9];
void dfs(int x){
// 현재 노드를 방문 처리
visited[x] = true;
cout << x << ' ';
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i=0; i<graph[x].size(); i++){
int y = graph[x][i];
if (!visited[y]) dfs(y);
}
}
int main(void){
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
dfs(1);
return 0;
}실행 결과
1 2 7 6 8 3 4 5
BFS(Breadth-First Search)
- 너비 우선 탐색 = 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조 이용
동작 과정
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
- 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
BFS 소스 코드 예제
#include <bits/stdc++.h>
using namespace std;
bool visited[9];
vector<int> graph[9];
// BFS 함수 정의
void bfs(int start) {
queue<int> q;
q.push(start);
// 현재 노드를 방문 처리
visited[start] = true;
// 큐가 빌 때까지 반복
while(!q.empty()) {
// 큐에서 하나의 원소를 뽑아 출력
int x = q.front();
q.pop();
cout << x << ' ';
// 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for(int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if(!visited[y]) {
q.push(y);
visited[y] = true;
}
}
}
}
int main(void) {
// 노드 1에 연결된 노드 정보 저장
graph[1].push_back(2);
graph[1].push_back(3);
graph[1].push_back(8);
// 노드 2에 연결된 노드 정보 저장
graph[2].push_back(1);
graph[2].push_back(7);
// 노드 3에 연결된 노드 정보 저장
graph[3].push_back(1);
graph[3].push_back(4);
graph[3].push_back(5);
// 노드 4에 연결된 노드 정보 저장
graph[4].push_back(3);
graph[4].push_back(5);
// 노드 5에 연결된 노드 정보 저장
graph[5].push_back(3);
graph[5].push_back(4);
// 노드 6에 연결된 노드 정보 저장
graph[6].push_back(7);
// 노드 7에 연결된 노드 정보 저장
graph[7].push_back(2);
graph[7].push_back(6);
graph[7].push_back(8);
// 노드 8에 연결된 노드 정보 저장
graph[8].push_back(1);
graph[8].push_back(7);
bfs(1);
}실행 결과
1 2 7 6 8 3 4 5
