Problem-solving/알고리즘 정리4 탐욕법 (Greedy method) 각 단계마다 지금 당장 가장 좋은 방법만을 선택한다. 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다. 2020. 5. 15. 동적 계획법(Dynamic programming) 함수의 결과값을 저장해 놓는다. 동일한 함수 중복 호출 방지용. 저장해 놓은 결과값 재사용으로 불필요한 함수의 중복 호출 제거. 2020. 5. 14. 분할 정복(Divide and Conquer) 문제를 반으로 쪼개고, 또 다시 반으로 쪼개고 반복.. 가장 작은 단위까지 쪼갠다. 쪼개진 문제들을 해결하면서 원래의 문제까지 다시 합쳐나간다. 재귀 호출 사용. 일반적 재귀 호출과 다른 점 일반적 재귀 호출 : (한 조각 + 나머지 전체)의 형태로 나눔 분할 정복 : (반 + 반)의 형태로 나눔 짝수 개의 문제인 경우 : (반 + 반)으로 나눔. 홀수 개의 문제인 경우 : (짝수 개의 문제 + 한 문제)로 일단 나누어 놓고, 짝수 개의 문제를 반으로 나눔. (반에 가까운 짝수 개의 문제 + 반에 가까운 홀수 개의 문제)로 나누면 중복 계산이 많아짐. 2020. 5. 14. 부르트 포스(Brute Force) 무식하게 일일이 푸는 방법 for문쓰지말고 재귀로 base case(기저 사례) 설정을 잘 해야 한다. 중복 방지 특정 형태를 갖는 답만을 센다. ex) 사전순 특정한 순서대로 답을 생성하도록 강제한다. ex) 빈 칸 중에서 가장 윗 줄, 가장 왼쪽에 있는 칸을 처리. 2020. 5. 13. 이전 1 다음