동전 거스름돈 문제 (Coin Change Problem) 정해진 동전 d1, d2, …, dk, 거스름돈 n원 단, d1 > d2 > … > dk = 1 부분 문제 w원을 거슬러 줄 때 i번째 동전을 1개 추가할 때 동전 개수 w-di 원을 거슬러 줄 때 필요한 최소 동전의 개수 + 1개 1원씩 증가시켜서 문제 해결 C[j] = min1≤i≤k { C[j - di] + 1 }, if j ≥ di Pseudo code DPCoinChange Input 거스름돈 n원 k개의 동전 액면 d1 > d2 > … > k = 1 Output: C[n] 1. for i = 1 to n C[i] = ∞ 2. C[0] = 0 3. for j = 1 to n { // j는 1원부터 증가하는 (임시) 거스름돈 액수이고, j..
코틀린
배낭 문제 (Knapsack Problem) 물건 n개 각 물건 i, 무게 wi, 가치 vi 배낭 용량 C 위 조건에서 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제 단, 배낭에 담을 물건의 무게 합이 C를 초과하지 않고 각 물건은 1개씩만 존재 이러한 문제를 0-1 배낭이라고 명칭 부분 문제 K[i, w] 물건의 1 ~ i 까지만 고려하고, 배낭의 용량이 w일 때의 최대 가치 최적해 - K[n, C] C의 값이 매우 크면 알고리즘 수행시간이 매우 길어짐 Pseudo code Knapsack Input 배낭의 용량 C n개의 물건 각 물건 i의 무게 w 와 가치 v Output - K[n, C] 1. for i = 0 to n K[i, 0] = 0 // 배낭의 용량이 0일 때 2. for w = 0..
편집 거리 문제 (Edit Distance Problem) 문자열 S를 수정하여 문자열 T로 변환하려고 할 때 쓰이는 연산 삽입 - insert 삭제 - delete 대체 - substitude 편집 거리 - S를 T로 변환시키는데 필요한 최소 편집 횟수 편집 거리 예시 S - strong T - stone stong - r 삭제 stone - g → e 대체 총 2회 Idea 각 문자열의 접두부의 편집거리를 미리 알고있으면 부분 문제를 통해 현재를 알 수 있음 stro → sto, ng → ne를 알고 있으면 strong → stone을 알 수 있음 Pseudo code EditDistance Input S: String, T: String 단, S와 T의 길이는 m 과 n Output S를 T로 변환..
CompositionLocalProvider? 사이드 프로젝트를 진행하면서 아래와 같은 코드를 작성하게 되었습니다. CompositionLocalProvider(LocalAnalyticsHelper provides analyticsHelper) { FakeGpsTheme( darkTheme = darkTheme, androidTheme = shouldUseAndroidTheme(uiState), disableDynamicTheming = shouldDisableDynamicTheming(uiState), ) { FakeGpsApp(networkMonitor = networkMonitor) } } 해당 코드에서 CompositionLocalProvider 이 무슨 역할을 해주는지 알아보겠습니다. Compo..
연속 행렬 곱셈 (Chained Matrix Multiplications) 문제 연속된 행렬들의 곱셈에 필요한 원소간의 최소 곱셈 횟수를 찾는 문제 문제 예시 행렬 A가 10x20, 행렬 B가 20x5, 행렬 C가 5x15 (A x B) x C의 경우 A x B 계산 → 10 x 20 x 5 = 1,000번 AB x C 계산 → 10 x 5 x 15 = 750번 총 1,750번 A x (B x C)의 경우 B x C 계산 → 20 x 5 x 15 = 1,500번 A x BC 계산 → 10 x 20 x 15 = 3,000번 총 4,500번 Idea 동일한 결과값 이지만 곱셈 연산 횟수는 2,800번의 차이가 생김 곱셈 횟수를 최소화 시키기 위한 곱셈 순서를 찾아야함 주어진 행렬의 순서를 지켜서 이웃하는 행..
모든 쌍 최단 경로 문제 (All Pairs Shortest Paths) 각 쌍의 점 사이의 최단 경로를 찾는 문제 다익스트라(Dijkstra)의 최단 경로 알고리즘 이용 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행 시간복잡도는 n x O(n^2) = O(n^3) 단, n은 점의 수 2024.03.12 - [Algorithm] - [알고리즘] 다익스트라 (Dijkstra) 최단 경로 알고리즘 플로이드-워셜 (Floyd-Warshall) 알고리즘 Warshall 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안 Floyd 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워셜 알고리즘 이라 명칭 플로이드 알고리..
파일 압축 (file compression) 파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장되면, 그 파일의 bit 수는 8 x (파일의 문자 수) 주어진 파일의 크기를 줄이는 방법 허프만 압축(Huffman coding) 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당 드물게 나타나는 문자에는 긴 이진 코드를 할당 접두부 특성 (prefix property)이 존재 입력 파일에 대해 각 문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드를 할당 해당 이진 코드를 허프만 코드라고 지칭 접두부 특성 (prefix property) 각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부 (prefix)가 되지 않는다는 것 문자 ‘a’에 할당된 ..
작업 스케줄링 (Job Scheduling) 문제 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제 시작시간, 종료시간, 작업 길이에 대한 그리디 알고리즘 빠른 시작시간 작업 우선 (Earliest start time first) 배정 빠른 종료시간 작업 우선 (Earliest finish time first) 배정 짧은 작업 우선 (Shortest job first) 배정 긴 작업 우선 (Longest job first) 배정 첫 번째 알고리즘을 제외하고 나머지 3가지는 항상 최적해를 찾지 못함 Pseudo code JobScheduling(t) Input: n개의 작업 t1, t2, ⋯, tn Output: 각 기계에 배정된 작업 순서 1. 시작시간의 오름차순으로 ..
집합 커버 (Set Cover) 문제 n 개의 원소를 가진 집합 U U의 부분집합들을 원소로 하는 집합 F F의 원소들 중 선택하여 합집합이 U랑 같아지는 원소의 최소 개수 신도시 학교 배치 문제 아래 두 조건을 만족하는 학교 위치 선정 학교는 마을에 위치해야 함 등교 거리는 걸어서 15분 이내이어야 함 학교의 위치 최소 예시 문제 도식화 1. U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 2. F = {S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} 3. S1 = {1, 2, 3, 8} 4. S2 = {1, 2, 3, 4, 8} 5. S3 = {1, 2, 3, 4} 6. S4 = {2, 3, 4, 5, 7, 8} 7. S5 = {4, 5, 6, 7} 8. S6..
배낭 (Knapsack) 문제 n개의 각각 무게와 가치를 지닌 물건을 최대의 가치를 갖도록 배낭에 넣는 문제 부분 배낭 (Fractional Knapsack) 문제 물건을 나눠서 담는 것을 허용 그리디 사용 가능 0-1 배낭 문제 물건을 통째로 배낭에 넣어야 함 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결 부분 배낭 문제 그리디 알고리즘 Pseudo code FractionalKnapsack(n, weightAndPriceList, C) Input 물건 n개 각 물건의 무게와 가치 배낭의 용량 C Output 배낭에 담은 물건 리스트 L 배낭에 담은 물건 가치의 합 v 1. 각 물건에 대해 단위 무게 당 가치를 계산 2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정..
