블로그 이미지
bro.Yobi

Rss feed Tistory
CSE/Methodology 2006.11.13 23:59

Think Discretely..

원칙적으로 0과 1의 기계는 이산적일 수 밖에 없다. 무엇이든지 0과 1의 깡통으로 셈하려면 이산적으로 만들어져야한다.

이 세상을 '0과 1의 서랍' 속에 넣자.
CSE/Methodology 2004.06.23 23:19

몇가지 방법론..

알고리즘을 설계하는 일반적인 방법론은 있는가? 우리가 풀고자 하는 문제가 매우 다양하여 모든 문제 혹은 대부분의 문제에 대하여 적용될 수 있는 방법론은 존재하지 않고 대신에 꽤 많은 부류의 문제에 대하여 적용될 수 있는 방법론으로 욕심쟁이 방법, 분할 정복 방법, dynamic programming 방법 등이 있다.

욕샘쟁이 방법

해를 구하기 위한 일련의 선택 과정마다 그 단계에서 최선이라고 볼 수 있는 선택을 행해나가면 결과적으로 전체적인 최적 해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다.

분할 정복 방법 : bucket sort처럼..

dynamic programming
CSE/Methodology 2004.05.14 22:34

제한된 데이터, 공간에서 같은 방법으로 반복되는 연산이 있는 경우.

주어진 데이터에서 몇개의 한정된 새로운 데이터만 뽑아내서, 그것들을 저장하고있으면 기존의 연산을 더 빠른 시간에 처리할 수 있는지 확인해라.

피보나치 수열을 어떤 범위내에서 자주 구하는 경우, 그 범위내에서 모든 피보나치의 값을 저장해두면 편리할 수 있다. 또 이 경우, fibo(n)에서 fibo(1)로 재귀적으로 값을 구하면서 저장하는것 보다 fibo(1)에서 fibo(n)으로 단순히 더해가면서 구하는 것이 효율적이다. 첫번째 방법대로 하면 함수가 계속 스택에 계속 push되고 다시 pop되면서 구하는 값들이 저장된다. 하지만 두번째로 구하면 그냥 순차적으로 값이 저장된다.
CSE/Methodology 2004.05.14 22:20

차원 줄이기

1차원적인 문제가 차원이 높아지면 풀리지 않는 경우도 있다.
하지만 어떤 경우는 1차원적인 해결방법인 다차원에서 응용되서 문제를 더 빨리 풀거나 풀기 어려웠던 문제를 풀 수 있게되는 경우가 있다.

Maximum subrectangle sum에서 준희가 생각해낸 알고리즘이 그것이다.
1차원문제로 차원을 줄여서 생각하고 그것을 2차원에 응용시켰다. 덕분에 O(N^4)에서 O(N^3)으로 줄일 수 있었다.
CSE/Methodology 2004.05.14 22:17

검사를 복잡(?)하게 하기

복잡하기 하기라기 보다는, 가능성 없는 루틴을 빨리 벗어나게 검사해야 한다는것..
만약 recursion을 사용할 경우 루틴 하나가 없어짐으로써 엄청난 연산을 절약할 수 있다.

2GB의 가상메모리와 20분이라는 시간을 사용해도 문제를 풀지 못하던 코드가.. 몇줄의 수정으로 몇십MB의 가상메모리를 사용해서 1분정도에 문제를 풀었다.
TOTAL 238,851 TODAY 2