군대에서_코딩하기_알고리즘_23

신태원·2021년 11월 19일
1

군대에서_코딩하기

목록 보기
24/30

드디어 DFS 로 넘어왔다. 그 말은 즉슨 이제 난이도가 꽤 높아지고,, 진짜 코딩테스트에 나올법한 것들을 배운다 라는 소리다..(맞나?) 아무튼 음.. 보다 집중해서 열심히 해보겠다!
오늘은 문제를 풀기보다는 DFS에 대한 기본적인 이해와 간단하게 코드로 구현해보는 시간을 갖겠다.


다음과 같은 이진트리를 전위순회, 중위순회, 후위순회로 탐색해보겠다.
솔직히 말하자면 학교과제같은 것을 할 때, 맨날 구글링 할줄만 알았지 실제로 구현해본적은 없었다.
근데 오늘 굉장히 신기한 것을 알았다.
우선 전위순회 코드이다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void D(int v){
    if(v>7) return;
    else{
    	cout<<v<<" ";
        //ㄴ이부분이 정말 중요함!
        D(v*2);        
        D(v*2+1);
    }
}

int main(){
    
    D(1);
    
}

별거 없이 정말 간단하다.
사실 전위, 중위, 후위 순회의 코드는 한줄만 빼고 완벽하게 똑같다.
저기 코드 중간의 v를 출력해주는 코드의 순서만 다르지, 다른 부분은 똑같다.
전위 순회의 코드는 위의 코드처럼, '재귀로 들어가기전' 에 vertex를 출력해준다.

그렇다면 중위 순회는

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void D(int v){
    if(v>7) return;
    else{
        D(v*2);
        cout<<v<<" ";
        D(v*2+1);
    }
}

int main(){
    
    D(1);
    
}

D(v*2) 를 한번 거치고나서 vertex를 출력해준다. 간단하게 정리하자면, vertex에 2를 곱하면 왼쪽 서브트리가 나오니까, 왼쪽 서브트리까지 일단 탐색을 해주고 v를 출력한다.
그렇다면 후위 순회는?

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void D(int v){
    if(v>7) return;
    else{
        D(v*2);
        D(v*2+1);
        cout<<v<<" ";
    }
}

int main(){
    
    D(1);
    
}

요렇게 D(v*2+1)까지 거치고나서 vertex를 출력해준다.
위에서 말했듯 vertex에 2를 곱해주면 왼쪽 서브트리가 나오지만, vertex에 2를 곱하고 1을 더해주면 오른쪽 서브트리가 나온다.
즉 왼쪽과 오른쪽 서브트리를 모두 탐색해주고나서 vertex를 출력해주는것이 바로 후위 순회이다!

정리

  • 전위 순회: 왼쪽 서브트리와 오른쪽 서브트리를 탐색하기 '전'에 일단 출력
  • 중위 순회: 왼쪽 서브트리를 탐색하고 출력, 그리고 오른쪽 서브트리 탐색
  • 후위 순회: 왼쪽과 오른쪽 서브트리를 모두 탐색하고, 그리고 출력
profile
일단 배우는거만 정리해보자 차근차근,,

0개의 댓글