알고리즘(170)
-
[탐욕법] 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 -
[탐욕법] Greedy method
1. 탐욕법 가장 직관적인 알고리즘 설계 패러다임 중 하나임 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없음. 그러나 모든 선택지를 고려해 보고 , 그중 전체 답이 가장 좋은 것을 찾는 두 방법과 다르게 각 단계마다 '지금' 당장 가장 좋은 방법만을 선택함 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음 탐욕적 알고리즘은 많은 경우 최적해를 찾지 못하고 다음과 같은 경우에만 쓸 수 있음. 1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동젹 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용 2. 시간이나 공간적 게약으로 인해 다른 방법으..
2021.01.18 -
[동적 계획법][시도X] GENIUS 지니어스
1. 완전 탐색 이 문제는 다음으로 재생될 곡은 바로 이전 곡에만 영향 받기때문에 마르코프 모델이라고 할 수 있다. 이 문제는 주어진 k분 30초에 좋아하는 노래들이 각각 나올 확률을 구하는 문제이다. 좋아하는 곡들의 번호들과 i다음으로 j가 재생될 확률을 담고있는 행렬 T가 주어지고 각 곡의 길이가 주어진다 number 음악이 min분에 재생될 확률을 구하려면 일단 0 ~min 에 number 음악이 시작되는 확률을 먼저 구해야한다. 해당 음악이 min분에 재생될 확률은 해당 음악이 min - number.len + 1에서부터 min까지 시작되는 확률을 전부 더한것과 같기때문이다. play(min, number) = min에서 number가 재생될 확률 play(min, number) = Σ ( pla..
2021.01.18 -
[동적 계획법] [시도X] SUSHI 회전 초밥
1. 완전 탐색 이 문제는 packing 문제에서 중복가능한점을 제외하고 전부 같다 따라서 이문제는 다음과 같이 쓸수있다. menu(price) = price로 시킬 수 있는 메뉴의 최대 선호도 이에 모든 메뉴를 for문으로 탐색하면서 price를 넘어가지 않도록 선택하는 재귀함수를 구현하면 답을 구할 수 있다. 2. 반복적 동적 계획법 하지만 이 문제의 price의 최대 값은 10억이다. 총 n메뉴가 있을때 값이 2만을 넘지 않으므로 n^50000시간 이상 걸릴 수 있을 것이다. 이렇게 큰 수를 메모이제이션 하려면, 슬라이딩 윈도 기법을 사용해야한다. 이 기법은 반복적 동적 계획법을 이용해야만 쓸 수 있다. menu(price) = price로 시킬 수 있는 메뉴들의 최대 선호도 합 이 식이 의미하는 ..
2021.01.18 -
[동적 계획법][비트 마스크][시도X] BLOCKGAME 블록게임
1. 완전 탐색 이 문제는 BOARDCOVER에서 문제를 풀었듯이 완전 탐색으로 해결 할 수 있다. 각 차례마다 사용 가능한 모든 블록들을 모든 위치에 넣어보면서 한번이라도 짝수 차례일때 블록을 못넣으면 함수를 종료시키면 된다. 2. 비트 마스크를 사용한 동적 계획법 이 문제는 주어진 게임판의 상태에 따라 승패가 좌우된다. 이전 까지의 블록의 배치와 지금이 누구 차례인지 알 필요 없다는 것이다. 게임판은 5*5배열로 '#' 과 '.' 두 상태가 있으므로 비트마스크로 배열을 하나의 정수로 표현할 수 있다. 이 정수 하나로 메모이제이션이 가능해지고 완전 탐색에서 더욱 수행시간을 최적화 시킬 수 있다. 3. 비트마스크를 사용한 블록 배치 가능 유무성 판단 이 문제에서 블록의 형태는 L자 형과 | 형 ㅡ 형 이..
2021.01.16