목록분류 전체보기 (150)
개발하는 리프터 꽃게맨입니다.
1. 신장 트리신장 트리(Spanning tree)란 그래프내의 모든 정점을 포함하는 부분 그래프(혹은 트리)이다.신장 트리는 특수한 형태로 모든 정점들이 연결되어 있어야 하고 사이클을 포함하면 안된다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리의 경우 BFS, DFS 를 사용하면 도중에 사용된 간선을 모아 만들 수 있다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다.여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다.n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 ..
앞으로 유니티 및 툴 개발하기 위해서C#이라는 언어에 대한 스터디를 진행합니다. 제가 스터디를 하면서 기록하는거라제 글을 보고 무엇을 배우는건 권장하지 않습니다. 교재는 '이것이 C#이다! 3판' 을 사용합니다. 일단 늘 하는 Hello World 부터 출력해보도록 합시다. using System; 은C의 include 와 유사해보입니다. System은 namespace이고해당 namespace 안에 유용한 가용 클래스들이 있는 것으로 보입니다. 없어도 System.Console.~~ 이런 형식으로 사용할 수 있다고 합니다. 조금 생소했던것은 using static System.Console; 부분입니다.using 키워드만 사용하면 네임스페이스 전체를 사용한다는 의미지만using static 은 어..
참고자료: C언어로 쉽게 풀어쓴 자료구조 - 천인국 저 1. 그래프란?그래프(graph)는 객체 사이 연결 관계를 표현할 수 있는 자료구조다.그래프의 대표적인 예는 '지도'이다. 위 그림은 여러 개의 도시들이 어떻게 연결되었는지를 보여준다.지도를 그래프로 표현하면 특정한 지역에서 다른 지역으로 가는 최단 경로를 쉽게 프로그래밍해서 찾을 수 있다. 또한 전기 소자를 그래프로 표현하게 되면 전기 회로의 소자들이 어떻게 연결되어 있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있으며, 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 그래프는 이러한 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구이다.우리가 이때까지 배워온 ..
이진 탐색 알고리즘은 '정렬된 상태의 배열' 에서 원하는 값을 O(log n) 만에 탐색할 수 있는 알고리즘 입니다. 그 방법은 '업앤다운 숫자맞추기'를 하는 방법과 유사합니다. 1~50 중에서 상대방이 생각한 숫자를 가장 빨리 맞추는 방법은 절반인 25를 말해서 업, 다운을 듣고 업! 이라면 37 다운! 이라면 12 을 말하면서 점차 줄여나가는 방식입니다. 계속 절반 절반 반띵하면서 원하는 수를 찾아가는 것이죠. 샘플코드 입니다. 찾고자 하는 값이 mid 값보다 크냐 작냐에 따라서 찾고자하는 범위를 좁혀나가는 것입니다. 재귀적으로 코드를 구성할 수 있습니다. 이진탐색의 경우 log2 N 의 시간복잡도를 가지며, 임의 접근이 불가한 연결리스트의 경우에는 설사 정렬이 되어 있더라도 이진 탐색을 사용할 수 ..
https://powerclabman.tistory.com/90 [C++/이론] 최소 스패닝 트리 : 프림 알고리듬 (Prim Algorithm) 스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 powerclabman.tistory.com 개요 크루스칼 알고리즘은 최소 스패닝 트리를 구하기 위한 또 다른 알고리즘입니다. 앞전에 소개한 프림 알고리즘과 차이점은, 프림 알고리즘의 경우 특정 노드에서 출발해 노드들을 탐색하면서 최소 스패닝 트리를 완성시켜나가는 알고리즘이었다면 크루스칼 알고리즘은 모든 경로를 두고, 최소 경로만 쏙쏙 선택해서 트리를 만들어낸다고 보면 되..