LIS 문제를 해결하는 방법은 두 가지가 있다. 1. 수열 중 LIS를 만족하는 모든 경우의 수 확인 + 메모이제이션 / 시간복잡도 (N^2) 2. LIS가 항상 순증가 한다는 특성을 활용한 방법 (길이가 i인 LIS 중 가장 유리한 LIS는 마지막 값이 최소인 LIS) / 시간복잡도 (NlogN) 1번 방식 [생각의 흐름] 1. 재귀 함수를 통해 모든 경우의 수를 구한다. 2. 부분문제로 정의 할 때 현재 수열에서(subsequence[startPosition]) LIS값을 구하는게 최적의 값 3. 메모이제이션을 통해 중복 된 계산을 제거 /* https://www.algospot.com/judge/problem/read/LIS */ #include #include #include using names..
[생각의 흐름] 1. 완전 탐색으로 솔루션 도출 가능 (오른쪽이동 & 아래이동) 2. map의 각 포지션마다 메모이제이션 가능한 것을 파악 => 어떤 포지션이던 항상 결과는 동일 (참조적 투명성) /* https://www.algospot.com/judge/problem/read/JUMPGAME */ #include const int MAX_MAP_SIZE = 101; int n; int map[MAX_MAP_SIZE][MAX_MAP_SIZE]; int cache[MAX_MAP_SIZE][MAX_MAP_SIZE]; void init() { for (int i = 0; i < MAX_MAP_SIZE; i++) { for (int j = 0; j < MAX_MAP_SIZE; j++) { cache[i][j]..
[생각의 흐름] 1. 모든 경우의 수 중 가장 넓은 사각형의 넓이를 구하려고 시도 => N^2으로 시간초과 발생 2. 분할정복을 시도 3. 가운데 사각형을 기준으로 1)왼쪽 전체 사각형 2)오른쪽 전체 사각형 3)가운데 포함 좌우 사각형 추가하는 세가지 경우로 나눔 4. 가운데 포함 좌우 사각형의 경우 좌,우를 선택할 때 높이가 더 높은 사각형부터 추가함 => 작은 사각형을 먼저 추가하면 최대 값을 구할 수 없는 경우가 생김 /* https://www.algospot.com/judge/problem/read/FENCE */ #include #include #include const int MAX_FENCE = 20002; using namespace std; int N; int fenceHeight[MA..
[생각의 흐름] 1. 쿼드 트리의 이해 아래 순서로 흑/백 압축을 한다. 1 2 3 4 2. 쿼드트리 상하 반전 어떻게 처리할까? -> 뭔가 규칙이 있을 것 같다 3. 문제의 example을 보니 1, 2, 3, 4 를 3, 4, 1, 2로 바꾸면 상하반전이 된다. 4. 현재 level에서 노드를 4개로 묶어서 상하반전 시키면 되겠다. 5. x는 어떻게 처리하나? -> 분할정복으로 처리하고 올라온다. /* 쿼드 트리 뒤집기 https://www.algospot.com/judge/problem/read/QUADTREE */ #include #include char str[1001]; int len; void inverseNode(int nodeStart[], int nodeEnd[]) { char tmpS..
