알고리즘76 [알고리즘 정리] 최장 증가 수열(LIS,Largest Increasing Sequence) 알고리즘 최장 증가 수열이란 주어진 수열의 부분수열중 가장 긴 증가 하는 수열을 말합니다. 예를들어, 다음과 같은 10개 원소의 수열에서 1, 3, 4, 5, 6, 9, 10의 7의 부분 수열이 가장 긴 증가 하는 수열입니다. DP를 사용한 아이디어로서, 이분탐색을 이용하여 O(NlogN)의 시간복잡도로 해결합니다. 앞에서 부터 뒤로 O(N)으로 탐색을 하고 현재 원소의 놓여질 최적의 자리를 찾는데 이분탐색을 이용하여 O(logN)이 걸립니다. 1. 처음 벡터에 -INF를 넣어줍니다. 2. 벡터의 맨 뒤의 값보다 넣으려는 1이 크기 때문에(-INF 2018. 7. 16. 백준(BOJ) 13547 수열과 쿼리5 *** # Mo's algorithm # Sqrt Decomposition 그냥 놀라웠다.... 대단했다...아직 부족하다... #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAX 100005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pi; typedef pair pf; stru.. 2018. 6. 28. 백준(BOJ) 15807 빛영우 *** # DP 이 문제는 좌표 때문인지 쉽사리 dp를 떠올리기 어려웠다. # 실수 했던 점 빛의 시작과 끝지점이 증가될때 시작지점이좌표 밖으로 나가는것을 조심해야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAX 3005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pi;.. 2018. 6. 28. 백준(BOJ) 15808 주말 여행 계획 ** # 다익스트라 알고리즘 # 실수 했던 점 기본적으로 다익스트라 알고리즘은 각 방문지의 값을 INF로 초기화 시켜놔야 하는데초기화를 안했다. 이문제의 경우 -INF로 해야한다 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define MAX 1005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pai.. 2018. 6. 28. 이전 1 2 3 4 5 6 ··· 19 다음
