quant developer dave

트리의 지름은 임의의 한 노드에서 다른 노드까지 거리를 구한 후 가징 멀리있는 노드에서 다시 모든 노드까지 거리를 구한후 가장 멀리 떨어져 있는 노드와의 거리가 지름이 된다. 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

오늘은 전체적으로 쉬운 문제가 많이 있었다. C번 히든넘버 .... ㅋㅋㅋㅋㅋㅋㅋㅋ 꼭 한번 풀어보시길 ㅋㅋㅋㅋㅋㅋ

오늘도 요렇게 랜덤 함수 돌려서 대회 만듬 오늘은 문제가 극악이였다. A번 컨벤션 센터는 약간 꼬은 그리디 문제. 적절한 난이도인데 마지막에 풀어서 시간이 모자랐고B번 Dream Counting 문제는 그냥 쉬운 구현문제D번 신나는 분수 계산은 귀찮은 구현문제 (쉬운데 코드량이 많음) D번에 시간을 다 쏟아 부어서 아쉽다. 문자열 처리하는데 웹 컴파일러에서 정규식이 작동을 잘 안해서 직접 다 손으로 구현했다. 이런 문제는 파이썬을 쓰면 손쉽게 해결 가능할듯 ..

틈날때 마다 dfs 문제를 풀어나가고 있다. 이 문제도 그냥 dfs 하면서 가장 멀리 갈 수 있는 경로의 길이를 출력하는 문제다 ..boj에 dfs로 태그되어 있는 문제를 푸는데 앞에서 부터 풀다보니 계속 난이도가 쉬운 문제 위주로 풀게 되는 것 같다. #include #include using namespace std; char map[21][21];int color[26] = { 0 };int Y, X; int dfs(int y, int x){//최대 이동할 수 있는 칸 return;int ret = 0;char cur = map[y][x];color[cur - 'A'] = 1;for (int i = -1; i = X) continue;char next = map[nextY][nextX];if (co..

#include #include using namespace std; int main() {int arr[100001] = { 0 }, a, b;for (int i = 2; i 0) continue; for (int j = i + i; j > a >> b;int count = 0;for (int i = a; i