알고리즘/알고리즘 문제 [easy](24)
-
[탐욕법] STRJOIN 문자열합치기
1. 탐욕법 문자들을 합쳐 문자열을 만드는데 드는 비용이 최소가 되게 선택하려면 일단 가장 작은 문자 두개를 선택해 합쳐나가야 할 것 같다. 합쳐진 문자열에 또 합치게 되면 이전에 합치게한 문자열이 중복으로 또 다시 카운트 되기 때문이다. 2. 증명 탐욕적 선택 속성을 증명하기 위해 먼저 가장 작은 두 문자가 서로 합쳐지지 않은 최적해가 있다고 해보자 a와 b가 가장 작은 두 수 일때 먼저 다른 문자열과 합친것을 다음과 같이 표현했다. X = b + B Y = a + C 거리가 같은경우 : X + Y 일 경우 a 와 B를 바꾸어도 비용은 일정하므로 답은 변하지 않는다 거리가 다른 경우: X + a 일경우 a와 B를 바꾸게 될경우 B가 병합되는 횟수가 적어져 비용이 줄어들게 된다. 그러므로 작은 두 문자열..
2021.01.18 -
[탐욕법] LUNCHBOX 도시락 데우기
1. 탐욕법 이 문제는 전자레인지를 데우는 시간의 총 합은 변하지 않는다 이 총합과 어떤 음식하나를 다 먹는 시간 의 합의 최소값이 문제에서 구하라는 해이다. 점심시간을 최소화하기 위해서 일단 음식하나에의해 좌우 되니 음식 먹는 속도가 느린 사람이 제일 먼저 전자레인지를 돌릴꺼 같다. 2. 증명 만약 음식 먹는 속도가 느린사람이 첫번째로 안오는 최적해를 생각해보자 맨 처음 사람과 속도가 제일 느린 사람의 순서를 바꿔보자 순서를 바꿔도 최적해인것에는 변함이 없다. 그러므로 속도가 느린 사람부터 선택하는 방법은 최적해에 포함된다. 부분문제 또한 자명하다. 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..
2021.01.18 -
[동적 계획법] DRAGON 드래곤 커브
1. 완전 탐색 이 문제는 다음 과 같은 규칙이 있다 gen 0: gen0 gen 1: gen1 gen 2: gen1 + -gen1 gen 3: gen2 + -gen2 gen 4: gen3 + -gen3 . . . gen n: gen n + -gen n 여기서 -gen1은 gen1의 가운데 부호를 마이너스를 바꾼 것이다. 이를 통해 우리는 완전 탐색 함수를 구현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 std::string minusDragon(int gen) { if(gen == 1) return "FX-YF"; return dragon(gen-1) + "-" + minusDragon(gen-1); } std::string dragon(int gen) { if(gen == 0) re..
2021.01.15 -
[동적 계획법] PACKING 여행짐 싸기
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 #include #include #include #include #include class pac { public: std::string name; int imminence; int w; pac(); pac(std::s..
2021.01.13 -
[동적 계획법] NUMB3RS 두니발 박사의 탈옥
1. 완전 탐색 이 문제는 day만큼 날이 지난다음 q의 마을에 p에서 탈옥한 박사가 있을 확률을 구하는 문제이다. 날마다 박사는 인접한곳으로 이동한다. 그러므로 완전 탐색으로 풀때에는 p에서 시작해서 확률을 곱해가며 모든 경우의 수를 세면서 마지막 날일 때 ret[town] += 해당 경우의 확률 이처럼 더해가면된다 그 후 ret[0] ret[2] 를 호출하게되면 바로 바로 답이 나오게 된다. 2. 점화식 이 문제에서 동적 계획법을 적용하려면 완전 탐색 과는 다르게 뒤에서 부터 생각해야한다. FIND(remainDay, startpoint) = Σ(per(startpoint) * FIND(remainday - 1, next)) remainDay의 날짜가 남았을 떄 startpoint부터 시작하여 교도소..
2021.01.11 -
[동적 계획법] Quantization
1. 완전 탐색 알고리즘 이 문제는 입력으로 주어진 배열을 먼저 정렬해야한다. 정렬을 하고나면 이 문제는 간단히 풀 수 있다. 어떤 구간에서 평균값이 오차의 최소값이므로 우리는 부분문제를 평균값과 오차의 제곱 합을 따로 구할 수 있는 함수를 구현만하면 된다. end quant(begin) = min(quant(hi)+ quantization(begin, hi)) begin = 0 hi = 1 quantization(begin, hi)는 begin부터 hi까지 배열의 평균값 오차의 제곱 합을 반환하는 함수이다. 2. 메모이제이션 적용 Cache[begin][usednum] = usednumb만큼 양자화를 수행한 상태에서 begin으로 시작하는 배열의 양자화 오차 제곱의 합의 최소값을 가짐 usednumb만..
2021.01.09