알고리즘 별 문제 정리/DP (16) 썸네일형 리스트형 [C++] 백준 2011: 암호코드 https://www.acmicpc.net/problem/2011 문제 풀이DP로 푼 문제이다. 출력에서 원하는 값을 dp배열의 값으로 설정하여,dp[i] = i번째 숫자까지 읽을 수 있는 해석의 가짓수로 진행했다. 예제를 통해서 문제를 풀어보자.쉽게 123으로 예시를 들겠다. 1. dp[1]의 값은 무엇일까?당연히 하나의 숫자만 존재하므로 해석의 가짓수도 A로 하나만 존재한다.즉, dp[1] = 1이다. 2. 그럼 dp[2]는?1과 2를 따로 구분하여 인식하거나, 12를 하나의 숫자로 인식하는 두 가지 경우가 존재한다. 먼저 첫 번째 경우이다.사실 각각의 숫자를 개별로 인식한다면 가짓수는 늘어나지 않는다.즉 dp[i] = dp[i-1]이라는 뜻이다.이때 숫자가 하나 있을 경우 즉, dp[0]의 .. [C++] 백준 1915: 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 문제 이해n * m의 0과 1로 구성된 배열이 있을 때1로만 이루어진 정사각형 중 가장 큰 것의 넓이를 구하는 문제입니다. n, m : 1 ~ 10^3 완전 탐색으론 시간 초과가 났기에, DP를 사용해야겠다는 생각을 했는데 도저히 점화식을 못 찾았습니다. 도저히 감이 안 잡혀서 다음 포스트를 참고하고 풀었습니다. https://yabmoons.tistory.com/158 [ 백준 1915 ] 가장 큰 정사각형 (C++)백준의 가장 큰 정사각형(1915) 문제이다.[ 문제 바로가기 ] [ 문제풀이 ]1) 주어진 맵에서, 가장 큰 정사각형의 넓이를 출력하는 문제이다. Dynamic Programming으로 어떻게 구현해야 하는지 알아보자.. [C++] 백준 10492: 팰린드롬? https://www.acmicpc.net/problem/10942 문제 요약수열이 주어졌을 때, S ~ E까지의 수열이 팰린드롬인지 확인하는 문제.수열의 원소의 개수는 최대 2,000(10^3)개질문의 횟수는 최대 1,000,000(10^6)개 ※팰린드롬: 앞에서 읽어도 뒤에서 읽어도 같은 값을 나타내는 문자열. 풀이1. 처음 생각했던건 단순 브루트포스였다. 하지만 시간 제한이 0.5초였고,질문의 개수만 해도 10^6이라서 각 질문마다 팰린드롬인지 계산한다면무조건 시간초과가 나올 수 밖에 없었다. 2. 다음으로 생각한 건 DP이다.dp배열의 차원과 값을 설정하는 게 좀 시간이 걸렸다.2차원으로 dp배열을 만들경우 모든 원소를 써야 되는 게 아닌가? 라는 고정관념에 빠져 더 힘들었던 거 같다. 결국.. [C++] 백준 9252: LCS 2 https://www.acmicpc.net/problem/9252 LCS 1에서 발전한 문제이다!https://dmoritle.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251-LCS [C++] 백준 9251: LCShttps://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다! 자, DP이므로 배열의 의미를 잘 지정하dmoritle.tistory.com안 풀어본 분들께서는 위의 포스팅을 참고해주시면 좋을 것 같다! 풀이LCS 1과의 차이점은 LCS인 문자열을 출력해줘야 한다는 것이다.dp배열을 다 구해둔 상태이니 역추적을 하면 될 것 같다. f.. [C++] 백준 14002: 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열을 선행했다면 굉장히 쉽게 풀 수 있는 문제였습니다. 풀이int n; cin>>n; for(int i = 1; i >num[i]; dp[i] = 1; } for(int i = 2; i num[j]) dp[i]++; } }먼저 위와 같이dp[i] = i번째 숫자가 끝일 때, 가장 긴 증가하는 부분 수열의 길이로 설정하고,그 값을 구해줍니다. 한 개의 원소로 구성된 수열은 값이 1이기에 초깃값으로 설정해주고,원소의 범위를 늘려가며 가장 긴 증가하는 부분 수열의 길이를 구해줍니다. 조건문의 조건에 대해 살펴보겠습니다.먼저, 증가하는 부분 수열이기에 num[i.. [C++] 백준 2096: 내려가기 https://www.acmicpc.net/problem/2096 왼쪽으로 내려갈 때,가운데로 내려갈 때,오른쪽으로 내려갈 때 3가지의 경우의 수에 대하여 각각의 점화식을 세우면 쉽게 풀 수 있다고 생각되는 문제였습니다. 풀이dp[i][j][k] = i번째 행의 j번째 자리일 때 얻을 수 있는 최댓값 or 최솟값(k로 구분, 0은 최댓값 1은 최솟값) 왼쪽으로 내려갈 수 있는 건,이전 단계에서 왼쪽에 있을 때와 가운데에 있을 때입니다.dp[i][0][k] = dp[i-1][0][k] + dp[i-1][1][k] 가운데로 내려갈 수 있는 건,이전 단계에서 왼쪽, 가운데, 오른쪽입니다.dp[i][1][k] = dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][2][k] 오른쪽으로 내려.. [C++] 백준 17070: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 dp배열의 값 설정문제에서 (N,N)로 이동시키는 방법의 개수를 물어봤으므로, dp[i][j] = (i, j)까지 이동시키는 방법의 개수라고 가정하고 시작했다. 이 문제는 좌표뿐만 아니라 방향값도 존재하므로 배열의 차원을 하나 늘려방향값도 저장하는 게 좋겠다는 생각이 들었다. 그래서 dp[i][j][k] = k의 방향을 가지는 (i,j)까지 이동시키는 방법의 개수로 가정했다. 처음에 파이프는 가로 방향으로 (1,2)에 끝이 위치하므로 dp[1][2][0] = 1; 다음과 같이 초기값을 설정했고,그 후에 점화식을 생각해보았다. 점화식 구하기dp[n][n][0] = 가로 방향으로 (n,n)까지 이동시키는 방법의 개수이다. 즉, .. [C++] 백준 2565: 전깃줄 https://www.acmicpc.net/problem/2565 풀이입력을 받을 때 두 개의 전깃줄을 동시에 받으므로 vector 자료형의 pair를 통해 받은 뒤,정렬을 해주면 될 것 같았다. 정렬을 하고 ,dp[i] = i번째 전깃줄이 교차하지 않고 연결되어 있기위한 없애야 하는 전깃줄의 최소 개수로 가정하고 풀이를 떠올려봤는데 도저히 감이 안 잡혔다. 인터넷 검색을 통해 풀이를 슬쩍 봤는데,가장 긴 증가하는 부분수열을 활용하는 문제라고 나와있었다.그걸 보자마자 무릎을 탁 쳤다!!https://www.acmicpc.net/problem/11053 dp[i] = i번째까지 중 가장 긴 증가하는 부분수열의 길이로 하면이미 좌측 배열의 값은 정렬이 되어있는 상태이기에, dp[i] = i번째까지의 전.. 이전 1 2 다음
