알고리즘/알고리즘 문제 [medium](24)
-
[동적 계획법] ASYMTILING 비대칭 타일링
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 #include #include const int MOD = 1000000007; int wide = 0; int cache[100][100][3]; int asy(int vertical, int horizontal, int before) { int &ret = cache[vertical][horizontal][before], ishalf = 0, width = vertical+ indexx; if(ret != -1) return ret; if (wide % 2 == 0 && ((width == wide/2 + 1 && befor..
2021.01.10 -
[동적 계획법] Longest Increasing Sequence, JLIS 합친 LIS
-jlis 문제를 푸는 과정에서의 나의 잘못된 접근방법 1. LISLongest Increasing Sequence jlis 문제를 풀기전에 알고리즘 문제해결전략 책에 나와있는 LIS의 더 빠른 알고리즘을 구현하였다. (동적계획법을 사용한 O(n^2)알고리즘과 다르게 O(nlgn)만에 수행된다.) 이 알고리즘은 배열의 각 원소들을 앞에서 부터 탐색해나가며 다음과 같은 배열에 원소들을 집어넣는다. C[i] = 지금 까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막값 C[i]에 원소들을 집어 넣을 때 push()함수가 쓰이는데 이 함수는 삽입정렬과 비슷하며 다음과 같이 작동한다. C[i] 배열에 x라는 원소를 삽입하고자할 때 이 함수는 i에서 시작하여 1까지 탐색하여 lo < x && x
2021.01.08 -
[동적 계획법, 그래프] JUMPGAME 외발 뛰기
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 #include #include #define UNTRAVELED -1 #define NO 0 #define YES 1 int cache[100][100]; int board[100][100]; int dy[2]{1,0}; int dx[2]{0,1}; bool inRange(int y, int x, int n) { return ((y n; memset(cache, -1, sizeof cache); for(int j{0}..
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 -
[Brute-force, Dynamic] 보글 게임
brute-force 핵심함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 const int dx[8] = { -1, -1, -1, 1, 1, 1, 0, 0}; const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1}; bool hasWord(int y, int x, const string& word) { if(!inRange(y,x)) return false; if(board[y][x] != word[0]) return false; if(word.size() == 1) return true; for(int direction = 0; direction 3으로 표현하여 size()가 가장 작은 알파벳으로 분할하면 더 빨리 풀 수 있을 것이다. - 3..
2020.12.28