Code Review (12) 썸네일형 리스트형 [ SWEA 14510번 나무 높이 ] Python 코드 (Greedy) 1. 문제 SWEA 14501번 나무 높이 2. 풀이 완전탐색 기반으로 풀이할 방법이 생각나지도 않을 뿐더러, 설사 어떻게 생각해낸다 하더라도 경우의 수가 너무많다. 따라서 Greedy로 풀어야한다. 이름부터 사악한 Greedy 알고리즘이란, 지역적인 최적값 선택의 연속이 글로벌한 최적값으로 이루어진다는 것인데 실제 문제를 풀어보면, 그냥 알아서 잘 짜야한다. 나는 흡사 IQ 테스트같다고 생각한다. 따라서 Greedy한 알고리즘을 만들 때 가장 중요한 것은 코드가 너무 많은 if문으로 case를 나누지 말아야한다. 그러면 일단 Greedy하지 않을 뿐더러, 무엇보다 우리가 푸는 문제가 누군가에 의해 만들어졌다는 것을 고려할 때, 코드가 지저분하게 케이스를 나누고 있다면 접근방식이 잘못 되었을 가능성이 농.. [ 백준 1890번 점프 ] Python 코드 (DP) 1. 문제 백준 1890번 점프 2. 풀이 백트래킹, 메모이제이션, DP을 모두 적용시킬 수 있는 아주 흥미로운 문제이다. (아물론 제약조건 때문에 DP를 적용한 코드만 통과했다.) 3가지 풀이방법 모두 완전탐색을 기반으로 한다. 다만 그 효율성을 어떻게 높였는지에 따라 알고리즘이 분류된 것일 뿐이다. 백드래킹은 가지치기 코드를 통해 유효하지 않은 상태트리(경우의 수)를 더이상 탐색하지 않는다. 메모이제이션은 탑다운 방식으로 탐색을 이어나가는 중, 중복되는 상태트리를 만나는 경우 저장된 값을 불러온다. DP는 바텀업 방식으로 탐색을 하되, 이전 탐색의 값을 기억해두었다가 적절하게 재활용하여 완전탐색을 만족시킨다. 개인적으로 백트래킹과 메모이제이션은 어느 정도 코드의 정형화가 가능하기에 상대적으로 쉬운 반.. 이전 1 2 다음
