공부공부/알고리즘!14 알고스팟(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. 알고스팟 (algospot) 9장 동적계획법 테크닉 9.1 최적화 문제의 실제 답 계산하기재귀 호출의 각단계에서 최적해를 만들었던 선택을 배열에 저장후 비교 최신화별도의 재귀함수를 이용해 선택지를 저장 출력!**예제)**최대증가 부분수열 실제로 출력하기-> LIS = 각원소가 이전 원소보다 크게 리스트를 구성한것중 가장 길이가 긴것 각 문제들9.2 여행짐싸기9.4 광학문자인식 9.6 k번째 답 계산하기모든 답들을 만들고 메모이제이션(물론 각 블록을 구분할수있다면 스킵하고 저장 가능)k-1개를 스킵하고 답을 출력한다 ---> 최소최대값존재할수도있음 ex) 10000000000 이하임예제) 모스부호사전-- 부호 만들어 찾기 각 문제들9.7 k번째 최대 증가 부분수열9.9 드래곤 커브 9.11 정수 이외의 입력에 대한.. 2022. 5. 8. 최소신장트리!(프림과 크루스칼) *그래프 내의 모든 정점을 포함하는 트리(최소로) *사이클 있으면 ㄴㄴ 프림 — 시작정점을 기준으로 신장트리를 확장— 방법은 다익스트라와 동일한거 같음! 차이점- 다익스트라는 모든정점이 아닌 최단경로만 계산! 프림은 모든 정접을 지나가는 경로를 계산! def get_min_node(node_num): print("get_min_node 함수 진입했다") for i in range(node_num): if not visited[i]: v = i break print("아직 방문하지 않은 v: ", v) for i in range(node_num): if not visited[i] and distances[i] < distances[v]: print("i: ", i, "\\tv: ", v) print("di.. 2022. 3. 4. 이전 1 2 3 다음 728x90 반응형
