본문 바로가기

알고리즘/백준

 (109)
[BOJ 1256] 사전 이 문제는, 조합에 대한 고등학교 공식을 알아야 풀 수 있다. C(N, M) = C(N - 1, M - 1) + C(N - 1, M) 이 식으로, K의 범위를 체크할 수 있다. 하지만, 단어를 찾기 위해서는 하나 더 생각할 필요가 있다. 1) a _ _ _ _ 2) z _ _ _ _ 위와 같은 형태가 있을 때, K와 대소관계에 따라서 1), 2) 중 하나가 선택된다. 만약 N이 2, M이 3이라고 하면, 1)이 되려면 K > N >> M >>K; C[0][0] = 1; for(int i = 1; i
[BOJ 1509] 팰린드롬 분할 팰린드롬 분할의 개수의 최솟값을 찾아야 한다. 기존에 구해놓은 팰린드롬 분할의 개수의 최솟값을 이용해서 전체 팰린드롬 분할의 개수의 최솟값 찾아야 한다. 전체 펠린드롬의 분할의 개수의 최솟값을 찾기 위해서, 분할할 수 있는 모든 경우의 수를 확인해야 한다. 해설코드(C++). 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 39 40 41 42 43 #include using namespace std; string s; bool dp[2500][2500]; int count[2500]; int main() { cin >> s; for(int i = 0; i
[BOJ 7579] 앱 이 문제는 메모리 초과로 인해서 매개변수를 수정해서 DP를 선언해야 한다. 최소 비용을 찾기 위해서 DP를 인덱스 하나와 바이트를 이용하면, 메모리 초과가 발생한다. 따라서, 인덱스 하나와 비용을 이용해서 최대의 바이트를 가지도록 관계식을 세워야 한다. DP[i][j]일 때, i = 비활성화할 메모리 인덱스의 시작 j = 쓸 수 있는 비용 해설코드(C++). 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 39 40 41 42 43 #include #include using namespace std; int N, M; int c[101]; int m[101]; lon..
[BOJ 2240] 자두나무 이 문제는, 위의 형태로 재귀적으로 호출할 수 있다. 메모이제이션을 통해서, 같은 반복문을 돌지 않도록 코드를 구성하면 된다. 주의할 점은, 문제의 조건에서 1번 나무에서 무조건 시작된다고 했으므로, 2번 나무로 시작할려면 W를 1 감소시키고 시작해야 한다. 해설코드(C++). 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 39 40 41 42 43 44 45 46 47 48 49 50 #include #include #include using namespace std; int T, W; int arr[1001] = { 0 }; int dp[1001][31][3];..
[BOJ 2352] 반도체 설계(이분탐색) 이 문제는 증가하는 수열의 최장길이를 구하는 문제와 동일하다. 1 2 3 4 5 6 4 2 6 1 3 5 n번 포트끼리 겹치지 않는 방식을 살펴보면, 최장길이를 구하는 방식과 동일함을 알 수 있다. 주의할점은, N * N 시간복잡도가 아닌 이분 탐색(N * log N)을 이용해야 한다. 이분 탐색에 대한 이해를 돕기 위한 개념들을 좀 적어보자면, 이분 탐색을 위해 새로 선언된 벡터는 항상 정렬된 상태를 유지하게 된다. 왜냐하면, lower_bound도 함수의 정렬을 방해하지 않는다. lower_bound의 역할은 최장길이를 찾을 수 있도록 기존의 벡터의 원소들을 변경시킨다. 벡터의 원소들을 변경시켜도, 현재 최장길이엔 변함이 없다. 다만, 미래에 최장길이를 찾을 수 있는 가능성을 만들어준다. 해설코드(C..
[BOJ 2169] 로봇 조종하기 다이나믹 프로그래밍 분류 문제이다. 만약 dp를 2차원 배열로 정의하면 문제가 해결되지 않는다. dp[i][j]의 값이 만들어질 때, 직전 출발지가 왼쪽에서 왔는지, 오른쪽에서 왔는지, 위쪽에서 왔는지에 따라 값이 달라져야 하기 때문에 3차원 배열이 필요하다. 해설코드(C++). 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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #define MIN -987654321 using namespace std; int N, M; int arr[1001][1001]; bool ch..
[BOJ 5582] 공통 부분 문자열 간단한 문제인데 벙쪄있었다. 왜 그랬을까? 아마도 dp를 공통 부분 문자열의 최장 길이로 정의할려다가 보니 점화식을 못세워서 뇌정지가 왔던 거 같다.. 이 문제를 풀기 위해서는, 점화식을 세워야 한다. S1과 S2의 각 각 인덱스를 i와 j라고 하자. dp는 S1[i]와 S2[j]가 공통 부분 문자열의 마지막 부분일 때, 공통 부분 문자열의 길이의 값이다. dp[i][j] = dp[i - 1][j - 1] + 1 (S1[i] == S2[j]) dp[i][j] = 0 (S1[i] != S2[j]) 위의 점화식을 통해서 코드를 작성하면 된다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include u..
[BOJ 1038] 감소하는 수(다이나믹 프로그래밍, 수학 풀이) https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. www.acmicpc.net 다이나믹 프로그래밍은 For문을 이용하거나, 재귀적으로 함수를 구성하는 것이 아니다. 문제를 나누어서 해결하는 것이다! 이 문제가 그러한 특징을 정확히 담고 있다. 새로운 감소하는 수를 찾으려면, 기존에 감수하는 수를 이용할 수 있다. 기존..

티스토리툴바