[생각의 흐름] 1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨 2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다. #include #include const int MOD = 1000000007; const int MAX_TILE_SIZE = 111; int N; int cache[MAX_TILE_SIZE]; int sol(int n) { if(n == N) return 1; if(n > N) return 0; int &ret = cache[n]; if(ret != -1) return ret; // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우 ret = (sol(n+1) % ..
[생각의 흐름] 1. 주어진 입력을 정렬하면 구현이 더 편해진다. 2. 정렬한 뒤 어떠한 기준에 따라 S개로 묶는다(양자화) 3. 어떠한 기준을 정의한다. -> a번째 부터 b번째 까지의 수열에 있는 모든 자연수 중 하나를 선택하여 오차 제곱의 합이 최소가 되는 값을 구한다. (minQuan 함수) /* https://www.algospot.com/judge/problem/read/QUANTIZE */ #include #include #include #include using namespace std; const int MAX_SEQ_SIZE = 111; const int MAX_QUAN_SIZE = 11; const int INF = 987654321; int N, S; int num[MAX_SEQ_S..
[생각의 흐름] 1. 문자열을 3, 4, 5개로 쪼갤 수 있기 때문에 재귀함수를 통해 모든 경우의 수를 구할 수 있다. 2. 1234123인 수를 쪼개는 방법은 3, 4 혹은 4, 3이다. 즉, 12341234가 N개 있으면 시간복잡도는 2^N이 된다. => 시간초과예상 3. 재귀함수가 현재 문자열의 position에 있을때 계산이 중복된다. => 메모이제이션 가능 /* https://www.algospot.com/judge/problem/read/PI */ #include #include #include using namespace std; const int INF = 987654321; const int MAX_LEN = 10001; char PI[MAX_LEN]; int cache[MAX_LEN];..
[생각의 흐름] - 오답 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. *을 제외하면 나머지는 그냥 넘어가면 된다(문자가 같다. ?와 '같은 문자'는 동일하게 처리) 2. *를 처리하는 방식은 두 가지로 나눌 수 있다. 1) *를 사용한다. 2) *를 버린다.(사용하지 않는다.) 3. 재귀함수를 돌 때, 와일드 카드와 파일명의 인덱스의 위치에 따라 중복 계산이 발생한다.=> 캐싱가능 /* https://www.algospot.com/judge/problem/read/WILDCARD */ #include #include #include #include #include #include using namespace std; const int MAX_STR = 111; char wildCard[MAX_STR]; char str[50][MAX_STR]; int ..
[생각의 흐름] 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..
아래의 코드처럼 복사 생성자, 복사 대입 연산자를 delete하여 싱글톤의 품질을 높일 수 있다. #include using namespace std; class Singleton { public: Singleton(const Singleton&) = delete; // 복사 생성자(copy constructor) 금지 Singleton& operator=(const Singleton&) = delete; // 복사 대입 연산자(copy assignment operator) 금지 static Singleton& getInstance() { static Singleton instance; // 늦은 초기화 + 쓰레드 세이프 return instance; } private: Singleton() { cout