조합 탐색(2)
-
[조합 탐색] ALLERGY 알러지가 심한 친구들
1. 완전 탐색(시간초과, 잘못된 구현) 이 문제는 각 친구들이 먹을 수 있는 음식이 하나라도 먹을 수 있게 하는 최소한의 메뉴를 선정하는 문제이다. 이 문제는 다음과 같이 완전 탐색할 수 있다. - 친구들을 기준으로 탐색 - 음식들을 기준으로 탐색 모든 친구들이 먹을 수 있는게 하나라도 있어야하므로 친구들을 기준으로 탐색하는게 더욱 구현이 직관적일 것이다. 코드는 다음과 같다. 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 6..
2021.01.20 -
[조합 탐색][시도x]BOARDCOVER2 게임판 덮기2
1. 완전 탐색 주어진 블록으로 빈 공간에 넣을 수 있는 최대 개수를 구하는 문제이다. 이 문제를 풀기 위해서는 일단 다음과 같은 함수가 필요할 것 같다. - 블록들을 회전 시키는 함수. - 왼쪽위에서부터 오른쪽아래까지 블록을 넣는지 않넣는지 , 블록을 넣을때 회전하는 케이스 까지 모든 경우를 세는 함수. 이 완전 탐색으로는 시간안에 못풀것 같다. 10*10 의 빈 공간이 있으면 최대 5^100번 함수가 실행 될것 같기 때문이다. (5가지 경우 수 선택 x 0 90 180 270에 100개의 칸) 물론 이것이 실제 돌아가면 훨씬 더 빨리 수행될것이다. 하지만 그래도 엄청나게 큰 수행시간 일 것이다. 2. 조합탐색 - 가지치기 단순 휴리스틱 함수를 구현하면 더욱 빨리 수행될 것 같다. 이 함수는 남은 칸의..
2021.01.20