[생각의 흐름] 1. 최대 경로를 먼저 cache한다. (https://d-yong.tistory.com/107 와 동일) 2. 아래로 가는 경우 / 오른쪽 아래로 가는 경우 중 최대 경로가 큰 값을 경우의 수에 추가한다.(단, 두 값이 같은 경우 두 경우의 수를 모두 더한다.) /* https://www.algospot.com/judge/problem/read/TRIPATHCNT */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; int cache[MAX_SIZE][MAX_SIZE]; int cacheCnt[MAX_SIZE][MAX_SIZE]; ..
[생각의 흐름] - 오답 1. 수열A와 수열B의 LIS를 구해 더한다 -> 위와 같은 로직이면 예제 {10, 20, 30, 1, 2} {10, 20, 30} 일 때 정답은 {10, 20, 30}으로 JLIS의 길이는 3이됨 (정답은 5) 2. 수열A와 수열B의 중복 된 수를 한 쪽 수열에서 제거 한 뒤 각각 LIS를 구해 더한다. -> 문제의 예제에서 정답은 나오나 코드 제출 시 오답나옴 -> 중복이 제거되어도 1과 같은 수열 케이스가 나오면 오답 [생각의 흐름] - 정답 1. 수열A와 수열B의 모든 수를 따지면서 LIS를 구한다. -> "수열A의 수를 선택하거나 수열B의 수를 선택하거나"의 부분문제로 정의한다. 2. cache사용을 위해 계산의 중복이 있는지 찾아본다. -> 예를들어 {1, 5, 9, ..
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^100이라 타임 아웃 발생 2. 동적계획법을 통해 캐싱 3. 캐싱은 cache[Y][X][sum]을 먼저 생각했으나 sum의 경우 100000 * 100이 되어 메모리 초과발생 4. cache[Y][X]가 가능한지 고민 => Y, X일 때 최대값만 구하면 된다. => 아래(Y+1, X)와 오른쪽 아래(Y+1, X+1) 의 값 중 큰 값을 선택 /* https://www.algospot.com/judge/problem/read/TRIANGLEPATH */ #include #include #include using namespace std; const int MAX_SIZE = 101; int n; int triangle[MAX_SIZE][MAX_SIZE]; ..
[생각의 흐름] 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..
https://www.algospot.com/judge/problem/read/PICNIC [생각의 흐름] 1. 완전탐색으로 짝을 구한다. 2. 친구 관계를 2차원 vector로 추상화 한다. 3. 짝이 지어졌는지 확인하기 위해 boolean타입 isPiar배열로 체크한다. 4. (1,0) (0,1)과 같은 중복케이스를 제거하기 위해 순차적으로 짝을 정해준다 (0, 1)만 가능하게 /* 소풍 PICNIC https://www.algospot.com/judge/problem/read/PICNIC */ #include #include #include using namespace std; const int MAX_CHILDREN = 10; bool isPair[MAX_CHILDREN]; int C, n, m,..
https://www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 www.algospot.com [생각의 흐름] 1. 시작 위치를 정한뒤 8방향으로 완전 탐색을 해보자 -> 완전탐색 시 timeout 발생 2. DP문제임을 고려해보고 중복되는(연산) 부분 고민 -> 단어의 현재 알파벳위치와 x, y의 값을 이용하면 캐싱 가능? -> 경우의 수는 항상 같기 때문에 캐싱 가능 -> 메모이제이션으로 시간초과 해결 /* BOGGLE 보글 게임 htt..
