live, learn & love

최적화 문제를 해결하기 위한 알고리즘 패러다임 중 하나로, 하위 문제의 해결 결과를 저장하고 활용하여 중복 계산을 피하는 방법 탑다운(DP with Memoization) 재귀적인 방식으로 문제를 해결하면서 중복 계산을 피하기 위해 이전에 계산한 결과를 메모리에 저장 재귀 함수와 메모이제이션(캐싱) 바텀업(Bottom-Up DP) 작은 부분 문제부터 시작하여 전체 문제의 해결 방법을 구하는 방식 반복문을 사용하며, 주로 반복적 동적 프로그래밍 또는 테이블을 활용 0/1 배낭 문제(Knapsack Problem) 일정한 용량을 가진 배낭에 가치와 무게가 다른 물건들을 넣을 때 최대 가치를 얻는 문제 무게 제한이 있는 배낭 문제와 무게 제한이 없는 배낭 문제로 나뉨 최장 증가 부분 수열(LIS - Longe..

그래프 구조를 다루고 문제를 해결하기 위한 다양한 알고리즘으로 그래프의 형태, 방향, 가중치 등에 따라 다양한 종류로 분류 깊이 우선 탐색 (Depth-First Search, DFS) 그래프를 탐색할 때 깊이를 우선으로 하여 노드를 방문 스택 또는 재귀를 사용하여 구현하며, 주로 연결 요소의 탐색에 사용 너비 우선 탐색 (Breadth-First Search, BFS) 그래프를 탐색할 때 너비를 우선으로 하여 노드를 방문 큐를 사용하여 구현하며, 최단 경로, 트리의 레벨 순회 등에 활용 최단 경로 알고리즘 그래프에서 두 노드 간의 최단 경로를 찾음 다익스트라 알고리즘과 벨만-포드 알고리즘 최소 신장 트리 (Minimum Spanning Tree, MST) 그래프에서 모든 노드를 포함하면서 간선의 가중치..

데이터 집합에서 특정 항목을 찾는 데 사용되는 방법 선형 탐색 (Linear Search): 데이터를 처음부터 끝까지 순차적으로 검색하는 방법이며 시간 복잡도는 O(n) public class LinearSearchTest { public static int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // 찾은 경우 해당 인덱스 반환 } } return -1; // 찾지 못한 경우 -1 반환 } public static void main(String[] args) { int[] arr = {4, 2, 8, 1, 7, 5}; int target = 7;..

데이터를 특정한 순서로 정리하는 방법 선택 정렬 (Selection Sort): 가장 작은 값을 선택하여 맨 앞으로 이동시키는 방식으로 정렬 public class SelectionSortTest { public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } public static voi..