morgankim

동적 계획법(DP, Dynamic Programming)은 복잡한 문제를 해결하기 위해 그 문제를 더 작은 부분 문제로 나누고, 각 부분 문제를 한 번만 해결하여 그 결과를 저장하고 재사용하는 방법론입니다. DP는 주로 중복된 계산을 피하고 문제를 효율적으로 해결하기 위해 사용됩니다. 동적 계획법의 주요 특징1. 중복된 계산 제거: 동일한 부분 문제를 여러 번 계산하지 않고, 한 번 계산한 값을 저장해두고 다시 사용합니다.2. 부분 문제: 큰 문제를 해결하기 위해서는 작은 문제들의 해결이 필요합니다.3. 최적 부분 구조: 전체 문제의 최적 해결은 부분 문제의 최적 해결을 바탕으로 합니다.4. 메모리 사용: DP는 계산한 값을 저장하는 테이블(보통 배열이나 리스트)을 사용합니다. 동적 계획법의 두 가지 기..

벨만-포드 알고리즘 (Bellman-Ford Algorithm)  벨만-포드 알고리즘은 최단 경로를 구하는 알고리즘으로, 특히 음의 가중치를 갖는 간선이 있는 그래프에서도 동작하는 알고리즘입니다. 다익스트라 알고리즘과 달리 음의 가중치를 처리할 수 있다는 점에서 중요한 특성을 가집니다. 기본 아이디어벨만-포드 알고리즘은 그리디 방식이 아닌 동적 계획법(DP)을 기반으로 하는 알고리즘입니다. 각 단계에서 모든 간선을 한번씩 탐색하면서, 각 노드의 최단 거리를 점차적으로 갱신합니다. 알고리즘 동작 원리1. 초기화:   - 시작 노드의 거리는 0, 나머지 노드들은 무한대(`INFINITY`)로 설정합니다.  2. 간선 완화(Relaxation):   - 그래프의 모든 간선 `(u, v)`에 대해, `dist[..

다익스트라 알고리즘 (Dijkstra's Algorithm)  다익스트라 알고리즘은 주어진 그래프에서 출발 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘입니다. 특히, 음의 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 그리디 알고리즘으로 분류되며, 우선순위 큐를 이용하여 효율적으로 구현됩니다. 기본 아이디어1. 출발 노드에서 시작하여, 다른 모든 노드로 가는 최소 비용을 차례대로 계산합니다.2. 최단 거리를 찾는 방법은 우선 최단 거리가 확정된 노드를 하나씩 확정하면서, 그 노드와 연결된 다른 노드들의 거리를 갱신하는 방식입니다.3. 우선순위 큐(Priority Queue) 를 사용하여, 현재까지 계산된 최소 비용을 기준으로 가장 작은 값을 가진 노드를 먼저 처..

에라토스테네스의 체 (Sieve of Eratosthenes) 는 주어진 범위 내에서 소수를 구하는 알고리즘입니다. 이 방법은 모든 자연수 중에서 소수만을 찾아내는 알고리즘으로, 시간 복잡도가 `O(n log(log n))`으로 매우 효율적입니다. 기본 아이디어는 2부터 시작하여 각 숫자의 배수를 모두 지워 나가는 방식입니다.에라토스테네스의 체 개념:1. 배수 지우기: 2부터 시작하여, 2의 배수들(4, 6, 8, ...)을 모두 지웁니다. 그다음 3의 배수들(6, 9, 12, ...)을 지우고, 4는 이미 지워졌으므로 5의 배수들(10, 15, 20, ...)을 지웁니다. 이런 식으로 숫자를 지워 나갑니다.2. 남은 숫자들: 마지막에 남은 숫자들은 모두 소수입니다.에라토스테네스의 체 알고리즘의 핵심:-..

`List`는 순서가 있는 원소들의 집합을 나타내는 자료구조입니다. `List`는 중복 원소를 허용하며 각 원소가 인덱스를 가지는 순서가 있는 컬렉션입니다. 자바에서 `List`는 `java.util.List` 인터페이스를 구현한 다양한 클래스들로 제공됩니다.List의 특징1. 중복 원소 허용: `List`는 같은 값을 여러 번 저장할 수 있습니다.2. 순서 보장: `List`는 원소들이 추가된 순서대로 저장되며, 각 원소는 인덱스를 가지고 있어 순차적으로 접근할 수 있습니다.3. 인덱스를 통한 접근: `List`는 인덱스를 통해 특정 원소를 빠르게 조회할 수 있습니다.4. 동적 크기: `List`는 동적으로 크기가 늘어나고 줄어듭니다. 즉, 배열과 달리 크기를 미리 정의할 필요가 없습니다.List를 구..

`Set`은 집합을 나타내는 자료구조입니다. 집합은 중복된 원소가 없고 원소들 간에 순서가 중요하지 않은 데이터 구조입니다. `Set`은 기본적으로 중복을 허용하지 않으며, 각 원소가 한 번만 존재하도록 보장합니다.Set의 특징:1. 중복 허용하지 않음: `Set`에 값을 추가할 때 이미 존재하는 값은 추가되지 않습니다.2. 순서 없음: `Set`은 원소의 순서를 보장하지 않으며, 일반적으로 `HashSet`과 같은 구현체는 내부적으로 순서에 상관없이 원소를 저장합니다.3. 자동 정렬이 없음: `HashSet`은 정렬되지 않지만, `TreeSet`은 원소들을 자동으로 오름차순으로 정렬하여 저장합니다.4. 효율적인 검색: `Set`의 주요 특징 중 하나는 중복 원소를 자동으로 제거하고 검색, 추가, 삭제 ..

1. 조합 (Combination)조합은 주어진 원소들 중에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 경우를 말합니다. 즉, 선택된 원소들의 순서가 중요하지 않으며, 같은 원소를 여러 번 선택할 수 없습니다.예시:주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:- 가능한 조합은 `{1, 2}, {1, 3}, {2, 3}`입니다.수학적 정의:- `n`개의 원소 중에서 `r`개를 선택하는 조합의 수는 `C(n, r) = n! / (r! * (n - r)!)`입니다. 조합 구현:- 조합을 구하는 방법은 순열과 달리 순서가 중요하지 않으므로, 중복을 피하면서 원소를 선택하는 방식으로 구현됩니다. 재귀적으로 원소를 선택하고, 선택된 원소를 포함한 조합을 탐색합니다. 백트래킹 방식을 사용합니다.i..

1. 순열 (Permutation)순열은 주어진 원소들 중에서 순서를 고려하여 특정 개수의 원소를 선택하는 경우입니다. 주어진 원소들에서 중복 없이 선택한 원소들의 순서가 중요합니다.예시:주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:- 가능한 순열은 `(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)`입니다.수학적 정의:- `n`개의 원소 중에서 `r`개를 선택하는 순열의 수는 `P(n, r) = n! / (n - r)!`입니다. 순열 구현:- 백트래킹은 가능한 모든 경우의 수를 시도하면서 불필요한 부분은 빠르게 가지치기하여 탐색을 줄이는 기법입니다. 순열을 구할 때 주로 사용되며, 각 원소를 선택하는 모든 경우를 탐색합니다. import java.util.*..

그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 문제를 해결할 때, 매 단계에서 최선의 선택을 하는 알고리즘입니다. 이 알고리즘은 전체 문제를 해결하기 위한 국소 최적화(local optimum)를 선택하며, 이를 통해 전체 문제의 전역 최적화(global optimum)를 달성한다고 가정합니다. 그리디 알고리즘은 일반적으로 탐욕적인 선택이 항상 최적의 해결책으로 이어지는 문제에 적합합니다. 그리디 알고리즘의 특징1. 현재 상황에서 최적이라고 생각되는 선택을 한다: 그때그때 가장 좋은 선택을 하기 때문에 미래를 고려하지 않습니다.2. 문제를 해결할 수 있는 "단계적" 접근 방식을 사용합니다.3. 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니므로, 이 알고리즘을 적용할 수 있는 문제..

완전탐색 알고리즘 (Brute Force Algorithm)완전탐색 알고리즘은 주어진 문제의 모든 가능한 해를 탐색하여 최적의 해를 찾는 방법입니다. 이 방법은 가능한 모든 경우를 하나하나 대입하거나 확인하는 방식으로 동작합니다. 일반적으로 완전탐색은 최적화된 알고리즘에 비해 비효율적일 수 있지만, 문제의 크기가 작거나 해가 존재하는 범위가 제한적일 때 유용하게 사용됩니다. 완전탐색의 특징- 모든 가능한 경우를 고려: 문제에 대한 모든 가능한 해결책을 찾으므로, 정확한 해를 보장합니다.- 효율성: 경우의 수가 많을수록 시간 복잡도가 기하급수적으로 증가할 수 있어 비효율적입니다.- 간단한 구현: 문제의 해법을 구체적으로 정의할 수 있을 때 비교적 구현이 간단합니다. 완전탐색 알고리즘이 사용될 수 있는 문제..