728x90 반응형 2023-1/알고리즘10 배낭 채우기 문제 n개의 물건이 있다. 각 물건은 무게와 가치가 정해져있다. 무게는 w[n]={...}, 가치는 p[n]={...}이다. W = 배낭에 넣을 수 있는 총 무게라고 할 때, "W 2023. 6. 18. 알고리즘 설계 - 그리디 그리디 알고리즘은 현재 상태에서 가장 최적이라고 생각되는 결정을 계속해서 취하는 방식의 알고리즘이다. Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘은 모두 그리디 알고리즘에 속하며, 그래프에서 최적의 경로를 찾는 데 주로 사용된다. 1. **Prim 알고리즘 (Prim's Algorithm)**: Prim 알고리즘이란 주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리는 그래프의 모든 정점을 연결하는 간선들의 가중치 합이 최소인 트리를 말한다. Prim 알고리즘은 특정 정점에서 시작하여 가장 가중치가 낮은 간선을 선택하면서 트리를 확장해 나간다. 2. **Kruskal 알고리즘 (Kruskal's Algorithm)**: Kruskal 알고리즘도 Prim 알고리.. 2023. 6. 18. 알고리즘 설계- 동적 프로그래밍 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 분해하고, 그것으로부터 최적의 해결책을 찾는 알고리즘 기법이다. 이 방식은 각 부분 문제의 해를 저장하고 ("메모이제이션"이라고 함), 필요할 때 다시 사용해서 중복 계산을 방지한다. 동적 프로그래밍은 주로 최적화 문제에서 사용되며, 아래 두 가지 속성을 만족하는 문제에 적용할 수 있다: 1. **최적 부분 구조(Optimal Substructure)**: 큰 문제의 최적의 해를 그 문제의 작은 부분 문제들의 최적의 해로부터 구할 수 있어야 한다. 2. **중복되는 부분 문제(Overlapping Subproblems)**: 같은 부분 문제들이 여러 번 반복해서 나타나는 경우, 이 부분 문제들의 결과를 저장하고.. 2023. 6. 18. 알고리즘 설계 - 분할 정복 분할 정복(Divide and Conquer)은 큰 문제를 더 작은 하위 문제로 나누고, 이러한 하위 문제를 해결하여 원래의 문제를 해결하는 방식이다. 분할 정복 방법은 주로 재귀적으로 구현되며 이를 하향식 접근방법이라고 한다. 분할 정복 알고리즘은 일반적으로 다음 세 단계를 거친다. 1. **분할(Divide)**: 원래의 문제를 더 작은 하위 문제로 분할. 2. **정복(Conquer)**: 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작아서 직접적으로 해결할 수 있을 때까지 이 과정을 반복. 3. **결합(Combine)**: 하위 문제의 해결책을 결합하여 원래의 문제를 해결. 분할 정복법에 해당하는 알고리즘들 : 이진 검색, quick sort, 행렬 곱셈(strassen 방법) 이.. 2023. 6. 17. String(3-way quicksort, huffman 코딩) 3-way quicksort 알고리즘이다. 문자를 비교해서, 문자가 더 작으면 위로, 더 크면 아래로 보내서 (작은거)(같은거)(큰거)로 나눈다. 이렇게 나누어놓은 문자열들끼리 또 정렬하도록 한다.(재귀) public class QuickSort3Way { public static void sort(String[] arr) { sort(arr, 0, arr.length - 1); } private static void sort(String[] arr, int low, int high) { if (high 2023. 6. 17. 최적 이진 검색 트리/ AVL 트리 최적 이진 검색 트리 최적 이진 탐색 트리(Optimal Binary Search Tree)는 이진 검색 트리(Binary Search Tree, BST)의 일종으로, 주어진 키 집합에 대해 평균 검색 비용이 최소가 되도록 구성된 트리입니다. AVL트리 AVL트리는 이진 탐색 트리의 일종으로, 자동으로 균형을 유지하는 자료구조입니다. 글로 적기 힘들어서 영상으로 찍음. 2023. 3. 29. Search Structures 1. Symbol Table (키,값)쌍의 모임을 symbol table이라고 한다. 사전에서 특정 단어(키)를 이용하여 뜻(값)을 알아내는 것도 심볼테이블의 응용분야이다. symbol table public class SymbolTable { void put(Key k,Value v); Value get(Key k) boolean contains(Key k) void delete(Key k) boolean isEmpty() int size() Iterator keys() } 심볼테이블은 보통 위와같은 메소드들을 가진다. 여기서는 Generics 지원하며, 중복키는 허용하지 않는다. 만약 중복키가 입력될 경우 기존의 값을 새 값으로 변경한다. 키와 값은 null이 될 수 없고, 테이블에 없는 키값으로 검.. 2023. 3. 20. 외부 정렬(External Sort) 외부정렬은 대용량의 데이터를 정렬하는 알고리즘으로, 메모리보다 큰 데이터셋을 정렬할 때 사용된다. 외부정렬은 기본적으로: 정렬할 파일을 메모리에 적재가능한 크기의 run들로 분할한다. 각 run에 대해 내부 정렬 후 다른 파일에 저장한다. 파일에 저장된 run들을 병합하여 다시 파일에 저장한다. 병합된 run의 수가 1이 될 때까지 병합을 반복한다. 병합 방법에 따라 sort/merge 알고리즘은 다음과 같이 분류할 수 있다. Binary Sort/Merge Balanced Binary Sort/Merge Balanced K-way Sort/Merge Polyphase Sort/Merge Binary Sort/Merge Sorting phase - 초기 run들을 정렬한 후, 2개의 외부 파일에 저장 M.. 2023. 3. 16. 버킷 정렬, 기수 정렬, 병합 정렬 버킷 정렬: 1.입력 배열의 원소들을 해당하는 버킷에 저장 2. 각 버킷을 정렬함. 3. 버킷을 차례로 방문하여 원소들을 원 배열에 저장 기수 정렬(Radix sort) -높은 자리 우선 정렬(MSD) -낮은 자리 우선 정렬(LSD) 가 있음. 이 때 LSD방식은 버킷별로 별도 정렬 단계가 필요 없으므로 MSD보다 많이 사용됨. LSD를 이용한 기수 정렬 입력 데이터에서 가장 큰 숫자를 max라고 할 때, 입력 데이터를 일의자리 수부터, max의 최대자릿수까지,한 값을 기준으로 삼아 차례대로 counting sort를 반복한다. public class Radix { public static void sort(int[] A){ int i,m = A[0], exp=1, n=A.length; int[] B =.. 2023. 3. 13. [알고리즘] 선택정렬, 삽입정렬, 쉘 정렬 (추상클래스 AbstractSort) 더보기 public abstract class AbstractSort { public static void sort(Comparable[] a) {}; protected static boolean less(Comparable v, Comparable w) { return v.compareTo(w)1칸 떨어진 원소들끼리 삽입정렬 순으로 정렬을 진행함. 그럼 뒤에있는 원소가 제일 작은 값일때도 금방 앞으로 보낼 수 있게 된다. public class Shell extends AbstractSort{ public static void sort(Comparable[] a) { int N = a.length; int h = 1; while(h=1) { for(int i=h;i.. 2023. 3. 7. 이전 1 다음 728x90 반응형