반응형 #111 #11 : 그리드에서 가장 큰 곱수 구하기(Brute Force) 이번 문제는 사실 효율적인 알고리즘을 찾기가 어렵네요. 난이도 5%로 아주 쉬운 문제로 평가되어 있는 문제입니다. 탐욕 알고리즘을 이용해서 풀어볼려고 시도를 했는데, 탐욕 알고리즘이 늘 최선의 결과를 내는 것이 아니고, 오히려 정렬하는 시간 때문에 속도 향상을 기대하기 힘드네요. 400개의 데이터를 정렬하는 것 자체가, 순차적으로 모든 곱을 계산하는 것보다 기본적으로 점근적 접근상 더 큰 값을 가지니까요. 효율로 따져서 득 될 것이 없다고 생각했습니다. 제가 처음에 생각했던 탐욕 알고리즘은, 가장 큰 수부터 차례대로 근처에 있는 곱을 계산하고, 현재의 최대값이 다음 가장 큰수의 네제곱수보다 크다면, 거기서 종료하는 방법이었습니다. 이 알고리즘으로 한다면, 제일 큰 곱수를 구할 수 있습니다만, 과연 이게 .. 2014. 12. 28. 이전 1 다음 728x90