IT/알고리즘 및 자료구조13 [알고리즘 정리] 이분 탐색 이분 탐색 시간 복잡도 : Log(N) left : 값의 범위중 가장 작은 값right : 값의 범위중 가장 큰 값mid : (left + right) / 2target : 찾으려는 값 ex) 1~100 사이의 5개의 값 1, 11, 21, 31, 99 중에서 31이 있나 찾자!left : 1, right : 100, mid : 50, target : 31 기본 코드 while (left target) right = mid - 1; else left = mid + 1; } 기본 예제 https://www.acmicpc.net/problem/1920 #include #include #include #include #include #include #include #include #include #define.. 2018. 9. 14. [알고리즘 정리] 그라함 알고리즘(Graham’s scan) 알고리즘 ccw 알고리즘(?)을 이용하여 블록 껍질(convex hull)을 뽑아내는 알고리즘 입니다. CCW(Counter Clock Wise) 알고리즘 시간복잡도는 O(nlogn) # 풀이 순서 1. 가장 x, y가 작은 ori점을 찾는다. 2. ori 이외의 점들을 반시계 방향을 정렬한다. 3. ccw를 활용하여 블록 껍질을 찾는다. ccw>0이 되었을 때만 스택에 넣어주면 된다. # 관련문제 : https://www.acmicpc.net/problem/1708 #include #include #include #include #include #include #include #include #include #define MAX 200005 #define INF 987654321 #define MOD 31991.. 2018. 8. 26. [알고리즘] 구조체를 이용한 행렬의 곱 구현 크기가 d인 행렬(d*d)의 곱 a*b를 구하는 코드 실행 코드 #include #pragma warning(disable:4996) using namespace std; int d; struct st { int m[55][55] = {}; st operator*(st a) const { st ret; for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) for (int k = 0; k < d; k++) ret.m[i][j] = (ret.m[i][j] + m[i][k] * a.m[k][j]); return ret; } }a,b,c; int main() { d=3; for(int i=0;i 2018. 8. 11. [알고리즘 정리] 최장 증가 수열(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. 이전 1 2 3 4 다음
