Study/Algorithm (5) 썸네일형 리스트형 Dynamic Programming(동적 계획법) 다이나믹 프로그래밍이란?최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 DP를 쓰는 이유일반적인 재귀방식과 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다. 예를들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하게 된다면return f(n) = f(n - 1) + f(n - 2)그러나 위의 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게되고 이로인해 100번째 피보나치수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 늘어난다. 이러한 반복되는 문제들의 결과값을 저장해두고 재사용하게된다면 매우 효율적으로 문제를 해결할 수 있게 된다.. [알고리즘] 최소신장트리(MST, Minimum Spanning Trees) / 위상정렬 신장 트리(Spanning Tree)란? 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미한다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 된다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리이다. 가중치는 거리, 비용, 시간등으로 응용할 수 있다. 최소 신장 트리의 대표적인 알고리즘 으로는 프림 알고리즘과 크루스칼 알고리즘이 있다. 프림 알고리즘(Prim's Algorithm) 프림 알고리즘은 최소 신장트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 방법이다. [과정] 크루스칼 알고리즘(Kruskal's Algorithm) 크루스칼 알고리즘은 그래프 내의.. [알고리즘] 그래프 알고리즘 (BFS / DFS) 그래프란? 현상이나 사물을 정점과 간선으로 표현한 것. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 구현 방식 그래프는 주로 두가지 방식으로 구현된다. 1. 연결 리스트를 이용한 인접 리스트 방식 간선의 개수만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(v)의 시간복잡도를 가진다. 2. 2차원 배열을 이용하는 인접 행렬 방식 메모리 공간을 많이 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다. 3. N개의 연결 배열로 표현한 인접 배열 방식 메모리 사용량을 절감하면서 포인터 오버헤드 감소, 두 정점의 인접 여부를 체크하는 시간을 절감한다. 그래프 탐색 알고리즘 대표적인 두 가지 방법 - 너비우선탐색 (BFS) - 깊이우선탐색 (DFS) 너비우선탐색 (BF.. [알고리즘] 동적 프로그래밍(Dynamic Programming) 알고리즘 동적 프로그래밍(Dynamic Programming)알고리즘이란? 동적 프로그래밍이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. DP를 사용하는 이유 DP는 일반적인 재귀 방식과 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작운 문제들이 여러번 반복 되어 비효율적인 계산이 될 수 있다는 것이다. 또한 분할정복과 비슷하다고도 생각할 수 있는데 이는 작은 문제가 중복이 일어나는지 안일어나는지 차이점이 있다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 .. [알고리즘] 브루트 포스(Brute Force) 알고리즘 완전탐색 브루트 포스 알고리즘이란? 브루트 포스를 직역한다면 브루트(Brute) 무식한 + 포스(Force) 힘 즉, 모든 경우의 수를 무식하게 탐색한다는 것이다. 전체를 탐색한다는 의미해서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 정답을 찾을 수 있다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breath First Search)이 가장 기본적인 도구이다. DFS와 BFS는 그래프 알고리즘을 정리할 때 다루어보자. 브루트 포스의 장점과 단점 장점 알고리즘을 설계하고 구현하기 매우.. 이전 1 다음
