알고리즘 문제해결전략(100)
-
[동적 계획법] Dynamic programming
동적 계획법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔다. 중복되는 부분 문제 없애 최적화하여 속도향상을 꾀하는 알고리즘 설계 기법이 바로 동적 계획법이다. 동적계획법은 분할 정복과 접근방식이 같다. 주어진문제 -> 더 작은문제들 -> 조각 계산 -> 조각의 답들로부터 원래 문제 답 계산 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도 향상을 꾀함 각 문제의 답을 메모리에 저장해 둘 필요가 있음 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시라고 부름 두번 이상 계산되는 부분문제를 부분 문제(overlapping subproblems)라고 부름 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 ..
2021.01.06 -
[분할 정복] FANMEETING 팬미팅
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include #include #include #include #inclu..
2021.01.05 -
[분할 정복, 스위핑, 스택, 상호 배타적 집합] FENCE 울타리 잘라내기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #include #define max(a,b) a>b?a:b #define min(a,b) a>b?b:a int fenceHeight[20000] ={0,}; int maxRec(int low ,int high) { int ret = 0, mid = (low + high)/2, left = 0, right = 0, tmpRec = 0, width = 1, height = 0; if(low +1 == high) return f..
2021.01.04 -
[분할 정복] QUADTREE
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include //all black -> b //all white -> w //all different - > quad : x(left up)(right up)(left down)(right down) //Upside down void dividePicture(const std::string& picture, std::string (&pieces)[4], int index, int currentPiece, int count) { if..
2021.01.03 -
[분할 정복] Divide & Conquer
주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀 호출을 이용해 계산 각 부분 문제의 답으로부터 전체 문제의 답을 계산 문제를 거의 같은 크기의 부분문제로 나눈다. 세가지 구성요소 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case) 자연스러운 방법으로 나누고 나눈 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 필요 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커짐 (부분 문제가 중복된다 overlapping subproblems) 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분..
2021.01.02 -
[Brute-force] Synchronizing Clocks
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 #include #include #include int clocks[4][4] = {0,}; int switchPushNum[10] = {0,}; std::vector switchToClock = { {0, 1, 2}, {3, 7..
2021.01.01