Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 우선순위큐
  • 스택
  • 유니온 파인드
  • 최소 스패닝 트리
  • 트라이
  • 수학
  • 브루트포스
  • 이분탐색
  • 동적계획법
  • 투포인터
  • 구현
  • 백준
  • 기하
  • KMP
  • 그래프
  • C++
  • 누적합
  • 정수론
  • 백트래킹
  • LCA
  • 문자열
  • 분할정복
  • SCC
  • 트리
  • 위상 정렬
  • UC++
  • 세그먼트 트리
  • 조합론
  • 큐
  • 정렬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 2263번 문제
공부 및 정리/백준 코드

[C++]백준 - 2263번 문제

2021. 9. 24. 16:30

2263번: 트리의 순회 (acmicpc.net)

 

2263번: 트리의 순회

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

www.acmicpc.net

 

2263번 : 트리의 순회


n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

입력


첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

 

 

출력


첫째 줄에 프리오더를 출력한다.

 

 


 

생각해 볼 점


후위 순회와 중위 순회의 결과물을 입력 받은 후, 실제 트리를 찾아내야 합니다.

 

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리 (donggoolosori.github.io)

 

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리

문제

donggoolosori.github.io

위의 링크에서 아주 잘 설명해주고 있습니다.

 

Root, Left, Right를 분할해주면서 맨 아래 Leaf 노드까지 내려갔다면, 트리가 어떻게 생겼는지 확인할 수 있습니다.

 

 

코드


#include <iostream>
#include <stack>
using namespace std;

//int 3개 짜리 구조체
struct thr
{
    int in_start;   //중위 순회 시작점
    int post_start;     //후위 순회 시작점
    int len;    //트리의 길이
};

int main() 
{
    int N;
    scanf("%d", &N);
    
    int *in = new int[N];
    int *post = new int[N];
    
    for(int i = 0; i < N; i++) scanf("%d", &in[i]);
    for(int i = 0; i < N; i++) scanf("%d", &post[i]);
    
    thr t;
    t.in_start = 0;
    t.post_start = 0;
    t.len = N;
    
    stack<thr> st;
    st.push(t);            
    while(!st.empty())
    {
        int in_start = st.top().in_start;
        int post_start = st.top().post_start;
        int len = st.top().len;
        
        //트리의 루트는 후위 순회의 가장 마지막 원소
        int root = post[post_start + len - 1];
        st.pop();
        
        //중위 순회에서 root를 찾아 좌, 우의 트리로 나눔
        for(int i = in_start; i < in_start + len; i++)
        {
            if(in[i] == root)
            {
                printf("%d ", root);
                thr left, right;
                
                //좌측 트리
                left.in_start = in_start;
                left.post_start = post_start;
                left.len = i - in_start;

                //우측 트리
                right.in_start = i + 1;
                right.post_start = post_start + left.len;
                right.len = in_start + len - 1 - i;

                //Left를 먼저 탐색해야 전위순회이므로 right부터 push
                if(0 < right.len) st.push(right);
                if(0 < left.len) st.push(left);
            }
        }
    }
    
    delete[] in;
    delete[] post;
	return 0;
}

 

그 외


개인적으로 정말 어렵게 생각했던 문제 중 하나입니다.

 

문제의 해결법을 생각하는 것 자체는 가능한데, 정말 그 방법이 맞는지 확신을 갖는 데에 시간이 걸렸던 것 같습니다.

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 4803번 문제  (0) 2021.09.25
[C++]백준 - 5639번 문제  (0) 2021.09.24
[C++]백준 - 14002번 문제  (0) 2021.09.22
[C++]백준 - 1450번 문제  (0) 2021.09.22
[C++]백준 - 1991번 문제  (0) 2021.09.20
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 4803번 문제
    • [C++]백준 - 5639번 문제
    • [C++]백준 - 14002번 문제
    • [C++]백준 - 1450번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바