Today I learned : DFS, recursion
퇴사하고 서울에서 계속 약속이나 나가고 누워있고.. 뭐 그랬다. 연휴 동안 알고리즘 진도 많이 빼야 한다!!!!
오늘 할 일
바킹독 DFS- 바킹독 재귀 -> 진행중.. 너무 많이 남아서 밤샐듯 ㅎ
- 바킹독 백트래킹
- 워크북 스택 완료
- 워크북 큐 완료
- 워크북 덱 완료
- 드림핵 크립토 문제 풀던 거 완료하기
- 자정 지나면 티스토리 임시 글 발행하기
바킹독의 실전 알고리즘 : DFS
DFS : 다차원 배열에서 각 칸을 방문할 때 깊이를 우선순위로 BFS : 다차원 배열에서 각 칸을 방문할 때 너비를 우선순위로
DFS 방법
- 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
- 스택에서 원소를 꺼ㅐ서 상하좌우로 인접한 칸에 대해 3번을 진행
- 이전에 방문했다면 continue;, 처음으로 방문했다면 표시 남기고 스택에 삽입
- 스택이 빌 때까지 2번을 반복 -> 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 O(n)
구현
구현은 내가 일단 시도해보자.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[502][502]; // 0,1로 정의된 배열
vool vis[502][502];
int n=7, m=10;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int,int>> s;
vis[0][0]=1;
s.push(0,0);
while(!s.empty()){
pair<int,int> cur=s.top(); s.pop();
cout<<"(" <<cur.X<<","<<cur.Y<<")-> ";
for(int dir=0;dir<4;dir++){
int nx=cur.X+dx[dir];
int ny=cur.Y+dy[dir];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(vis[nx][ny] || board[nx][ny]!=1) continue;
vis[nx][ny] =1;
s.push({nx,ny});
}
}
}
BFS와의 차이
이미지 연상으로 기억하는 게 좋을 것 같다. BFS는 상하좌우로 동심원 생기듯이 방문한다면, DFS는 일단 직진해서 한 방향 파고 그다음 방향 파듯이 방문한다.
또한, “현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재 보는 칸보다 1만큼 더 떨어져있다”는 BFS 성질이 DFS에서는 성립하지 않는다. 거리 측정은 BFS만이 가능하니 웬만하면 BFS로 푸는 것이 좋다(DFS는 추후에 그래프와 트리 자료구조에서 나온다)
바킹독의 실전 알고리즘 : 재귀
재귀 : 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘 (recursion)
N부터 1까지 출력하는 함수
int print_n(int n){
if(n==0) return 0;
cout<<n;
return print_n(n-1);
}
int main(void){
print_n(n);
}
1부터 N까지의 합을 구하는 함수
int sum_n(int n, int sum){
if(n==0) return sum;
return sum_n(n-1,sum+n);
}
int main(void){
int sum=0;
cout<<sum_n(n,sum);
}
더 직관적인 재귀는 아래와 같다.
int sum_n(int n) {
if (n == 1) return 1;
return n + sum_n(n - 1); // n 더하기 (1부터 n-1까지의 합)
}
물론 sum은 그냥 수열 공식으로 쓰는 것이 좋다. -> {n(n+1)}/2
재귀 함수의 조건
void func1(int n){
if(n==0) return 0; // 특정 조건에는 종료 (base condition)
cout<<n<<' ';
func1(n-1);
}
결국에는 base condition으로 수렴해야 한다. 이렇지 않으면 무한루프가 될 수 있다.
그리고 재귀는 코드가 간결하지만 메모리/시간이 많이 소모된다. 모든 재귀 함수는 재귀 구조 없이 반복문으로 만들 수 있다. 재귀 없이 구현했을 때 너무 복잡해지는 경우는 재귀로 구현하는 것이 좋다.
- 함수의 정의
- base condition
- recursion 식