JJ_blog

배낭 관련된 문제들을 풀때 2차원 배열에 어떤 값을 넣어야 풀 수 있는지 아직 감이 잡히지 않는 것 같다. 배낭 유형 문제들을 풀면서 감을 익혀야 할 것 같다. 문제 - 1 페이지 www.acmicpc.net 이번 문제도 삽질을 좀 많이 했다.. 2차원 배열에서 행: 입력 횟수, 열: 비용으로 생각하고 풀면 되지만 열에 해당하는 최댓값은 입력받은 모든 비용의 합으로 해야한다. #include #define BYTE 1 #define COST 0 using namespace std; void app7579(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N,M; cin>>N>>M; vector App(N+1); int dp[N+1][1..

배낭 알고리즘은 DP의 대표적인 문제라고 한다. (사실 처음 봄.. ㅎ) 문제를 풀고 보니 앞선 문제에서 사용했던 LCS 푸는 방법과 유사했다. 예시를 통해서 알아보자 (백준 예제를 살짝 변형한 예제이다) 다음과 같이 입력을 받았다고 하자 index는 arr 배열에서의 index를 의미한다 여기서 weight = 0, value = 1이다. ex) arr [1][weight] = 6, arr [1][value] = 13 LCS 알고리즘에서 DP table에 값을 저장할 때 해당 값의 유무가 아닌 이전 값을 고려하여 정보를 저장했다. (먼저 혼자서 끄적여 본 표..) 위 표에서 자세하게 봐야할 부분은 (n=3, k=7)인 부분이다. arr에서 (n>n>>k; int arr[n+1][2]; int dp[n+..

LCS 2와 다르게 이번에는 3개의 문자열을 받아서 처리하는 문제이다. LCS 2에서 두개의 문자열을 비교할 때 반복문 2번을 돌렸다면 이번에는 3번을 돌리면 된다. □ 소스 코드 void LCS1958(){ ios::sync_with_stdio(false); cin.tie(NULL); string arr1, arr2, arr3; cin >> arr1 >> arr2 >> arr3; int LCS[101][101][101] = {0}; for(int i=0;i

2중 반복문을 돌려서 해당 문자열까지 겹치는 횟수를 2차원 배열에 기록하는 방법으로 문제를 해결했다. 여기서 중요한 것은 2차원 배열에 기록을 할 때 문자 하나하나를 비교해서 기록하는 것이 아닌 문자열과 비교해서 기록해야 한다는 것이다. 예를 들어 왼쪽 문자열(ACAYKP)에서 부분 문자열 A와 위쪽 문자열(CAPCAK)에서 부분문자열 C와 비교한다면 A와 C는 겹치는 부분이 없으므로 0이 된다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 AC와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보면 AC와 C는 겹치는 문자가 C 하나가 있다. 따라서 해당 부분에 1을 기록한다. 그다음 왼쪽 문자열(ACAYKP)에서 부분 문자열 ACA와 위쪽 문자열(CAPCAK)에서 부분문자열 C를 비교해 보..

전깃줄 문제를 처음 접했을 때 앞에 가장 긴 시리즈 문제들을 해결을 한 상태라서 되게 쉽게 느껴졌다. 그림을 본 순간 든 생각은 A와 연결된 B애들을 순서대로 적어보자! 였다. 적자마자 수열이 떠올랐다. ㅋㅋ 해당 수열을 가지고 가장 긴 증가하는 수열을 찾고 전체 길이에서 빼주면 답이 나온다. ㅎㅎ 가장 긴 시리즈에서 유용하게 사용했던 Dp + 이진탐색을 활용해서 문제를 해결했다. 전깃줄 2 길이를 구하는 건 쉬운데 또 부분 수열의 요소들을 찾으랜다. 이것 역시 가장 긴 수열 시리즈에서 했던 역추적 방법을 사용하면 풀 수 있다. 역추적을 하고 나면 위에서 작성했던 가장 긴 부분 수열은 {1, 4, 6, 7, 10}이 나오게 된다. 그러면 {8, 2, 9, 1, 4, 6, 7, 10}에서 가장 긴 부분 수..

이 문제는 어렵다기보다 아이디어 차이인 것 같다. 문제를 해결한 방법으로 DP를 사용하였다. 일반적인 Dp방법으로 1. (앞 → 뒤) 방향으로 dpI를 담는다. 2. (뒤 → 앞) 방향으로 dpD를 담는다. 그 이후 두 dp들을 더한다. 더한 후 가장 값이 큰 요소를 찾은 다음 1을 뺀다. 소름 돋게 간단하다. □ 소스 코드 void bye11054(){ int n; scanf("%d",&n); vector array; vector dpI(n); vector dpD(n); for(int i=0;i

수열 문제를 풀다 보니 4,5번까지 오게 됐다! 14002, 14003은 앞선 문제들(12015, 12738)과 다르게 부분 수열의 최대 길이뿐만 아니라 부분 수열도 출력을 해야 한다. 물론 Dp 방식으로 문제를 풀면 14002는 해결할 수 있지만 14003은 범위 때문에 시간초과로 해결하지 못한다. 이번 문제에서도 아래 문제에서 풀 듯이 이진탐색을 섞어서 풀었다. [백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000..

11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000,000,000 ~ 1,000,000,000 [백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf( hj39-develop.tistory.com 11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다..

이번 문제는 11053과 다르게 가장 긴 수열의 길이를 찾는 게 아닌 증가하는 수열들 중에서 가장 큰 합을 가지는 부분 수열을 찾는 문제이다. 11053에서 찾은 새로운 방법(이진 탐색)으로 합을 찾아보려고 했지만.. 할 수 없는 건지 실력이 부족한 건지 풀 수가 없었다. ㅠㅠ 더 공부한 후에 다시 도전해 봐야지 그래서 결국 DP를 이용하여 문제를 해결했다. 11053에서 DP를 이용한 방법과 아주 유사하다. 앞선 문제에서는 dp 배열에 길이를 저장했다면 이번 문제에서는 dp 배열에 원소의 합을 저장해 주면 된다. □ 소스코드 void best11055(){ int n; scanf("%d",&n); int array[1001] = {0}; int dp[1001] = {0}; for(int i=1;i

DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf("%d",&n); int dp[1001] = {0}; int array[1001] = {0}; for(int i=1;i