알고리즘 😘
Tree 에 대해서 알아보자! (자료구조, 알고리즘)
안녕하세요 원재입니다 ^ㅡ^ 이번 글에서는 빠른 탐색을 위해 사용되는 트리 자료구조에 대해서 알아보려고 합니다! Tree 는? Tree 는 말 그대로 나무입니다 ^ㅡ^ 읽어주셔서 감사합니다가 아니라 생뚱맞게 왜 자료구조를 공부하기 위해 작성된 게시글에서 갑자기 나무 사진을 들고 여러분들에게 소개를 하고있을까요? 한번 위에 있는 나무를 뒤집어 볼까요? 독자분들이 물구나무서기를 할 필요없이 제가 완벽하게 뒤집었습니다. 근데 이게 무슨 소용이 있길래 제가 어마무시한 노력과 정성 그리고 시간을 들여 나무를 뒤집어버렸을까요? 바로 아래 배울 자료구조로서의 트리의 생김새가 마치 나무를 뒤집은 것과 비슷하게 생겼기 때문입니다. 위 그림이 우리가 알아볼 트리입니다. 꽤나 비슷하게 생기지 않았나요? 사실 저도 뒤집어놓고..
Union-Find(Disjoint-Set) 에 대해, + BOJ 4195
안녕하세요 원재입니다 ^ㅡ^ 이번에는 알고리즘에서 주로 쓰이는 (특히 그래프 알고리즘) Union-Find 에 대해서 알아보려고 합니다! Union-Find 는? Union-Find 의 가벼운 첫 인상을 알려드리자면, Union-Find 는 우리 조상님 찾기 라고 볼 수 있습니다! 조상님이라고 부르세요 위와 같은 그래프가 있다고 생각해 봅시다. 루트 노드는 1 과 5 가 되겠죠? 3,4 를 자식으로 가지는 1번 트리와, 6, 2를 자식으로 가지는 5번 트리가 존재한다고 생각하겠습니다. 그렇다면 우리는 Union-Find 를 통해 4의 조상님은 1이에요! 라는 것을 Find 할 수 있습니다. 그렇다면 Union 은 어떨때 사용할까요? 바로 족보 구매 입니다. 족보입니다 만약 위와 같은 노드에서 5번 노드가..