허성규
8 years ago
컴퓨터 과학이 여는 세계
Avg 3.9
1.상식적 알고리즘 정리 . -모조리 훑기exhaustive search : 내가 문제를 풀 때 접근하는 주된 방식. 모든 경우의 수를 생각하고 판단한다. 경우의 수를 모두 파악하는 과정에서 시간/메모리 비용이 너무 많이 든다. . -되돌아가기backtracking : 바둑이나 장기에서 수 물리는 것과 같다. 되돌아간 지점까지는 같은 행보를 하고 다음 행보를 재수정한다. . -나눠풀어 합치기divide-and-conquer : 문제를 작은 크기로 쪼갠 다음 작은 문제들의 답을 합쳐 전체 문제의 답을 구한다. 예를 들면 세계인구조사를 국가 단위로 진행하여 결과 취합하는 것. . -기억하며 풀기 dynamic programming : 문제의 일부분을 풀고 다른 부분을 풀 때 이전에 구한 부분의 답을 활용한다. 예를 들면 피보나치 수열에서 f3+f4=f5일 때 f1+f2=f3의 이전 결과를 활용한다. . -질러놓고 다듬기 iterative improvement : 한 개의 답 후보를 임의로 선택하고, 일부분을 손질하면서 답에 가까워져 간다.