MathTrauma

문제 링크 : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제에 포함된 예를 보자. 1. Top-Down 길이가 \( l \) 인 수열이 팰린드롬인지 여부는 양끝을 조사해서 다르면 그대로 종료하고, 같으면 양끝을 제거한 \( l-2 \) 인 수열을 살펴보면 된다. #include using namespace std; int arr[20001], dp[2001][2001]; int recur(int s,int e){ if(s==e) return 1; if(s+1==e) { if(..

문제 링크 : https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 각각의 i, j 에서 변의 길이 \( l \) 을 이용하여 loop 를 돌리면 시간 복잡도는 \( O(n^4) \) 이 된다. 2차원 부분합을 미리 구했다면 \(O(n^3)\) 으로 해결할 수 있지만 시간 초과일 것이다. 앞 단계에서 최대 정사각형을 찾기 위해 조사한 것을 재활용할 수 있음을 깨닫게 되면 DP 풀이는 쉽다. 우선 문자열 2차원 배열을 정수 2차원 배열 grid 에 저장했다고 가정한다. 그리고, dp[i][j] 를 i , j 가 정사각형의..

문제 링크 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 비교적 쉬운 문제들부터 Top-Down 구현과 Bottom-Up 구현을 비교해 보고 있는데, 부족한 것이 한둘이 아니다. 이 문제에서는 두 구현에 같은 사고 방식을 적용하지 못했다. 따라서 시간 비교는 별 의미는 없지만 Top-Down 방식이 4 배 이상의 시간을 소요한다. recur( a , b ) 함수는 구간 [ a , b ] 에서 최적의 순서(최소 비용)로 결합한 비용..

문제 링크 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net dp 문제에서 top-down 방식과 bottom-up 방식의 시간을 비교하려고 풀어보았다. 규모가 너무 작아서 의미 있는 비교는 할 수 없었지만 몇 가지 언급하고 지나간다. 우선 문제의 조건에서 대각선 이동 (r,c)->(r+1,c+1) 은 필요가 없다. 사탕의 최댓값을 구하는 마당에 갈 수 있는 방을 건너뛸 이유가 있을까? 바텀업 방식의 코드부터 보자. #inclu..

문제 링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 단봉(unimodal) 수열, 즉 증가하다가 감소하는 수열의 길이를 구해야 한다. (증가수열, 감소수열은 허용된다.) arr 의 index 는 1 부터 N 까지. 최대 부분 감소 수열을 구할 수 있으면 충분하다. 원소가 하나인 수열을 생각하면, dp 의 초기값은 모두 1 이다. dp[0][i] = ( i 에서 끝나는 최대 부분 증가 수열의 길이 ) dp[1][i] = ( i 에서 시작되는 최대..

문제 링크 : https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dynamic programming 시간 분석은 나에게는 너무 어렵다. 시간이 어떻게 바뀌는지 보기 위해 두 가지 코드를 작성했는데 시간 차가 너무 커서 놀랐다. 0ms 와 232ms ! 처음 작성한 코드는 아무런 기교가 사용되지 않는다. 채워야할 남은 카드의 수를 r 이라 했을 때, 이 r 장의 카드를 구성하기 위해 1 번 팩, 2번 팩, ... , n 번 팩을 사용하고 다시 남은 카드에..

문제 링크 : https://www.acmicpc.net/problem/14165 14165번: Team Building Every year, Farmer John brings his N cows to compete for "best in show" at the state fair. His arch-rival, Farmer Paul, brings his M cows to compete as well (1≤N≤1000,1≤M≤1000). Each of the N+M cows at the event receive an individual integer score. www.acmicpc.net 문제를 이해하는데 어려움을 겪었다. 설명에 등장하는 다음 문장 That is, each distinct pair (s..