"(백준/ C++) 11049 - 행렬 곱셈 순서 / 다이나믹 프로그래밍" 해도해도 어려운 DP .. 혼자 못 풀었다. 유투브 설명 보고 풀었다 .. ㅠㅠ 핵심은 AEH 사이의 (ABCDE) (FGH)가 어떠한 방법으로 연산을 했든지 간에 (ABCDE) 의 최종행렬의 크기는 { a , f } (FGH)의 최종행렬 크기는 { f , i }가 된다. 라는 사실이다.  점화식:  a x f x i + Func(x , k) + Func (k+1, y)    //== [ 행렬 곱셈 순서 ] ==#include #include #include using namespace std;int col[500], row[500];int dp[500][500];int func(int idx_x, int idx_y){ if (d..

" (백준/ C++) 7579 - 앱 "  https://www.acmicpc.net/problem/7579 7579 - 앱입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다.www.acmicpc.net 다이나믹 프로그래밍으로 풀어야 하는 문제. 처음에는 무게로 DP를 만들면 되겠다 ~ 했지만 ?? 무게(M)이 최대 10,000,000 이였다. DP[ n ][ m ] 이건 ..

" (백준/ C++) 1106 - 호텔 " https://www.acmicpc.net/problem/1106 1106 - 호텔첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.www.acmicpc.net 이 문제는 냅색과 비슷하다.다른 점이 있다면 중복으로 넣을 수 있는 점? 냅색 문제는 물건 하나 씩 넣는다. 가장 간단해보이는 예제 입력1번을 보고 DFS를 이용하여 풀 수 있는 방법을 고민해봤다.  " C명(12명)을 확보하면서 최소의 비용이 들어..

"(백준/ C++) 2629 - 양팔저울"https://www.acmicpc.net/problem/2629 아마 .. 양팔저울 문제 설명에 냅색 알고리즘으로 푸는 문제라고 적혀 있지 않으면 오랫동안 못 풀었을거 같다.. ^^;;  냅색과 같이 나올수 있는 무게의 경우를 만드는 방식으로 풀이를 했다. 점화식은 (가)저울에만 추를 둘수 있다고 생각 하고 경우의 수를 고려하였다. (가)에 A추가 있는 경우 → (가) A추 + 구슬 = (나) B추 → (가) 구슬 = (나) B추  -  A추 (나)에 A추가 있는 경우 → (가) 구슬 = (나) B추 + A추(가), (나)에 A추가 모두 없는 경우 → (가) 구슬 = (나) B추 처음에는 이분탐색으로 찾으려 했으나 메모리 문제로 실패 ! DP[비교대상개수][무게..

11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 희소 테이블에 대해 모른다면 풀기 어려운 문제 일거 같습니다. 풀기전에 희소 테이블로 워밍업을 하고 천천히 풀어보자. 아래 주소는 희소 테이블에 관한 문제입니다. [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 (tistory.com) [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 Sparse Table (스파스 테이블) 특징 방..

12738오늘은 가장 긴 증가하는 부분 수열 1, 2, 3, 4, 5를 모두 풀어볼겁니다. 이 문제들을 다 풀었다면 자연스럽게 11055번 가장 큰 증가 부분 수열과 11054번 가장 긴 바이토닉 부분 수열은 쉽게 풀수 있을겁니다. 저는 단계별로 풀어보기에서 이분 탐색을 풀면서 연관된 문제 그냥 다 풀어보자 하는 마음으로 풀어보았고, 많은 블로그도 보고 질문 게시판의 도움도 받으면서 풀었습니다. 자 이제 그럼 풀어봅시다.  ❗문제❗수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.11053..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색은 생각하기 너무 어려운 문제인거 같습니다. 냅색이라는 이름만 보고 DP로 접근하려고 했는데 생각이 멈춰버렸습니다.... 언제 문제를 읽자마자 무슨 알고리즘을 써야하는지 떠오를까 ..ㅜㅜ 이 문제는 https://allmymight.tistory.com/99 [백준]1450번 냅색문제 - C++ https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 두 수의 합이 0과 가장 가까운 것(음수도 있을 수 있음)을 찾아야 한다. ▶▷ 두 수의 합을 구하고 절댓값으로 비교한다. 2. 주어진 수는 정렬 돼서 주어지지 않는다. ▶▷ 정렬을 후, 투 포인터의 조건을 만들어준다. ※ ex) "백준 1644 - 소수의 연속함" 투 포인터 인덱스 움직임의 조건: sum이 N보다 작으면 t..

1644번: 소수의 연속합 (acmicpc.net) 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 키워드 1. 연속된 소수의 합으로 나타낼 수 있는 자연수 2. 자기 자신이 소수 일 때도 카운트 해결 방법 1. 에라토스테네스의 체 알고리즘을 통해 N이하(N포함)의 소수를 찾아 Vector에 넣는다. 2. vector의 size가 0이 아닐 경우 두개의 index(oneIdx, twoIdx)는 vector의 맨 앞 인덱스 0을 가진다. 3 sum이 N보다 작으면 twoIdx를 클 경우 oneIdx를 증가시킨다. ※ sum은 one과 two 사이의 vector의 합 ▼TwoIdx ▲ OneIdx 코드 #include #inc..

4673번: 셀프 넘버 (acmicpc.net) 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net