본문 바로가기

백준34

BOJ 11049 - 행렬 곱셈 순서 (dp) https://www.acmicpc.net/problem/11049 파일 합치기와 매우 유사함 최대 500개의 행렬 정보가 n*m 형태로 입력될 때, 이들은 순서대로 곱할 수 있음이 보장된다. 모든 행렬을 곱할 때 곱셈 연산의 최소횟수를 구하는 문제. f(i, j) : i~j번째 행렬을 곱할 때 곱셈 연산의 최소 횟수 f(i, j) = f(i,k) + f(k+1,j) + a[i].f * a[k+1].f * a[j].s ( i > a[i].first >> a[i].second; memset(dp, -1, sizeof(dp)); cout 2019. 12. 29.
그리디 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다. 탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성 최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지 ->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재 알고리즘이 위 두 속성을 만족하는지 검증해야 한다. 1. 활동.. 2019. 12. 18.
BOJ 2450 - 모양 정돈 (KOI 중등 , 구현) https://www.acmicpc.net/problem/2450 최소한으로 이동하는 방법을 생각해 내지 못했다.. 정렬이 이뤄지면 결과적으로 6개의 가능한 모양이 있다. (1,2,3의 순열) 이 때 최소한으로 움직이는 방법을 살펴보면 1. 그룹(1)에 있는 그룹(2)(3)에 속해야 하는 요소들의 개수 (그룹(2),(3)에 속한 그룹(1)요소의 개수와 같다) (ex 입력이 1223111, (1,2,3)순서라면 2+1) 2. 그룹(2)에 있는 그룹(3)요소의 개수, 그룹(3)에 있는 그룹(2) 요소의 개수; 둘 중 큰 것 1,2를 더해주면 최소한으로 움직이는 횟수가 된다. 복잡해보이지만, 그룹1먼저 채워주고 그룹2,3을 생각해주는 것이다. 생각하는 과정에서 스쳐가듯 생각한 방법이긴 하지만, 이 방법이 유효.. 2019. 10. 17.
BOJ 10835 - 카드게임 ( 2015 KOI 초등, dp ) https://www.acmicpc.net/problem/10835 왼쪽 더미 i번째, 오른쪽 더미 j번째를 보고 있을 때 다음으로 선택할 수 있는 경우의 수가 최대 3가지 이다. bfs로 풀어야되나? 싶었는데 i,j 외에 여태 얻은 값을 세번째 상태로 계속 넘겨줘야 해서 visited공간이 부족하고, map으로 구현하기도 비효율적이다. dp로 풀기로 해서 점화식을 짜 봤는데 깔끔하게 짜 졌다. 이후 코드로 옮기기만 했다. #include #include using namespace std; int n, a[2000], b[2000], dp[2000][2000]; int f(int i, int j) { if (i == n || j == n) return 0; int& ret = dp[i][j]; if (.. 2019. 10. 14.

티스토리툴바