공부공부/알고리즘!14 알고스팟(algospot) 31장 최소 스패닝 트리(크루스칼과 프림 알고리즘) 31.1 도입-스패닝 트리(=신장 트리)? --> 사이클이 없고, 그래프 내의 모든 정점을 포함하는 트리 -일반 스패닝 트리는 여러 개가 있을 수 있다. -최소 스패닝 트리는 무조건 1개! - 최소 스패닝 트리를 해결해줄 2가지 알고리즘! 크루스 칼 알고리즘--> 배타적 집합 자료구조의 사용! (Union find) 프림 알고리즘--> 다익스트라 알고리즘과 비슷 * 둘 다 무방향 그래프일 때만 사용! 31.2 크루스 칼의 최소 스패닝 트리 알고리즘 가중치가 작은 간선과 큰 간선중 어느 쪽이 최소 스패닝 트리에 포함될 가능성이 높을까?---> 당연히 작은 간선! 이를 통한 알고리즘!1. 모든 간선을 가중치의 오름 차순으로 정렬한 뒤2. 하나씩 추.. 2022. 5. 22. 알고스팟(algospot) 21 장 트리의 구현과 순회 21.1 도입 계층구조를 가지는 것 같다? --> 트리 -트리의 구성요소 : 노드 node, 간선 edge -트리는 재귀적 속성을 가지기 때문에 트리를 구현한 함수들은 대부분 재귀로 구현 가능! -구조체로 구현하는것이 일반적! struct TreeNode { string label; // 저장할자료(물론꼭문자열일 필요는 없다.) TreeNod* parent; //부모노드를가리키는포인터 vector children; //자손노드들을가리키는포인터의 배열 }; 21.2 트리의 순회 -순회할때는 트리의 재귀적 속성을 사용하는 것이 좋음 void printlabets (TreeNod* root) { cout label children.size(); +.. 2022. 5. 15. 알고스팟(algospot) 20장 문자열 20.1 도입프로그래밍 대회에서는 비교적 간단한 알고리즘이 주로 사용됩니다...?문자열 검색 kmp알고리즘문자열 처리의 자료 구조 접미사 배열등등 을 사용 20.2 문자열 검색1. 단순 문자열 검색 알고리즘 : 하나씩 하나씩 비교vector naiveSearch(const string& H, const string& N) { vector ret; for(int begin = 0; begi n + N.size( ) 단순하지만 비효율적;;; 2. KMP 알고리즘 : 접두사와 접미사가 같은 --> 부분 일치 테이블을 이용하여 문자열 검색 시 뛰어넘어버리는 알고리즘! 부분 일치 테이블? 처럼 부분이 겹치는 것 구하는 방법 1. 단순 문자열 탐색.. 2022. 5. 15. 알고스팟(algospot) 19장 큐와 스택, 데크 19.1 도입큐 -- 한쪽으로 정보를 저장하고 다른 한쪽에서 정보를 꺼내는 (선입선출 FIFO) 스택 -- 한쪽으로 정보를 저장, 출력하는 (후입 선출 LIFO)데크-- 양쪽에서 저장,출력을 하는 19.2 큐와 스택, 데크의 구현 연결리스트를 통한 구현-- 구현하기에는 가장 간단 그러나 포인터를 통해 이동하는데 시간이 걸려 가장 효율적이지는 않다! 동적배열을 이용한 구현 -- 스택의 경우에는 Vector를 이용해서 쉽게 구현 가능 (--> 한쪽으로만 저장, 출력하기 때문) .. 2022. 5. 15. 알고스팟(algospot) 15장 계산 기하 15.2 계산기하의 도구1 ) 벡터의 구현!struct vector2{ double x, y; //생성자를 explicit으로 지정하면 vector2를 넣을 곳에 잘못해 //실수가 들어가는 일을 방지 explicit vector2(double x_ = 0, double y_ = 0) :x(x_), y(y_) { } //두 벡터의 비교 bool operator==(const vector2 &rhs) const { return x == rhs.x&&y == rhs.y; } bool operator 극각도.. 2022. 5. 8. 이전 1 2 3 다음 728x90 반응형
