알고스팟(70)
-
[동적 계획법] 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 -
[동적 계획법] WILDCARD 와일드 카드
동적 계획법을 적용한 문제 풀이 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 117 #include #include #i..
2021.01.07 -
[동적 계획법, 그래프] 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 -
[분할 정복] QUADTREE
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 #include #include //all black -> b //all white -> w //all different - > quad : x(left up)(right up)(left down)(right down) //Upside down void dividePicture(const std::string& picture, std::string (&pieces)[4], int index, int currentPiece, int count) { if..
2021.01.03