전체 글 (168) 썸네일형 리스트형 백준 1949 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, �� www.acmicpc.net Tree Dp 문제 돌이켜생각해보면 tree는 참 재밌는 구석이 많은 자료구조같다. 지름 구하는 것도 참 신기하고... 양방향 간선이므로 어떤 노드를 root로 선택해도 된다. 그래서 생각하기 편하도록 1번 노드를 Root 노드로 잡았다. 어떤 분은 트리 순회하는 순서를 처음부터 vector에 저장하시던데, 내 코드는 그러진 않았다. 코드를 보면 이해가 더 잘되실 것 같다. /* 우.. 백준 3109 빵집 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 그리디 알고리즘 문제다. 처음엔 DP를 끝에서부터 하다가 실패해서 그리디 알고리즘으로 다시 했다. 아이디어는 '성공할 수 있는 경로는 누가 와도 성공할 수 있다.'이다. 예를 들어서 .xx.. ..x.. ..... ...x. ...x. 문제는 다음과 같은 예시를 제공한다. 첫 행의 네 번째 열의 .까지 도착하면 바로 성공할 수 있다. 출발점이 무엇이든간에 저기에 도착하면 성공한다. 마찬가지로 성공으로 갈 수 .. 백준 2263 트리의 순회 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net In-Order와 Post-Order를 보고 Pre-Order를 유추하는 문제다. Post-Order의 제일 마지막 Node가 그 Tree의 Root Node가 된다. 해당 문제는 다음과 같은 예시를 제공한다. In Order : 1 2 3 Post Order : 1 3 2 Post Order의 제일 마지막에 있는 2가 root 노드이다. 그러면 In order에서 2를 찾는다( 각 노드번호는 고유하다) In Order에서 2를 .. 이전 1 ··· 33 34 35 36 37 38 39 ··· 56 다음