개요

백준 문제 1967번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 2시간
https://www.acmicpc.net/problem/1967

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

계획한 풀이법

이전에 푼 문제와 사실상 똑같은 문제였다.
비교대상은 무엇이든 상관없으니 1로 시작하도록 하고 가장 가중치가 큰 정점을 찾아
그 정점을 DFS하면 최대 길이가 나오게 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

#include <iostream>
#include <vector>
#include <stack>



using namespace std;
const int MAX = 10001;
//메모리 초과
vector<pair<int,int>> graph[MAX];
int N = 0;
bool visit[MAX];
int maxCost = 0;

int DFS(int startV)
{
	stack<pair<int,int>> s;
	s.push(make_pair(startV,0));
	int curV = 0;
	bool allVisited = false;
	int curCost = 0;
	int maxV = 0;

	while(s.size() != 0)
	{
		curV = s.top().first;
		if(!visit[curV])
		{
			curCost += s.top().second;

		}
		visit[curV] = true;
		allVisited = true;
		if(maxCost < curCost)
		{
			maxCost = curCost;
			maxV = curV;
		}
		for(int j=0;j<graph[curV].size();j++)
		{
			int nextV = graph[curV][j].first;
			if(visit[nextV])
			{
				continue;
			}
			int prevCost = graph[curV][j].second;
			s.push(make_pair(nextV, prevCost));
			allVisited = false;
			break;
		}
		if(allVisited)
		{
			curCost -= s.top().second;
			s.pop();
		}

	}
	return maxV;



}

void connectEdge(int v,int e,int cost)
{
	//cout << "V , E 연결\n";
	//cout << v << "," << e << "\n";

	graph[v].push_back(make_pair(e,cost));
	graph[e].push_back(make_pair(v,cost));

}

void init()
{
	cin >> N;
	int v,edge,cost;
	for(int i=0;i<N-1;i++)
	{
		cin >> v >> edge >> cost;
		connectEdge(v,edge,cost);
	}

}

void solve()
{
	int maxV = DFS(1);
	fill_n(visit,MAX,0);
	DFS(maxV);
	cout << maxCost;
}


int main()
{
	init();
	solve();




}

느낀 점

• 2시간 넘겨서 참고한 풀이가 바로 생각났는데 이래서는 내가 푼게 아닌 것 같은 기분이 들었다.
  하지만 여러가지 시도를 해보니 이 방법이 맞구나 체감이 되어서 곧 바로 풀었다.
  또 고집이 문제 풀이 시간을 눌렸다.
• 스스로가 생각한 풀이방법으로 풀린다면 얼마나 좋을까?
  하지만 그렇지 않은 경우가 앞으로 엄청나게 많을 것이다.
  그렇다고 기죽을 필요는 없는 것 같다.
  당연히 내가 잘하는 사람이 되기 전까지는 그 사람들의 뒷모습을 보는 것이 당연한 것이다.
  불만있으면 내가 잘하는 사람이 될때까지 더 열심히 해야 한다
• 지금은 결과주의자가 되자 문제를 빠르게 맞추는 것에만 집중하자
  아직은 직관을 배워야 할 것 같다.

i write this post at 1107.

About Current Study

have to write more oftenly

currently i’m doing CRF feature things

current problem is that if there is so many data that memory would be down..

how to solve this problem..well i thing this problem is have to access with engineering concept

first, i should understand feature is how interactive each other in inference level and analysis…

What i have felt

with those month i get those things:

1.nobody but you is the person that knows your code so you have to get into your code perfectly and you should love your code

2.hard work is perfectly loveable because it is only thing that express you perfectly

3.just start thing every day that making you a better person even maybe it’s small.

4.just don’t care about other eyes just focus inside of you.

5.mostly human are not good at multi task it doesn’t help your concentration you should have to watch a one thing at one time

6.more fun and impressive more you know.

7.always try to be your 100%, always say why and more to yourself

8.always find fun whatever you do, always have art inside heart.

CRF Flowchart

will shown flowchart is CRF split by 3 part:
get training data part,
get feature part,
optimize part
some optimze and specific mathmatical part was omitted

FlowChart

following part is FlowChart

• CRF outline

  
  this flowchart shows splitted part

• CRF read corpus

  
  this flowchart shows training data way

• CRF feature scan

  
  this flowchart shows how to make feature

• CRF optimize

  
  this flowchart shows optimize methods very simplely
  following:more specific but also there is no mathmatical explaination
  

furture..

continuing to study more specific parts…

210106 reserch object

• CRF that can train and inference with kor

  • it can completed by adding word, emjeol tokenizer
  • it have specific needed input data set
  • english, numbers are regarded as one representation character

• CRF that added mini batch batch so it can train with large data set

  • it has to be with lots of modify CRF code
  • it contains that each mini batch has its features that used by each mini batch

• ok with git

  • especially branch, merge, requests etc

• code with TDD method

  • it is good for make simple and looking good code and program structure

• always like i thought, coding with object-oriented way

  • especially code is should have unit that made by methods