요즘 본의 아니게 알고리즘 공부를 좀 하면서 깨달은 바에 대해 몇 개 적어본다.
1) Java의 System.in/out 은 굉장히 느리다. 얼마나 느리냐고? 다음은 10,000,000 정수를 읽는데 걸리는 수행시간이다:
Input Method | Time (sec) |
C scanf("%d", &arg) | 3.78 |
Scanner.parseInt() | 29.52 |
BufferedReader + inline Integer.parseInt | 2.89 |
BufferedReader + Reader.nextInt method | 3.01 |
단순히 2 ~ 3배 느린게 아니라 10배 가까이 차이가 난다. 이 때문에 BufferedReader 그리고, 출력에 있어서는 StringBuilder를 사용해야만 시간 초과를 피할 수 있다. 9935번 문자열 폭발이 대표적인데 알고리즘이 문제가 아니라 System.out.print 속도가 느려서 해결하기 쉽지 않다.
2) 최적화된 C/C++ 프로그램 속도는 빠르지만 역시나 코드는 더러워서 볼 수 가 없다 :/ 빠른게 능사가 아니란 말이다.
아래는 내 코드 (수행속도: 70 ms) 와 속도로 1위한 사람의 C++ 코드 (수행속도: 0 ms) 다. 물론 개발자 차이가 있을 수 있는데 ㅋ 일반적으로 Java나 함수형 언어에 익숙한 개발자는 대게 코드가 수식과 같고, C/C++은 무슨 연유인지 알 수 없으나 네이밍도 그렇고 코드가 대게가 지저분. 이 때문에 알고리즘 구현과 수행속도는 개발자의 평가기준이 절대 될 수 없다고 생각한다. Jeff Dean께서 그리 말씀하셨다니 나도 한마디 거들면 C++은 혐오스럽다.
한번 직접보시라:
import java.util.Scanner;
public class Main {
static int[] a;
static int[] memo;
private static int calculate(int i) {
if (i == 0) memo[i] = a[i];
else memo[i] = Math.max(a[i], memo[i - 1] + a[i]);
if (i == a.length - 1) {
return memo[i];
} else {
return Math.max(calculate(i + 1), memo[i]);
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
a = new int[n]; memo = new int[a.length];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt();
System.out.println(calculate(0));
sc.close();
}
}
vs.
#include
#include
namespace my
{
struct istream{};
istream cin;
inline bool is_num( char c ){ return ( c >= '0' && c <= '9' ); }
inline bool is_negative( char c ){ return c == '-'; }
inline istream& operator>>( istream& in, int& out )
{
char c; out = 0; bool neg = false;
while( c = getchar() ){ if( is_negative(c) ){ neg = true; break; } if( is_num(c) ){ out += (c-'0'); break; } }
while( c = getchar() ){ if( !is_num(c) ) break; out *= 10; out += (c-'0'); }
if( neg ) out *= -1;
return in;
}
inline void calc_max( int& max, int value ){ if( max < value ) max = value; }
inline void calc_min( int& min, int value ){ if( min > value ) min = value; }
}
int main( int argc, char** argv )
{
int N;
my::cin >> N;
int curr_max = std::numeric_limits::min();
int curr_min = 0;
int temp_min = 0;
int n, accum = 0;
for( int i = 0; i < N; ++i )
{
my::cin >> n;
accum += n;
if( accum > curr_max )
{
curr_max = accum;
}
if( accum - temp_min > curr_max - curr_min )
{
curr_max = accum;
curr_min = temp_min;
temp_min = 0;
}
if( accum < temp_min )
{
temp_min = accum;
}
}
printf("%d\n", curr_max-curr_min);
return 0;
}