전체 글27 C++/ 최소 스패닝 트리, Kruskal & Prim algorithm Spanning Tree (신장 트리) 란 그래프 내의 모든 정점을 포함하는 트리이며, 사이클을 포함해서는 안되는 트리이다. 사이클을 포함하지 않기 때문에 n개의 정점이 존재하면 간선의 개수는 n-1개이다. Minimum Spanning Tree (최소 신장 트리, MST) Spanning Tree 중에서 간선의 가중치 합이 최소인 트리를 일컫는다. -> 네트워크에 있는 모든 정점들을 가장 적은 수, 최소 비용의 간선으로 연결하는 트리를 말한다. 이런 MST를 구현하는데에 잘 알려진 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. Kruskal MST Algorithm 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 가는 방식의 알고리즘. (단순히 추.. 2021. 2. 16. C++/ 우선순위 큐 + 구조체를 이용한 벡터 정렬 (3개 이상의 값) 더보기 인프런 73,74 강의 1. 우선순위 큐 앞서 bfs에서 많이 활용한 큐 자료구조는 First in First out 구조로, rear로 데이터가 삽입되고 front로 삭제되는 구조였다. 우선순위 큐란 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조이다. 우선순위 큐는 최대 힙, 최소 힙을 구현하고자 할 때 쓰이는 자료구조이다. 더보기 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. 여기서 최대 힙은 내림차순으로 정렬된 이진 트리라고 생각하면 되기 때문에, root에 가장 큰 원소가 .. 2021. 2. 6. C++/ DFS 완전탐색 -이중배열, STL vector pair 인프런 dfs 강의 58번~68번까지 들은 후에 정리하는 글 "완전 탐색"을 가능하게 하는 dfs 함수로 경로탐색, 미로탐색, 최소비용 문제를 풀어보았다. 문제를 풀면서 무방향 그래프, 방향 그래프 모두 이차원 배열로 구현해 본 후에 vector pair 자료구조를 이용해서 더 효율성 있는 코드 작성법을 배웠다. 1. void DFS(int vertex) 문제를 풀면서 쓰인 dfs 함수의 구조는 거의 동일했다. if 문을 이용해 재귀함수를 빠져나올 조건을 걸고, else 문에서 다음 경로로 가는 코드를 짠다. void dfs(int v){ int i; if(v==n){ cnt++; } else{ for(i=1;i 2021. 1. 30. Spring 공부 1일차 - IntelliJ로 스프링 시작하기 스프링을 이용해 서버 프로젝트를 만들어 보기 위해 새롭게 공부를 시작했다. 1. 프로젝트 생성 스프링 부트 스타터 사이트의 도움을 받아 스프링 프로젝트를 생성한다 https://start.spring.io Project: Gradle Project Spring Boot: 2.3.x Language: Java Packaging: Jar Java: 11 Project Metadata groupId: hello artifactId: hello-spring Dependencies: Spring Web, Thymeleaf 보는 것과 같이 프로젝트의 라이브러리 관리 툴인 gradle, maven을 선택할 수 있고 스프링 버전을 설정해줄 수 있다 그룹명과 프로젝트 명을 기재한 후 GENERATE 버튼을 누르면 폴더에.. 2021. 1. 9. C++/ 재귀함수의 Stack 저장 원리로 DFS 이해하기 DFS (Depth First Search) 더보기 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. -출처 위키 여기서 "맹목적 탐색" 이라는 단어가 쓰인 이유는 연결된 노드 중 임의의 하나를 선택하여 탐색을 진행하는 방법이기 때문이다. 따라서 순서 복잡하게 여러 갈래가 될 수 있음 DFS의 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. DFS의 단점 해가 없는 경로에 깊이 빠질 가능성이 .. 2021. 1. 7. C++/ Queue 자료구조 정리 Queue의 정의 - 입출력이 서로 반대쪽에서 이루어지는 제한구조. - 자료가 입력된 순서대로 출력되는 FIFO(First In First Out) 방식이다. - 입력은 front에서, 출력은 back에서 되는 구조가 기본 cplusplus 정의 더보기 queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "b.. 2020. 12. 26. 이전 1 2 3 4 5 다음 반응형
