본문 바로가기

알고리즘

 (179)
[BOJ 1328] 고층 빌딩 N개의 빌딩이 있고 L = A, R = B일 때, N - 1개을 이용해서 어떻게 어떻게 만들 수 있을까? N - 1개의 빌딩들의 범위는 1 ~ N - 1이다. 각 높이에 1을 더해주고, 높이가 1짜리인 빌딩을 놓으면 N개의 빌딩을 만들 수 있다. 높이가 N인 빌딩을 이용했다면, 점화식을 세울 수 있을지 없을지도 모른다. 하지만, 높이가 1짜리인 빌딩을 이용하므로 점화식이 간편해진다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int N, L, R; long long dp[101][101][101]; int main() { cin >> N >> L >> R; dp[1][1][..
[BOJ 2618] 경찰차 처음엔 DP를 정의하기 위해서, 5차원 배열(경찰차 1, 2의 위치 + 현재 해결중인 사건)을 생각했었는데, 1000^5는 메모리제한을 초과하게 된다. 5차원 배열의 크기를 줄이는 것을 생각해보면, 경찰차 1, 2이 해결한 마지막 사건들을 이용하면 된다. 왜냐하면, 같은 사건은 중복된 장소에서 발생하지 않으므로, 마지막 사건들은 즉, 현재 해결중인 사건을 표현하고 경찰차의 위치도 나타낼 수 있다. 전체 탐색을 통해서 DP 배열을 완성하고, 한 단계씩 최소값을 찾아가면서 값을 출력하면 된다. 해설코드(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..
[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..

티스토리툴바