[생각의 흐름] 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..
[생각의 흐름] 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..
골라야 할 원소의 수(M)가 입력에 따라 달라지는 경우 반복문 보다 재귀를 사용하면 유연하게 대처할 수 있다. 0부터 N-1까지의 수중에 M개를 고르는 모든 경우의 수를 구하는 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include #include using namespace std; int maxN, maxM; void printNumber(vector& picked) { int cnt = picked.size(); for(int i=0; i
