다이나믹 프로그래밍

냅색 문제냅색 문제는 최적의 조합을 찾기 위한 일종의 최적화 문제입니다. 냅색문제의 기본 개념은 주어진 물품들을 배낭에 담아 최대 가치를 얻는 것입니다. 아래와 같은 15kg 무게 한도의 배낭이 있을 때, 무게 한도 내로 물품을 가방에 넣는다는 가정하에 물건 가치의 합이 최대가 되게 담는 것입니다. 냅색 문제는 몇 가지 변형이 존재하는데, 문제의 변형 형태에 따라 사용할 수 있는 알고리즘이 다릅니다. 냅색 문제의 대표적인 형태는 2가지가 있습니다. 분할 냅색 문제(Fractional Knapsack Problem)- 물품을 쪼개서 배낭에 담을 수 있습니다.- 무게당 가치가 높은 물품을 우선적으로 담으면 됩니다.- 가치 높은 물품을 우선적으로 담기만 하면 되기 때문에 그리디 알고리즘(Greedy Algor..

🎮LCS만 검색하면 롤 북미 프로 리그가 나오던데,,, 이거 아닙니다! LCS 알고리즘LCS 알고리즘은 문자열 혹은 배열 내에서 가장 긴 공통 부분 수열을 찾는 알고리즘입니다. 여기서 공통 부분 수열이란 수열(문자열/배열) 내의 원소 내에서 순서대로 나타나지만 반드시 연속될 필요는 없는 부분 수열을 뜻합니다. LCS는 두 문서가 얼마나 비슷한지를 확인하는 코드 비교 도구, 버전 관리 시스템에 응용되거나 생물정보학의 서열 간 유사성 조사를 위해 DNA, RNA 서열 분석에 응용됩니다. 설명을 위해 그림으로 설명하겠습니다. 아래와 같이 두 문자열이 존재한다고 가정해봅시다.두 문자열 내에서 공통으로 존재하는 문자열은 ABEFG입니다. 해당 문자열은 두 문자열 내에서 반드시 나타나지만 반드시 연속해서 나타나지..

다익스트라 알고리즘(Dijkstra Algorithm)다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로의 최단 경로를 찾기 위해 사용되는 최단 경로 알고리즘입니다. 최단 경로를 찾는 알고리즘 하면 BFS를 떠올릴 수도 있지만, 다익스트라는 BFS(넓이 우선 탐색) 알고리즘과는 다르게 가중치가 존재하는 그래프에서 최단 경로를 찾을 때 사용됩니다. 이 때 그래프의 가중치는 음수가 될 수 없습니다.  특정 노드에서 각 노드까지의 최단 경로를 찾기 위해 사용하는 알고리즘인 만큼 실생활의 활용 예시로는 1. 지도의 특정 지점에서 다른 지점까지의 최단 경로 찾기2. 컴퓨터 네트워크에서의 데이터 패킷의 최적 경로를 찾기 위한 네트워크 라우팅 등 에서 사용됩니다. 다익스트라 알고리즘 구현다익스트라 알고리즘의 핵..

다이나믹 프로그래밍다이나믹 프로그래밍은 하나의 문제를 단 한 번만 풀도록 하는 것이 핵심입니다. 어떤 특정 범위까지의 값을 구한다고 할 때, 그것을 하위나 상위 등 다른 범위의 값을 이용하여 효율적으로 푸는 알고리즘이 바로 다이나믹 프로그래밍, 혹은 동적 계획법입니다. 현재 주어진 문제를 더 작은 문제로 나누어 각 부분 문제의 값을 계산하고, 최종적인 결과 값을 도출한다는 점에서 분할 정복 알고리즘과 비슷하지만, 명백한 차이점이 있습니다. 다이나믹 프로그래밍 vs 분할 정복 알고리즘다이나믹 프로그래밍은 분할 정복 알고리즘과 다르게 동일한 계산을 할 경우 계산한 결과를 미리 저장해 두었다가, 필요한 경우 꺼내서 사용합니다. 즉 메모리라는 공간 자원을 활용하여 불필요한 계산을 줄여 계산에 소요되는 시간을 줄..