프림(Prim) 알고리즘1. 그래프에서 시작점을 정한다 - (어떤 노드이어도 상관없음)2. 선택한 정점과 인접하는 정점들 중 최소 비용인 간선에 연결된 정점을 선택한다.3. 모든 정점이 선택될 때까지 1,2과정을 반복한다.※ 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리를 구성하는데 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 정렬 후 가장 최소 비용으로 간선을 선택하기 때문에 사이클이 발생하는지 판단하면서 진행해야 한다.

크루스칼(Kruscal) 알고리즘 최소 비용 신장트리(Minimum Spanning Tree) 대표적인 알고리즘 중 하나로 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용한 알고리즘이다. [Algorithm] 최소 비용 신장 트리 (MST, Minimum SpanningTree) (tistory.com) [Algorithm] 최소 비용 신장 트리 (MST, Minimum SpanningTree)신장트리(SpanningTree) 그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개cclient.tistory.com이전에 포스팅한 최소 비용 신장 트리의 다섯까지 특징..

신장트리(SpanningTree)그래프 중 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프를 의미한다. 특징으로는 N개의 정점을 가지는 그래프의 최소 간선(edge)의 수는 (N-1)개이다. 최소 비용 신장 트리 (MST, Minimum SpanningTree)신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 한 곳으로 도달하는 경우가 두 개 이상 존재하는 경우, 즉 사이클이 존재하는 경우에는 최소한의 연결이라 말할 수 없기 때문에, 모든 위치 하나에서 다른 곳으로 이동하는 경우는 단 한 가지로 결정되도록 항상 트리의 형태를 나타낸다. 최소 비용 신장 트리는 이러한 신장 트리들 중 간선의 가중치 합이 가장 작은 트리이다. 최소 비용 신장 트리는 그리디 ..

Union-Find(유니온 파인드)그래프 알고리즘 중 하나로 서로소(disjoint sets) 집합 자료구조이다. 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조를 구현할 때는 트리 자료구조를 이용하여 집합을 표현하는데, 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다.1. union(합집합)연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.       - A와 B의 루트 노트 A', B'를 각각 찾는다.       - A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.)2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.17. Union-Find(..

C++17이전에는 읽기 전용 스트링을 받는 함수의 매개변수 타입을 쉽게 결정할 수 없었다. const char*로 지정하면 std::string을 사용하는 클라이언트에서 c_str( )나 data( )를 이용하여 string을 const char*로 변환해서 호출해야 한다. 이렇게 하면 std::string의 객체지향 속성과 여기서 제공하는 헬퍼 메서드를 제대로 활용할 수 없다. 이러한 문제를 해결하기 위해서는 C++17부터 추가된 std::string_view를 사용하면 된다. std::string_view - 헤더: - 클래스 템플릿: std::base_string_view - 추가 메서드: remove_prefix(size_t), remove_suffix(size_t) → 지정한 오프셋만큼 스트링의..

종류 연산자 프로토타입 이항 산술 연산자 operator+ operator- operator* operator/ operator% T operator■ ( const T&, const T& ) ; 단항 산술 및 비트 연산자 operator+ operator- operator~ T operator■ ( ) const ; 선행, 후행 (증가,감소) operator++ operator-- T& operator■ ( ); T& operator■ ( int ); 대입 연산자 operator = T& operator■ ( const T& ); 축약 산술 대입 연산자 operator+= operator-= operator*= operator/= operator%= T& operator■ ( const T& ); T&..

C++에서는 흔히 스트림의 출발지와 목적지로 콘솔, 파일, 스트링을 사용합니다. ※ 파일 끝을 나타내는 EOF(end of file)은 유닉스와 리눅스에서는 Ctrl+D를 사용하고 윈도우에서는 Ctrl+Z를 사용합니다. 1. 출력 스트림에서 제공하는 메서드 대표적인 cout은 빼고 정리했습니다. cin 입력 스트림. '입력 콘솔'에 들어온 데이터를 읽는다. cout 버퍼를 사용하는 출력 스트림. 데이터를 '출력 콘솔'에 쓴다. cerr 버퍼를 사용하지 않는 출력 스트림. 데이트를 '에러 콘솔'에 슨다. clog 버퍼를 사용하는 cerr ※ 버퍼를 사용하는 것과 사용하지 않는 것의 차이와 장점은? 버퍼를 사용하는 스트림은 받은 데이터를 버퍼에 저장했다가 블록 단위로 목적지로 보내고, 버퍼를 사용하지 않는 ..

《출처. 시작하자! C++17 프로그래밍 (박헌재 지음)》 시작하기 전 동기와 비동기에 대해서 먼저 알아보자! Asynchronous(비동기) Synchronous(동기) 발음도 어려워 보이는 동기, 비동기 일단 말은 할 수 있어야 하니.. 번역기에 돌려 읽어주는데로 한 번 적어보겠습니다. Synchronous-> siNGkrənəs(씨-인!크로너스) Asynchronous->āˈsiNGkrənəs(에이 씨-인!크로너스) 이런식으로 발음해주고 있습니다. 알아 둡시다.. 면접에서 물어보면 알아듣긴 해야하니깐 (T_T)/ 이제 이 둘의 차이점과 지닌 뜻을 알아보자! 더보기 더보기 더보기 ● Asynchronous(비동기) : 작업을 위임하고 기다리는 방식 쉽게 이야기 하면, 꼭 한 줄 한 줄 순서대로 실행되..

《출처. 시작하자! C++17 프로그래밍 (박헌재 지음)》 독립적으로 실행되는 스레드라 하더라도 경우에 따라 다른 스레드에 전달할 정보가 있기 마련이다. 전달하는 방법 중 우리가 공부할 방법은 '조건변수(Conditional Variable)' 라고 부르는 기능이다. 조건변수는 주로 게임에서 많이 사용하는 데 달리기 시합처럼 모든 선수가 출발선상에 대기한 상태에서 총소리와 함께 출발하도록 스레드 모두 대기 상태로 만들고 동시에 공동 경쟁을 수행한다. 조건변수는 단지 변수를 통해 신호를 주고 받는 기능만을 제공할 뿐 자체 잠금 기능이 없다. 따라서 다수의 스레드에 의해 실행되는 작업이 안전성을 보장하기 위해 별도 뮤텍스를 사용한다. 가장 중요한 함수는 wait(), notify_all() 함수이다. 조건변..