이진 트리의 자식 표현 방법 이진 트리는 트리와 달리 자식의 Left, Right에 대한 정보가 반드시 필요하다. 따라서 일반적인 그래프로 구현하기 힘들다. 배열, 구조체, 연결리스트 등으로 표현가능하지만 트리의 구조를 이용하여 배열로 간단하게 나타낼 수 있다. 이진 트리의 4가지 순회 방법 1. 레벨 순회(Lever Travel) Level Travel은 트리이 깊이를 순차적으로 탐색한다. 방문 순서는 cur → Left Child → Right Child이다. 레벨 순회는 BFS와 유사한 구조를 가진다. 구현은 일반적인 BFS처럼 해주면 된다. 이를 코드로 구현하면 다음과 같다. void levelTravel(){ queue q; q.push(1); while(!q.empty()){ int cur =..

이번 포스팅에서는 유니온 파인드 알고리즘에 대해서 알아보겠습니다. 유니온 파인드를 알기 위해 간단한 트리의 개념을 알아야 합니다. 트리가 처음이라면 먼저 간단하게라도 트리의 개념과 트리 순회를 알아보고 오는 것을 추천드립니다.유니온 파인드 알고리즘은 기본 구현보다 최적화 방법과 문제 적용이 더 중요합니다. 최적화 원리까지 이해하고 문제 적용하는 것을 강력 권장합니다. 1. 유니온 파인드란?다음과 같이 여러 노드간의 연결 관계가 주어졌다고 해봅시다.임의의 두 노드가 주어졌을 때 유니온 파인드 알고리즘을 이용하면 두 노드가 같은 집합에 속하는지 확인할 수 있습니다. 예를 들어 1과 2는 같은 집합, 3과 5도 같은 집합, 4와 6은 다른집합입니다. 유니온 파인드를 이용하면 이러한 연산을 O(1)에 바로 알 ..

트리란? 트리란 싸이클이 없는 무방향 그래프를 말한다. 싸이클이 존재하지 않아서 모든 노드가 루트가 될 수 있다. 마치 실로 연결된 구슬이 있는데 한 구슬을 잡아서 들어올릴 때마다 그 구슬이 루트가 되고 트리 구조가 형성되는 것과 비슷하다. 트리 순회하기 그래프의 구조를 가지므로 BFS와 DFS를 이용할 수 있다. 이 과정에서 부모의 정보 or 깊이의 정보가 필요한 경우 중간중간에 기록해주면 된다. 1. BFS void bfs(int root){ queue q; q.push(root); while(!q.empty()){ int cur = q.front(); cout