알고리즘/알고리즘 문제 [hard](20)
-
[결정 문제] [시간 초과] WITHDRAWAL 수강 철회
1. 최적 문제 n개의 강의 중에서 k개이상의 강의만 남겨놓고 철회할 때 최소 누적 등수를 구하는 문제이다. 이것은 k개 까지 하나 하나 철회해보면서 누적등수를 계산하고 그 중에서 최소값을 구하는 최적화 문제이다. 이 문제를 결정문제로 변형해보자 2. 결정 문제 isOkay(r) = r의 누적등수가 주어졌을 때 이것보다 작은값이 있는가? 위와 같은 식을 토대로 함수를 작성해 보았다. isOkay는 k개 까지 모든 경우를 세서 주어진 누적등수보다 작은 값이 나오면 true 작은 값이 나오지 않을 경우 false를 반환한다. 하지만 이 함수는 최악의 경우 2^1000 개를 카운트하므로 당연히 제출한 코드는 시간 초과를 내뿜었다. 이전 꺼랑 비교해서 더 큰값이 나올 경우 가지치기하려는 생각도 해봤지만 답을 구..
2021.01.22 -
[조합 탐색][시도x]BOARDCOVER2 게임판 덮기2
1. 완전 탐색 주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다. - 블록들을 회전 시키는 함수. - 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지 모든 경우를 세는 함수. 이 완전 탐색으로는 시간안에 못풀것 같다. 10*10 의 빈 공간이 있으면 최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸) 물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다. 하지만 그래도 엄청나게 큰 수행시간 일 것이다. 2. 조합탐색 - 가지치기 단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다. 이 함수는 남은 칸의..
2021.01.20 -
[탐욕법] [시도x] MINASTIRITH 미나스 아노르
1. 문제의 데이터를 변형해야한다. 초소의 실수 좌표들이 주어지고, 반지름이 주어진다. 이 데이터들을 가공하여 문제를 바로 푸는 것은 까다롭다. 그러므로 책에서는 이 데이터들을 중심각 구간으로 표현하였다. 중심각 이외에 원과 원이 만나는 X축 구간으로도 풀 수 있을것 같다. 2. 탐욕법 각 초소들의 구간으로 나타내면 이것은 활동 선택문제와 매우 유사하다. 하지만 이 문제는 처음 구간을 고르는게 중요하다. 원은 순환하기 때문에 처음 구간은 맨 마지막 구간과 이어지기 때문이다. 전체 구간이 0~2π 라고 할때 0 을 포함하는 구간들은 항상 두개 이하 선택 해야한다. 맨 오른쪽, 맨 왼쪽에 해당하는 구간 두개가 있으면 항상 다른 구간들은 그 구간에 포함되기 때문이다. 그리고 0 을 포함하는 구간들을 지금 선택..
2021.01.19 -
[동적 계획법][시도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