본문 바로가기

thoughts

Paths, Trees, and Flowers presentation Matching in graphs is a subset of edges with no shared endpoints. and a maximum matching is a matching of maximum size among all matchings in a given graph. Edmonds represented the first such algorithm in his famous paper "Paths, Trees, and Flowers" in 1965. 더보기
Euclidean Algorithm 컴퓨터 사이언스나 컴퓨터 공학을 전공하는 학생이라면 누구나 Euclidean Algorithm을 한 번 쯤을 들어봤을 것이다. Euclidean Algorithm은 가장 오래된 알고리즘 중 하나로 2300년전 그리스의 수학자 Euclid에 의해 고안되었다. Euclidean Algorithm은 음이 아닌 두 정수 a, b의 최대공약수 GCD(a, b)를 구하는 알고리즘으로 C++로는 아래와 같이 간단하게 구현할 수 있다. int GCD(int a, int b){if (b==0) return a;return GCD(b, a%b);} 코드가 워낙 간단하기 때문에 여태껏 그냥 외워서 쓰고 있었는데 사실 그 본질에 대해서는 제대로 이해하고 있지는 않았다. 오늘 우연히 루프 불변식에 대한 복습을 하다가 그 증명을.. 더보기
주제 1. 동종/이종간 거짓말이 생존에 미치는 영향 2. 배반 가능성(?)과 호혜의 관계 더보기
GA 프로젝트를 진행하면서... 이번학기 GA수업에서 초롱이님게서 야심차게 준비했던 프로젝트! 바로 로버트 엑셀로드가 시행했던 반복적 죄수의 딜레마의 확장판! 로버트 엑셀로드가 시행했던 죄수의 딜레마가 2x2 매트릭스였다면 이번 GA프로젝트는 nxn크기의 매트릭스에서 반복적 게임을 통해 많은 득점을 가지는 전략을 얻는 것이다. 물론 이 매트릭스에 죄수의 딜레마는 존재하지는 않는다. 여기에서 엑셀로드의 흥미로운 실험을 생각해보자.. 두 죄수가 붙잡혀 들어왔다. 이 죄수를 심문하던 형사는(혹은 검사일러나? 이거슨 중요한 문제가 아니다!) 두 죄수가 모두 죄를 자백하도록 만드는 기막힌 방법을 고안해 낸다. 형사는 서로 격리되어 있는 두 죄수에게 말한다. "당신과 당신의 동료가 모두 자백을 하지 않는다면 둘다 1년동안 징역을 살것이다. 하지만.. 더보기
Time Check use gettimeofday double gettime() { timeval t; gettimeofday(&t,0); return (double)(t.tv_sec)+(double)(t.tv_usec)/1000000.0; } use asm(CPU가 2.8GHz라면..) double gettime() { unsigned long long time; __asm__ volatile("rdtsc" : "=A" (time)); return time / 2.8e9; } 더보기
스도쿠 백트레킹으로 구현한 스도쿠 // 3*3 박스를 탐색하기위한 기준점으로 부터 변위차 const int dx[] = {0, 1, 2, 0, 1, 2, 0, 1, 2}; const int dy[] = {0, 0, 0, 1, 1, 1, 2, 2, 2}; // 문제가 풀렸나요? bool solved = false; // 문제를 푼다 // board - 확정된 숫자 판 // candi - 후보 숫자들 void solve(vector board, vector candi) { int i, j, k, m; bool loop = true; // 이미 풀렸으면 리턴 if (solved) return; // 일단은 논리적으로 할 수 있는데까지 푼다 while (loop) { loop = false; // 후보 숫자를 좁힌다... 더보기
Ternary Search Ternary Search(터너리 서치)는 함수의 최대나 최소점을 찾는 알고리즘으로 바이너리서치와 그 동작방법이 비슷하다. 터너리 서치로 최대점을 찾을 수 있는 함수는 최대점을 기준으로 왼쪽은 단조증가 오른쪽은 단조감소 해야한다. 마찬가지로 최소점을 찾을 수 있는 함수는 최소점을 기준으로 왼쪽은 단조감소 오른쪽은 단조증가 해야한다. 다시말해 지역 곡소점이나 극대점이 반드시 하나 존재해야 하고 이 점이 전역 최대나 최소점이 되어야 한다. 최대점을 찾아보자 a < b 인 두 점 a, b 가 있고 함수 f(x)의 최대점이 a와 b사이에 있다고 했을 때 a < a' < b' < b 인 a'과 b'을 잡을 수 있다. 이때 f(a') < f(b') 이라면 [a, a'] 구간은 단조증가하고 이 구간에 f(b') 보다.. 더보기
External Path Length IPL(Internal Path Length): Binary Tree의 각 노드의 depth의 합 EPL(Extend Path Length): Extended Binary Tree에 새로 추가된 노드들의 depth의 합 위 그림에서 왼쪽의 트리가 원래의 Binary Tree이고 오른쪽의 트리가 Extended Binary Tree이다. 오른쪽의 트리에서 동그라미로 그려진 노드가 Internal이고 네모로 그려진 노드가 External노드, 즉 원래의 Tree를 Extended Binary Tree로 만들기 위해 추가된 노드들이다. IPL은 동그라미로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값이 11이 된다. EPL은 네모로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값은 25이다.. 더보기
Syntax Highlighter 사용 웹페이지에 게시물을 쓰면서 가장 힘든것 중 하나가 소스코드를 올리는 것이었다. Syntax Highlighter는 이런 고충을 해결해주는 깜찍한 프로젝트가 아닌가 생각한다. Syntax Highlighter라는 것이 있다는 것은 알고는 있었지만 그동안 적용하기가 귀찮아서 이래저래 미뤄왔었는데.. 이곳에 블로그를 새로 연 겸사겸사 해서 Syntax Highlighter를 적용하기로 했다. 적용방법은 http://gyuha.tistory.com/193에 설명이 잘 되어있다. 사용방법은 다음과 같다. 일단 편집모드를 HTML로 변경하고 코드가 필요한 부분에 아래와 같이 입력한다. ... some code here ... 혹은.. ... some code here ... 주의할 점은 pre테그를 사용할 때는 더보기

티스토리툴바