알고리즘/알고리즘 정리 (4) 썸네일형 리스트형 [알고리즘 정리] - 동적 계획법(Dynamic Programming) 목차 1. 들어가며 2. 동적계획법이란 3. 예제 적용 들어가며 코딩테스트 단골 문제로 등장하는 동적 계획법, 일명 DP에 대해 정리해보려고한다. 정말 자주 출제되는 유형임에도 문제 유형이 DP인지 파악하기가 정말 어렵다. 그리고 그만큼 어려운게 사실이니 이번에 알아보자. 동적계획법이란 더보기 동적계획법 (Dynamic Programming) 먼저 동적 계획법이란 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 즉, 작은 문제들을 해결하여 큰 문제를 해결하는 방식의 기법인데, 동적 계획법이라는 이름과 전혀 매칭이 되지 않는다. 위키백과에는 이 이름의 유래에 대해 아래와 같이 설명한다. 알고리즘과 그 이름이 매칭이 안되서 찾아.. [알고리즘 정리] - Kruskal 알고리즘 목차 1. 들어가며 2. 최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘 3. 유니온 파인드(Union-Find) 들어가며 이번 글에서는 크루스칼(Kruskal) 알고리즘에 대해 정리해보려고 한다. 크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하고자 할 때 사용하는 알고리즘이다. 최소 신장 트리(Minimum Spanning Tree)와 크루스칼(Kruskal) 알고리즘 더보기 최소 신장 트리(Minimum Spnning Tree) 위의 그림과 같이 방향이 없는 가중치 그래프가 있다고 가정해보자. 여기서 최소 신장 트리란 모든 노드를 잇는 가중치가 최소인 신장 트리를 의미한다. 간단히 말하면 모든 노드들을 최소의 비용으로 방.. [알고리즘 정리] - DFS(Deprth First Search), BFS(Breadth First Search) 이번에는 경로 탐색의 대표적인 알고리즘인 DFS와 BFS에 대해 정리해보려고 한다. https://teachingforme.tistory.com/37 [자료구조] - 그래프(Graph) 경로탐색 알고리즘을 정리하기에 앞서 그래프 자료구조에 대해 정리해보려고 한다. 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미하며, vertex는 정점, edge는 정점과 정점을 연결하는 간 teachingforme.tistory.com 경로탐색 알고리즘은 기본적으로 그래프 자료구조를 통해 이루어지며 그래프에 대한 내용은 위의 글에서 정리하였다. 이번 글에서 정리할 DFS(Depth First Search), BFS(Breadth First Search)는 모든 edge(간선)의 가중치가 동일한(없는) 그.. [알고리즘 정리] - dfs vs 백트래킹 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백준에서 이 문제를 풀면서 백트래킹에 대해 학습을 하였다. 분명 이전에 공부했던 내용이지만, 코드로 구현하는 방법이 떠오르질 않았다. 그래서 이번에 공부하면서 알았던 것들을 정리해 보고자한다. #include #include #include using namespace std; void printArr(vector& choose, vector& visited, int stack, int num).. 이전 1 다음
