자료구조 및 알고리즘

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

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

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

그리디 알고리즘그리디 알고리즘의 핵심은 문제를 해결할 때 각 단계에서 매번 최선의 선택을 하는 것입니다. 당장 눈 앞의 선택지 중에 최선을 선택을 하여 결과적으로 최고/최적의 결과값을 도출해 내는 기법입니다. 이름이 Greedy Algorithm(탐욕 알고리즘)인 것을 생각해 보면 어느 정도 쉽게 이해가 됩니다. 그리디 알고리즘은 단계별로 그냥 최적의 선택만 하면 되기 때문에 단순하여 구현이 쉽다는 장점이 있습니다.  그리디 알고리즘에도 치명적인 단점이 존재합니다. 바로 매 순간 현재 단계에서 최선의 선택을 하더라도, 전체 문제의 관점에서 보았을 때 최선의 선택이 아닐 수 있다는 점입니다. 이런 점 때문에 그리디 알고리즘을 사용할 때는 아래의 조건을 충족하는 문제에서만 사용하여야 합니다. 1. 현재의 선..

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

위상정렬위상 정렬이란 방향그래프(Directed Graph)에서 순서가 정해져 있는 작업을 수행할 경우, 순서를 결정하기 위해 사용하는 정렬 알고리즘입니다. O(V+E)의 시간복잡도를 가집니다.  우리가 등교를 위해 옷을 입는 과정을 생각해 봅시다. 셔츠를 먼저 입을 수도, 양말을 먼저 신을 수도, 속옷을 먼저 입을 수도 있지만,신발을 신고 양말을 신거나 바지를 입고 속옷을 입을 수는 없습니다. 이처럼 순서가 정해져 있는 작업을 수행할 경우 올바른 순서를 도출해 내기 위해 위상정렬을 사용합니다. 위상정렬을 사용하기 위한 조건- 그래프가 비순환 방향 그래프(DAG: Directed Acyclic Graph)여야 합니다. DAG는 모든 노드에 대해 어떤 노드로부터 다른 노드로의 경로가 유일하며, 다시 출발점..