Algorithm/개념정리4 Kruskal vs Prim 신장 트리란? 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다. 최소 비용 신장 트리란? 신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다. 최소 비용 신장 트리의 특징 무방향 가중치 그래프입니다. 가중치의 합이 최소입니다. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다. 사이클이 포함되서는 안됩니다. 최소 비용 신장 트리의 사용 도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야하는 경우에 유용하게 사용됩니다. 최소 비용 신장 트리를.. 2023. 12. 2. Comparable, Comparator 인터페이스 백준 문제풀이를 진행하는데 있어 정렬에 조건을 줄 때, 아직 미흡한 이해 때문에 구글링을 번복하고 있다. 그렇기에 이번 기회에 확실하게 개념을 잡고 활용해보고자 정리하게 되었다. Comparable 인터페이스를 사용하려면 compareTo 메소드를 구현해야하는 것, Comparator 인터페이스를 쓰려면 compare 메소드를 구현해야 하는 점이 서로의 차이점이다. 보통 두 인터페이스는 "객체를 비교할 수 있도록 만든다." 라고 생각하는 것이 편하다. 하지만 왜 객체를 비교할 수 있도록 생각하라는 것일까? 우리는 원시 타입의 실수 변수 경우 부등호로 쉽게 비교할 수 있기 떄문이다. 하지만 새로운 클래스 객체를 만들어 비교하고자 한다면 본질적으로 객체는 사용자가 기준을 정해주지 않는 이상 어떤 객체가 더 .. 2023. 4. 15. 글을 쓰기에 앞서서 위 카테고리를 이제 생성에 대해 많은 시간을 고민했다. 이유는 아직 부족한 코테의 실력과 더불어 알고리즘에 대한 이해가 충분히 풍부하지 않았기 때문이다. 물론 지금도 훌륭한 적용을 바탕으로 문제를 해결하지는 못하지만, 현재 시점부터는 문제를 푸는 것 이외에 다양한 관점에서 여러 방면으로 접근해보고 더 꼼꼼한 공부를 해보고 싶었기에 시작하게 된 것이다. 코테 준비를 위해 1년 기간동안 알고리즘 스터디를 동기들과 꾸준하게 하고 있는데, 이는 4명이서 매주 4문제씩 백준 홈페이지에서 문제를 선정하고 있다. 문제에 대한 이해와 관점은 다른 경우가 많았기에 현재는 각자 Pr을 올려 코드 리뷰를 개인적으로 진행하고 있다. 깃허브 링크는 아래에 있으니 참고해도 좋을 것 같다. https://github.com/lco.. 2023. 4. 13. 이진 트리와 순회 방법 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 이진 트리는 많은 알고리즘에서 사용되며, 특히 검색 알고리즘에서 자주 사용됩니다. 이진 트리는 각 노드(Node)가 데이터와 두 개의 포인터(left, right)를 가지며, 이 포인터를 통해 자식 노드를 가리킵니다. 트리의 가장 위쪽에 위치한 노드를 루트 노드(Root Node)라고 하며, 가장 아래쪽에 있는 노드를 리프 노드(Leaf Node)라고 합니다. 이진 트리는 여러 가지 방법으로 순회할 수 있습니다. 대표적인 순회 방법으로는 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)가 있습니다.다음은 이진 트.. 2023. 4. 13. 이전 1 다음
