quant developer dave

dp(i,j) : (i,j)에서 시작해서 끝(m-1, n-1)까지 가는 경로의 합dp(i,j) = 인접칸 y,x(네 방향)의 dp(y,x)들의 합 (arr[i][j] > arr[y][x] 인 경우에만) #include #include using namespace std; int m,n,arr[501][501],cache[501][501];int func(int y, int x){if(y==m-1 && x == n-1) return 1;if(y>m-1 || x>n-1 || y arr[y-1][x]) count+=func(y-1,x);if(y arr[y+1][x]) count+=func(y+1,x);if(x>0 && std > arr[y][x-1]) count+=func(y,x-1);if(x arr[y][x..

http://www.tmath.or.kr/kin/qna/detail.asp?qnaNum=297

주어진 수열에서 최장 등차수열을 찾는 문제이다. 최근에 푼 문제 중에서 제법 어려운 편인것 같다.일단 d[i][j]를 수열에서 i번째수와 j번째수로 시작하는 등차수열의 최대 길이로 잡았다. 이 발상을 하는데 혼자 고민을 한시간 넘게했다.그 후에 동적 계획법 함수 dp 안에서 first, second로 third를 찾는데 순차 탐색을 하니 전체 시간복잡도가 O(n^3)이 되어서 시간이 모자랐다. 시간 문제를 해결 하기위해 순차 탐색 대신에 이진탐색을 수행하였는데 여기서도 예외가 발생했다. 같은 수가 여러개 있는 상황을 고려하지 못했다. third가 될 수 있는 수가 여러개가 있다면 가장 왼쪽의 수를 선택해야한다. 이는 stl::low_bound 함수로 구현했다. d[first][second] : first..

한국정보올림피아드 지역본선 2009 초등부 5번 문제 숫자 맞추기 포스팅은 뜸하지만 꾸준히 하루에 여섯문제 일곱문제 이상은 풀어가고 있다. 간만에 재밌는 dp 문제를 풀어서 포스팅 한다. 처음 문제를 보고 든 생각은 bfs로 최단거리를 구하려했다. 하지만 자리 수 제한이 10000... 만 자리나 되는 숫자로 bfs 하기는 힘들어 보였고 점화식을 찾아 동적 계획법으로 풀었다. - 함수 int dp(int state, int add) - state번째 자리에서 시작하는 숫자에 add번 왼쪽으로 돌린 상태에서의 최소 회전 수 반환 - 구해야 하는 값 dp(0,0) - 점화식 1. 오른쪽으로 돌릴 때 : 오른쪽 회전은 밑에 다른 숫자에 영향을 주지 않고 자기 자신만 돌아간다. 따라서 점화식은 dp(state ..

트리의 지름은 임의의 한 노드에서 다른 노드까지 거리를 구한 후 가징 멀리있는 노드에서 다시 모든 노드까지 거리를 구한후 가장 멀리 떨어져 있는 노드와의 거리가 지름이 된다. http://blog.myungwoo.kr/112 여기에 증명이 잘 되어있다. 양방향 가중치 그래프로 만들고 dfs를 하면서 가장 멀리 떨어진 노드와 그 노드까지 거리를 구한다.부모가 아닌지만 검사해 dfs 함수를 재귀적으로 호출하는 이유는 트리라서 싸이클이 없으니까 ! 소스코드 : #include #include #include using namespace std; vector adj[100001]; int res,idx; void dfs(int now,int parent, int len){if(len>res)res=len,idx..

간만에 포스팅. 바빠서 문제 풀이를 많이 하지는 못했고 또 푼 문제 중에서도 그닥 포스팅 하고 싶은 문제가 없었다.이 문제는 간단한 dp 문제지만 중간에 삽질로 오래 걸려서 포스팅한다. 점화식은 다음과 같다. 어떤 X가 KOI 유전자라면, aXt와 gXc도 KOI 유전자이다. d[l][r] = d[l+1][r-1] + 2 l, r 문자가 at 혹은 gc 일때 : d[l][r] = max(d[l][r] , d[l+1][r-1] + 2) 어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다. for(int i=l+1; i=r){ans = 0;}else if(r-l == 1) {if( isKOI(t[l],t[r])) ans = 2;else ans = 0;}else{int res=0; d..

오늘은 전북대학교 교내 알고리즘 대회 기출 문제로 만들었다. 딱 내 수준에 맞는듯 ㅋㅋA번 수면 장애 : ... 이ㅓㄱㄹ.. 이걸 못풀다니 !B번 고급 레스토랑 : 문제 이름이 왜 고급 레스토랑인지 도저히 모르겠다. 간단한게 시뮬레이션으로 풀면 된다.E번 틱!택!토 : 틱택토 게임 시뮬레이션 F번 : 최후이 승자는 누구? : 카드 게임 시뮬레이션G번 : 돌다리 BFS 알고리즘을 사용해 최단거리 계산

https://www.acmicpc.net/problem/13902 일반적인 동전 교환 dp 문제랑 많이 다르지 않다. 화폐 단위 대신 웍의 크기를 사용하는데, 특이한 점은 동시에 두개를 들고 요리가 가능하단다...그래서 서로 다른 웍의 크기를 더해 새로운 웍의 크기를 만들어주고 동적 계획법 하면 된다. #include #include #include #include #include using namespace std; int n,m,cache[10001]={0},t;vector size;int main() {cin>>n>>m;for(int i=0; i>t; size.push_back(t);}for(int i=0; i

학교 건물에서 어기적 어기적 거리다 심심해 보이는 홍 모씨와 알고리즘 연습을 했다. 예전에 같이 acm icpc 대회도 나갔었는데 그때 성적은 별로 좋지 못했다 .... ㅎ 간만에 같이 알고리즘 문제푸니 그 때 생각이 나서 좋았다.홍 모씨는 오랜만에 하는 문제풀이라 힘을 못쓰는듯 했다. 이럴줄 알았으면 치킨이라도 걸었어야하는데 ..

평소대로 메모리 신경안쓰고 재귀로 해결하니 (보통 100메쯤 주니까 ... 이 문제는 확인해보니 4메가) 메모리 초과로 오답을 받았다. 이차원배열이던 dp 배열을 1차원으로 바꾸고 2차원 반복문으로 해결했다. 점화식이 간단하니 점화식 설명은 생략 #include #include #include using namespace std; int main(){int cache[10001] = { 1,0 };vector cur;int c, m, t;cin >> c >> m;while (c--) {cin >> t;cur.push_back(t);} sort(cur.begin(), cur.end());for (int i = 0; i < cur.size(); i++) {for (int j = cur[i]; j