반응형 알고리즘 썸네일형 리스트형 LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이.. [C++] STL - sort STL에서 제공하는 sort 함수를 알아보자. 우선 sort 함수를 이용하기 위해서는 헤더 파일을 include 해주어야 한다. sort함수는 퀵정렬을 기반으로 하므로 O(nlogn)의 평균 시간 복잡도를 가진다. sort 함수의 형태는 아래와 같다. 1 2 3 4 5 template void sort(T start, T end); //default 오름차순 template void sort(T start, T end, Compare comp); //compare 함수 정의 가능 위처럼 정렬 기준이 되는 함수 (comp) 를 추가하지 않는다면 기본적으로 '오름차순'으로 정렬해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; .. Knuth's Optimization Knuth's Optimization은 Dynamic Programming의 점화식이 아래와 같은 특정 조건을 만족하는 경우 사용할 수 있는 "최적화" 기법이다. i) DP 점화식 형태 $ dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C[i][j] $ $ (i\le k [BOJ 1725] 히스토그램 1725번 (히스토그램) 위의 문제는 분할 정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다. 1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우 1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다. 문제에서 출력이 20억을 넘지 않는다고 하였으니, 변수 자료형을.. [BOJ 1992] 쿼드트리 1992번 (쿼드트리) 위와 같이 문제가 주어져 있다. 주어진 크기 안의 숫자가 모두 0이거나 모두 1이어야 하고, 만약 이를 만족하지 않는다면 다시 사각형을 4등분하기 때문에 재귀함수를 이용해야 한다는 생각을 할 수 있다. 따라서 분할정복으로 아래와 같이 코드를 작성하면 된다. quadtree라는 재귀함수를 작성하여, 해당 사각형내의 숫자가 모두 같은 경우에는 그 숫자를 출력하고, 같지 않다면 ( 괄호를 출력하고, 4등분한 사각형에 각각 재귀함수를 호출해준다. 볼록 껍질 (Convex Hull) 볼록 껍질 (Convex Hull) 볼록 껍질이란? "2차원 평면 상에서 주어진 점들을 모두 포함하는 가장 작은 다각형" (이 때, 다각형의 각 변들은 주어진 점을 양 끝점으로 갖는다) 기하 알고리즘에서 볼록 껍질이 자주 응용되기 때문에 중요한 알고리즘이다. 볼록 껍질을 구하는 데에는 '그라함 스캔 알고리즘(Graham's Scan Algorithm)'이 이용된다. 볼록 껍질 (Convex Hull) 구하는 과정은 다음과 같다. 1. 주어진 점들 중 y좌표가 가장 작거나 혹은 y좌표가 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택 2. 선택한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬 (각을 이용) 3. 그라함 스캔 알고리즘.. [BOJ 2166] 다각형의 면적 2166번 (다각형의 면적) CCW 알고리즘을 이용하여 다각형의 꼭짓점만으로 다각형의 면적을 구하는 문제이다. 코드의 자세한 원리는 CCW(Counter-ClockWise) - (2) 게시글 (https://wogud6792.tistory.com/12) 에서 확인할 수 있다. 주어지는 점들의 좌표가 모두 정수인데 왜 실수로 출력하라는지 정확히는 모르겠지만.. 이것때문에 꽤나 애를 먹었다. CCW (Counter-ClockWise) - (2) CCW (Counter-ClockWise) - (2) 이전 게시글 (CCW (Counter-ClockWise) https://wogud6792.tistory.com/10) 이번 게시글에서는 CCW알고리즘이 어떻게 이용되는지를 알아볼 것이다. 우선 CCW 알고리즘 코드는 다음과 같다. 소개할 내용은 아래와 같이 총 3가지이다. 1. 두 선분의 교차 여부 2. 다각형의 넓이 3. 볼록 껍질 (Convex Hull) 이 중에서 3. 볼록 껍질은 기하 알고리즘에서 중요한 파트이므로 별도의 게시글로 작성할 예정이다. 1. 두 선분의 교차 여부 평면상에서 어떤 두 선분이 주어졌을 때, 이 두 선분이 교차하고 있는지를 어떻게 판단할까? 이는 CCW알고리즘을 이용하면 매우 쉽게 판단할 수 있다. 위의 그림과 같이 선분.. 이전 1 ··· 3 4 5 6 7 다음
