chamMal

종합 시험이 있어 건네 받은 문제 은행을 토대로 DP, Greedy, Divide and Conquer, Master 정리, P,NP,NP-complete,NP-Hard, 정지 문제에 대해 공부한 내용으로 정리하였다. DP(Dynamic Programming, 동적 계획법) - 큰 문제를 작은 문제로 나누어 푸는 최적화 기법 - 중복되는 부분 문제가 존재하고, 이를 한번만 계산하고 결과를 저장해둠으로써 중복 계산을 줄임 - Memoization(메모이제이션) 기법을 사용하여 이미 계산된 값을 저장해둠 - 예시: 피보나치 수열, 최장 증가 부분 수열(LIS) 등 Greedy Algorithm(탐욕 알고리즘) - 각 단계에서 지금까지의 선택이 전체적인 결과를 만족시키는 최적해가 되는 방식 - 각 선택마다 최..

최소신장트리(Minimum Spanning Tree, MST)는 연결 그래프에서 모든 노드를 연결하는 트리(Tree)를 만들 때, 간선의 가중치 합이 최소가 되도록 하는 사이클이 존재하지 않는 트리를 말합니다. 이는 그래프 이론에서 매우 중요한 문제 중 하나이며, 실제로 최소신장트리 알고리즘은 다양한 분야에서 활용되고 있습니다. 대표적인 최소신장트리 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다. Kruskal 알고리즘은 그리디 알고리즘(Greedy Algorithm)을 기반으로 하며, 간선의 가중치가 작은 순서대로 간선을 선택하여 트리를 만들어 나가는 방식입니다. 반면, Prim 알고리즘은 시작점에서부터 출발하여 연결된 노드들 중에서 가장 가중치가 작은 간선을 선택하여 트리를 만들..

최단 경로 알고리즘은 두 노드 사이의 최단 경로를 찾는 알고리즘입니다. 그래프 이론에서 자주 사용됩니다. 가장 기본적인 최단 경로 알고리즘은 다익스트라 알고리즘입니다. 다익스트라 알고리즘은 음의 가중치를 가지지 않는 그래프에서 사용할 수 있으며, 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾을 수 있습니다. 이 알고리즘은 매우 효율적인 알고리즘으로 알려져 있으며, 우선순위 큐를 사용하여 구현할 수 있습니다. 그러나 음의 가중치를 가진 그래프에서는 벨만-포드 알고리즘이 사용됩니다. 이 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 가진 그래프에서도 사용할 수 있습니다. 그러나 다익스트라 알고리즘보다 더 느린 실행 속도를 가지며, 음수 가중치 사이클이 있는 경우에는 최단 경로를 찾을 수 없습니다..

다이나믹 프로그래밍(Dynamic Programming) : 큰 문제를 작은 문제로 나누어 푸는 방법으로 계산된 결과를 기록하고 재활용하며 문제의 답을 구할 수 있는 방식. 중간에 계산된 결과를 메모리에 저장하고 재활용 가능 분할 정복과의 차이 - 분할 정복은 부분 문제가 중복되지 않고, DP는 부분 문제가 중복되어 재활용을 한다 그리디 알고리즘과의 차이 - 그리디는 순간의 최선을 구하는 방식으로 근사치를 구할 수 있지만, DP는 모든 방법을 확인 후에 최적의 해를 구한다. 다이나믹 프로그래밍이 되기 위한 조건은 3가지가 있다고 한다. 1. Simple subproblems 큰 문제를 작은 문제로 나눌 수 있어야 합니다. 2. Optimal substructure 최적의 해를 찾는 구조를 만들 수 있어야..