대엉코딩

www.acmicpc.net/problem/15900

1. 풀이방법

- 트리 구조를 이용한 DFS문제 입니다.

- 처음에 문제를 읽으면서 가장 고민이 되었던 건 리프노드는 구별이 가능한데 (간선이 1개뿐인 놈(루트제외))

- 리프노드에서 한칸 타고 부모로 올라갔을 때, 그다음 부모노드가 어떤 녀석인지를 판정을 어떻게 해야하나

- 고민을 많이하고, 결국 class로 노드를 만들어 포인터를 통해서 인접리스트 방식으로 트리를 구현해야하나 생각

- 했었는데, 너무 하기 귀찮아서 다시 문제를 읽어보았는데

- 사실 문제가 원하는 출력이 그렇게 복잡하지 않습니다. 이기냐, 지냐 만 출력하는 문제이므로

- 사실 각각의 리프노드들로 부터 루트노트(1) 까지 가는 간선의 수 (즉 높이) 들의 합이

- 홀수이냐, 아니면 짝수 이냐만 파악하면 문제의 정답을 출력할 수 있었습니다.

- 즉 ! 높이만 알면 되므로 리프노드 부터 탐색할 필요가 없이, 루트노드부터 dfs를 통해 리프노드까지 가면 됩니다!!!!

- 가장 고민하던 문제가 해결되었습니다. 그 다음 부터는 쉽습니다

- 그러므로 vector<int> tree[500001]을 통해 트리의 간선정보를 담고 

- bool visitnode[500001] 을통해 위에서 내려오는 부모노드는 방문체크를 하여 dfs탐색에서 제외 시켜줍니다.

2. 주의사항

- 리프노드는 연결된 간선이 무조건 하나!!!! 하지만 여기서 주의할 것은 간선이 하나가 될 수 있는 녀석이 하나 더

- 있습니다..>!   바로 루트노드는 간선이 하나만 연결될 수 있습니다. 그러므로 종료조건에 s!=1(루트노드)를 추가

- 해주었습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int> tree[500001]; // 메모리때문에 인접행렬은 x 
bool visitnode[500001];
int totalheight = 0;
//간선이 하나만 존재하면 리프노드


void dfs(int s, int cnt) {
	if (tree[s].size() == 1 && s!=1) { //리프노드
		totalheight += cnt;
		return;
	}
	for (int i = 0; i < tree[s].size(); i++) {
		if (!visitnode[tree[s][i]]) {
			visitnode[tree[s][i]] = true;
			dfs(tree[s][i], cnt + 1);
			visitnode[tree[s][i]] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		tree[tmp1].push_back(tmp2);
		tree[tmp2].push_back(tmp1);
	}
	visitnode[1] = true;
	dfs(1, 0);
	if (totalheight % 2 == 1) cout << "Yes" << "\n";
	else { cout << "No" << "\n"; }
	
	return 0;
}

www.acmicpc.net/problem/13913

1. 풀이방법

- 걸리는 시간만 출력하라 했으면 정말 쉬웠을 텐데, 어떤식으로 경로도 출력 해야 합니다.

- 처음에는 출발점 1, 여기서 분화되는것이 3개 ( 배열:  0 | 1 2 3 )

- 그 다음 단계에서는 index 1,2,3 의 값(출발점에서 각각 3 개씩) ( 배열: 0 | 1 2 3 | 4 5 6 7 8 9 10 11 12 )

- 이런식으로 3의 제곱수로 분화된다는 것을 착안하여 k를 처음 발견한 위치의 index를 계산을 통해 앞쪽으로 이동

- 하면서 출력하였는데 시간이 너무 오래 걸립니다. (특히나 모든 경우의 수를 다 분화해서 가야하므로)

- 그래서 index계산을 통해서 가는 것을 포기하고 새로 bfs를 돌때 visit을 통해 방문한 지점은 다시 가지 않으므로

- 트리와 같은 느낌으로 어디서 왔는지 (부모가 누군지) 를 배열하나를 선언해서 넣어주면서 bfs를 돌고

- 나중에 k에서 시작해서 ---> 어디서왔는지를 쭉 탐색 ---> n을 발견하면 멈춤 이런식으로 구현하였습니다.

2. 주의사항

- 저 같은경우 출발점과 도착점은 무조건 출력해야 하는줄 알아서 

- 입력이 5 5 로 같으면 출력이 0 (시간) 5 5 (경로) 이렇게 인 것으로 착각 했으나

- n의 이동 경로이므로 5 하나만 출력해야 했습니다.

3. 나의코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;

int n, k;
queue<int> tmpq;
bool visit[100001];
int from[100001]; //어디서 온 놈인지르 표시해주자
vector<int> resultarr;

int second = 0;

int bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			int nextn = tmpq.front();
			tmpq.pop();
			if (nextn == k) { return second; }
			//1증가
			if (nextn + 1 <= 100000&& visit[nextn + 1] == false) {
				resultarr.push_back(2 * nextn);
				tmpq.push(nextn+1);
				visit[nextn + 1] = true;
				from[nextn + 1] = nextn;
			}

			if (nextn - 1 >= 0 && visit[nextn - 1] == false ) {
				tmpq.push(nextn - 1);
				resultarr.push_back(nextn - 1);
				visit[nextn - 1] = true;
				from[nextn - 1] = nextn;
			}
			
			if (nextn * 2 <= 100000&& visit[2 * nextn] == false) {
				tmpq.push(nextn *2);
				resultarr.push_back(nextn *2);
				visit[2 * nextn] = true;
				from[2 * nextn]=nextn;
			}
		}
		second++;
	}
}
void findparent() {
	int tmpk = k;
	resultarr.clear();
	resultarr.push_back(tmpk);
	while (1) {
		if (from[tmpk] == n) { resultarr.push_back(n); break; }
		resultarr.push_back(from[tmpk]);
		tmpk = from[tmpk];
	}
	for (int i = resultarr.size() - 1; i >= 0; i--) {
		cout<<resultarr[i] << " ";
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	int second = 0;
	if (n == k) { cout << 0 << "\n"; cout << n; return 0; }
	if (n > k) {
		cout << n-k<<"\n";
		cout << n << " ";
		for (int i = 1; i < (n - k); i++) {
			cout << n - i << " ";
		}
		cout << k << " ";
	}
	else {
		tmpq.push(n);
		visit[n] = true;
		cout << bfs() << "\n";
		findparent();
	}
	return 0;
}

0. 시작에 앞서...

- Minimum-Spanning-Tree 문제는 그래프의 최적화 문제 중 유명한 하나의 문제이다.

- 모든 정점을 최소비용으로 연결할 수 있는 트리를 구하거나 그 비용을 알아내는 문제.

- 즉 최적해(optimal solution)을 찾아내는 문제.

- 최소신장트리를 구하는 유명한 알고리즘으로 Prim과 Kruscal이 있는데 이번 시간에는 Kruscal 알고리즘을 다룬다.

1. 최소신장트리

- 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것

- 최소신장트리는 무향연결그래프에서 정의되며, 즉 connected, undirected,weight graph.

- 그래프의 weight는 그래프를 이루고 있는 subgraph들의 간선 가중치의 합.

- 트리 이므로 당연히 사이클이 발생해서는 안된다.

2. Union-Find data structure

- 서로 교집합이 없는 집합들을 모아놓은 자료형 ( disjoint set )

- operation : find(u) -> set id를 통해서 집합을 구분하는데 u라는 노드를 포함하고 있는 집합의 set id 를 return 한다.

                 union(u,v) -> u,v 두 노드가 각각 포함된 두 집합을 합집합한다.

3.Kruskal's Algorithm

- 접근 방식이 prim과 약간다르다고 할 수 있다.

- greedy technique을 이용한 알고리즘

- 각 노드들을 tree로 만들어 forest를 구성하고 그 tree들을 합쳐나간다.(merge)

- 간선에 dependent하다.

- 1. 가장 가중치가 적은 간선을 선택.

  2. 간선에 인접한 두 노드에 대해서 각각 find 연산을 수행한다.

  3. find(u) 와 find(v)의 리턴값이 다르면 두 노드가 서로다른 set에 포함되어있었던 것 이므로

     간선의 가중치를 추가해주고 두 노드에 대해 union(u,v)연산을 수행한다.(합집합)

  4. 만약 리턴값이 같다면 이미 두 노드는 같은 집합에 포함되어 있으므로 다른 작업을 수행하지 않는다.

  5. 모든 노드들이 포함되어 하나의 tree가 되면 위의 작업들을 반복하던 것을 종료한다.

4. Example

(1)

(2)

(3)

(!! 집합의 SET ID는 집합의 노드 중 알파벳 순으로 가장 작은것이 SET id 라고 가정)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12) 모든 노드가 TREE에 포함되었다.(MST)

5. 분석(Analysis)

- 시간복잡도 O(mlogm)  // m:간선의 수

- 크루스칼은 간선에 dependent하므로 그래프가 희소(sparse)

- 즉, 간선이 별로 존재하지 않는 그래프에서는 프림보다는 크루스칼이 유리하다.

- 시간복잡도, 즉 성능의 경우는 union-find 자료구조(data structure)을 어떻게 구현하느냐에 따라

   매우 상이하다.

- union find ADT를 구현할 때 

   weighted union : 더 큰 집합 뒤쪽에 작은 집합을 붙임

   path-compression: find연산을 한번 수행할 시 뒤쪽에 달린 노드들이 모두 setid인 노드를 가리키도록 구조를 바꿈

 이러한 방법들을 사용한다면 약간의 성능 향상을 기대할 수 있다.

0. 시작에 앞서...

- Minimum-Spanning-Tree 문제는 그래프의 최적화 문제 중 유명한 하나의 문제이다.

- 모든 정점을 최소비용으로 연결할 수 있는 트리를 구하거나 그 비용을 알아내는 문제.

- 즉 최적해(optimal solution)을 찾아내는 문제.

- 최소신장트리를 구하는 유명한 알고리즘으로 Prim과 Kruscal이 있는데 이번 시간에는 prim의 알고리즘을 다룬다.

1. 최소신장트리

- 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것

- 최소신장트리는 무향연결그래프에서 정의되며, 즉 connected, undirected,weight graph.

- 그래프의 weight는 그래프를 이루고 있는 subgraph들의 간선 가중치의 합.

- 트리 이므로 당연히 사이클이 발생해서는 안된다.

2.프림알고리즘의 아이디어

- 프림알고리즘은 트리를 점점 키워나가는 알고리즘이다.

- 먼저, 임의의 starting vertex를 선택한다.( 보통 그것이 root가 된다.)

- 연결된 간선 중 가중치가 작은 정점들을 차례대로 붙여나간다.

- 정점(vertices)들은 3종류의 disjoint categories로 나누어지는데

  1. Tree vertices

  2. Fringe vertices

  3. Unseen vertices

- 맨 처음에 모든 정점들은 unseen vertices이고 fringe set을 거쳐서 tree set으로 들어가게 된다.

  (단, 처음 선택하는 root vertex만이 fringe set을 거치지 않고  tree set에 들어가게 된다.)

- 예시로 한번 살펴보자(Example)

(1) 그래프는 아래와 같고 A라는 점을 root로 선택해서 시작한다고 가정.

(2) root를 제외한 모든 정점들은 unseen으로 setting

A에서 인접한 정점들을 fringe set에 넣어준다.

(3) (2)에서 가장 가중치가 적은 B를 선택해서 tree set에 넣고 다시 트리 정점으로 부터 인접한

     정점들을 fringe set에 넣는다. B와 인접해있는 C가 추가되었고..

     간선이 중복되는 경우가 있는데 이 경우 선택이 필요하다.

     AG(3) VS BG(6) 인데 AG가 가중치가 더 적으므로 AG를 선택한다.

(4) 이와 같은 과정을 모든 정점을 포함할 때 까지 하는 것이다.

     각 과정에서 가장 가중치가 적은 간선에 연결된 정점을 선택한다는 점에서 그리디 라고도 할 수 있겠다.

     FRINGE SET 은 Min Priority Queue를 이용하면 편하다.

3. Prim's Algorithm

4. 분석 (Analysis)

- 어떤 구조로 fringe set을 구현하느냐에 따라 차이가 있다.

- 일단, 모든 정점이 fringeset을 거쳐 tree set에 하나씩 들어가므로 (정점의 개수를 n이라 하면)

- unsorted array로 구현시 O(n^2)이라고 할 수 있다. 

- 힙으로 구현하면 fringe set에 삽입하는 시간을 O(log n)으로 줄일 수 있다.

- 프림 알고리즘의 경우 정점 개수에 dependent하므로 

- 그래프가 dense(간선이 많을 경우) 할 경우 프림의 알고리즘이 유리하다.

* 이진 탐색 트리?

 - 검색에 많이 사용이 되는 형태입니다.

 - 중위 순회 (Inordered traversal)를 할 경우 key값에 따라 sorting된 결과를 얻을 수 있습니다.

    # 구조 조건

     - 각 노드들은 자식노드를 기껏해야 두 개만을 가질 수 있습니다.

    # 순서 조건

     - 각 노드들의 왼쪽 서브트리에 있는 노드들은 각 노드보다 작은 값을 가집니다.(key)

     - 각 노드들의 오른쪽 서브트리에 있는 노드들은 각 노드보다 큰 값을 가집니다.(key)

    # 중위 순회

구조 조건과 순서 조건을 만족하는 이진탐색트리를 구성(construct) 하였다면

위와 같이 inordered traversal을 하면 key값을 기준으로 정렬이 됩니다.

(30,40,50,55,60,70)

 * 탐색연산(search)

 - root 노드 부터 시작하여 탐색하고자 하는 값 n 과 비교를 하며

   비교하는 노드보다 n값이 작다면 왼쪽 서브트리로 가서 왼쪽 서브트리의 루트노드와 다시 비교.

   비교하는 노드보다 n값이 크다면 오른쪽 서브트리로 가서 오른쪽 서브트리의 루트노드와 다시비교를 하면 됩니다.

* 삽입연산(insert)

 - 삽입연산은 탐색연산과 같이 내려가다가 자기 자리를 찾아서 들어가면 됩니다

 - 위의 저의 예시는 나름 예쁜? 모양이지만 이진탐색트리의 구조 조건과 순서 조건만 만족 하면서 구성해 나가면됩니다.

 - 같은 노드들의 값과 수 여도 다양한 모양의 이진탐색트리가 나올 수 있습니다.

 - 역시나 이와 같은 경우에도 순서와 구조 조건이 모두 맞습니다 --> 중위순회를 하여도 결과가 그대로 나옵니다.

 * 삭제연산(delete)

 - 이진탐색트리는 어떠한 노드를 삭제연산을 수행하여 제거 하여도 그 결과의 트리 역시 이진탐색트리여야 합니다.

    (당연하죠? ㅎ)

 - 두 경우로 나누어서 보겠습니다.

    1.) 삭제하려는 노드의 두 자식노드가 leaf노드인 경우입니다. --->그냥 삭제해버리면 됩니다.

    2.) 삭제하려는 노드의 자식이 하나는 leaf노드이고 한쪽은 서브트리(노드)를 가지는 경우

       - 삭제하려는 노드의 자리에 한쪽 서브트리를 연결 해주면 됩니다.

    3.) 두 자식이 모두 leaf노드가 아닌 값을 가진 노드 들( 즉, 두개의 서브트리를 가지는) 일 경우

        -- 본 예에서 60을 삭제 하고자 한다고 가정 하겠습니다. delete(40)

        -- 위의 예에서 보고 이렇게 하면되지 , 쉽게 보일 수 있지만 아래의 예를 보면 약간은 생각보다 복잡합니다.

        -- 두가지 방법이 있습니다(succesor를 삭제노드위치에 위치, predecessor을 삭제 노드 위치에 위치)

           더 금방 찾을 수 있는 (왼쪽 서브트리의 첫번째 노드) succesor를 이용합시다.

        -- succesor를 찾아서 삭제하려는 노드의 위치에 위치 시키고 부모노드와

        -- 삭제한 노드의 subtree들과 successor를 연결 시켜 주시면 됩니다.

        -- 위와 같이 삭제 연산을 수행 한 뒤에도 이진탐색트리가 나오게 되었습니다.

 * 성능분석

 - search, insert, delete (탐색, 삽입, 삭제) 연산 모두 O(n) 입니다.

 - worst case는 편향된(즉, 한쪽으로만 쭉쭉 뻗어있는 ) 트리입니다. 

 - tree에서의 연산들은 tree의 depth와 연관이 되어있는데 이럴경우 depth가 n(n-1) 이기 때문입니다.

 - average case의 경우 O(log n) 인데 worst case도 O(log n ) 을 맞추고 싶을 경우

 - depth를 맞추어주기 위해서 어느정도 균형이 잡혀 있는(예뿌장한?) 트리를 만들어 주어야 합니다.

 - 대표적인 균형이진트리들은 AVL TREE, RED-BLACK TREE 등이 있습니다.