오늘 새벽 0시에 Topcoder 를 드디어 시작했다.
Topcoder를 위해 C++ 서적을 뒤벼서 문법이나 STL을 1주일간 공부하고 참여했던만큼 의미가 남달랐다. ㅎㅎ
C++을 대학 졸업하고부터 거의 코딩한 적이 없었기 때문에 책을 보면서 생소하게 느껴지는 부분도 좀 있었다.
특히 그동안 몇가지 문제들을 C로 직접 Linked List같은 걸 구현해가며 풀었었는데, STL을 보고 나서는 입이 딱 벌어지는 느낌이었다.
STL이나 boost나 이런 좋은 라이브러리들이 있는데.. 아직도 C로만 짜고 있는 우리회사 기술력이 한심하게 느껴지는 순간이었다. C++을 제대로 공부해보고자 Effective시리즈 책들도 주문해서 책장에 꽂아놨다. ㅡㅡㅋ;
Topcoder 문제를 어제 오후에 몇개 풀어봤는데, Div2에 1번문제정도는 풀 수 있을 거 같아서, 어제 밤에 그냥 참가해봤다.
1번문제는 속도, 가속도, 거리 같은 개념이 나오면서 최소시간을 구하는 문제였다.
문제는 그리 쉬운문제였는데, 속도니 가속도니 하는 개념을 고등학교 물리시간 이후로 본 적이 없어서 당황스러웠다. 네이버에서 가속도, 거리 이런 내용으로 지식인에 고등학교 애들 질답올린 글 봐가면서 수식을 파악해갔다.
거의 40분을 잡아먹은 문제;;
2번은 무슨 복소수 개념이 나왔다. 문제를 한 10분인가 봤는데 이해가 안되서 패스..하고 그냥 3번을 열어봤다.
3번문제는 어려울 거 같아서, 그냥 문제만 이해해볼까 해서 열었는데, 생각보다 어려운 문제는 아니었다.
피보나치 수열 비슷하게, 재귀를 돌리면서 푸는 문제였는데 시간이 촉박해서 막 코딩에 들어갔다.
주어진 예제 5개정도를 만족시키는 걸 보고 컴파일하고, Submit을 했는데.. 마감 30초전이었다;
3번문제를 제출하고 나니 Score가 750점인가가 더해져서 900점대.. 방에서 순위권이었다. 잠깐 기분좋았음..
그렇게 코딩시간이 끝나고, 쉬는시간 5분동안 올린 소스를 보니, 아뿔싸!
내가 참고한 함수원형은 JAVA의 것이고, C++은 틀린 것이 아닌가..
JAVA에서는 return값이나 n값이 long형인데, C++은 long long 이었다;;
이런.. 문제에서 n은 10^12까지 주어질 수 있기 때문에 C++의 long형에서는 값을 다 처리하지 못한다;
아쉬움을 뒤로하고, Challenge Time이 시작됐는데.. 30초도 안되서, 누군가 내 3번문제를 Challenge Succeeded를 했다; 보나 안보나 long형 넘는 값을 넣었을 것이다.. 이론;
내가 짠 소스를 통과한 사람들 소스랑 비교해보니, long long으로 안한 문제와 함께, 다른사람들은 한번 구한값을 map같은데다 보관해 뒀다가, 다시 재귀를 안돌리고, 바로 리턴하게 알고리즘을 짜놨더라..
이걸 좀 찾아보니 그 유명한 DP알고리즘에 속하는거였다. 알고리즘 책을 공부할 필요성을 다시 한번 각인하는 계기가 됨.(DP알고리즘 안써서 올려보니, 큰값을 넣으면 수행시간 2초가 초과되었다고 나옴. topcoder에서 문제에는 명시되어있지 않지만, 수행시간 제한도 있는듯.. 효율적인 알고리즘을 항상 고려해야할듯 ㅎ;)
나도 Challenge해볼까 하고 다른사람들 소스를 보는데.. Challenge는 좀더 topcoder에 익숙해져야 가능할듯해서 패스..
아침에 회사와서 Topcoder rating을 조회해보니 오 그래도 1035점으로 녹색으로 아이디가 바껴있네.. ㅎㅎ
Topcoder 첫 매치의 경험은 아주 재미있었다. 그리고, 알고리즘이나 코딩연습에 대한 자극도 많이 된 거 같고, 앞으로 당분간 계속 참여해야 겠다..
DP알고리즘 검색하다가 김창준님의 좋은 글귀가 있어 기록해 둔다.
내가 하고 있는 학습방법이 제대로 가고 있구나 하는 걸 느낄 수 있는 좋은 자극제였음.
http://eminency.springnote.com/pages/843158
ps. 3번 문제 다시 풀어서 소스기록(이미 계산된 수는 map에 넣어서 바로 리턴하도록 변경)
----------------------------------------------------------------------------------------
#include <vector>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
map<long long, long long> np;
class InfiniteSequence
{
public:
long long recul(long long n, int p, int q)
{
if(n == 0 ) return 1;
if(np.find(n) != np.end()) return np[n];
np[n] = recul(n/p, p, q) + recul(n/q, p, q);
return np[n];
}
long long calc(long long n, int p, int q)
{
if(n == 0) return 1;
return recul(n/p, p, q) + recul(n/q, p, q);
}
};
Topcoder를 위해 C++ 서적을 뒤벼서 문법이나 STL을 1주일간 공부하고 참여했던만큼 의미가 남달랐다. ㅎㅎ
C++을 대학 졸업하고부터 거의 코딩한 적이 없었기 때문에 책을 보면서 생소하게 느껴지는 부분도 좀 있었다.
특히 그동안 몇가지 문제들을 C로 직접 Linked List같은 걸 구현해가며 풀었었는데, STL을 보고 나서는 입이 딱 벌어지는 느낌이었다.
STL이나 boost나 이런 좋은 라이브러리들이 있는데.. 아직도 C로만 짜고 있는 우리회사 기술력이 한심하게 느껴지는 순간이었다. C++을 제대로 공부해보고자 Effective시리즈 책들도 주문해서 책장에 꽂아놨다. ㅡㅡㅋ;
Topcoder 문제를 어제 오후에 몇개 풀어봤는데, Div2에 1번문제정도는 풀 수 있을 거 같아서, 어제 밤에 그냥 참가해봤다.
1번문제는 속도, 가속도, 거리 같은 개념이 나오면서 최소시간을 구하는 문제였다.
문제는 그리 쉬운문제였는데, 속도니 가속도니 하는 개념을 고등학교 물리시간 이후로 본 적이 없어서 당황스러웠다. 네이버에서 가속도, 거리 이런 내용으로 지식인에 고등학교 애들 질답올린 글 봐가면서 수식을 파악해갔다.
거의 40분을 잡아먹은 문제;;
2번은 무슨 복소수 개념이 나왔다. 문제를 한 10분인가 봤는데 이해가 안되서 패스..하고 그냥 3번을 열어봤다.
3번문제는 어려울 거 같아서, 그냥 문제만 이해해볼까 해서 열었는데, 생각보다 어려운 문제는 아니었다.
피보나치 수열 비슷하게, 재귀를 돌리면서 푸는 문제였는데 시간이 촉박해서 막 코딩에 들어갔다.
주어진 예제 5개정도를 만족시키는 걸 보고 컴파일하고, Submit을 했는데.. 마감 30초전이었다;
3번문제를 제출하고 나니 Score가 750점인가가 더해져서 900점대.. 방에서 순위권이었다. 잠깐 기분좋았음..
그렇게 코딩시간이 끝나고, 쉬는시간 5분동안 올린 소스를 보니, 아뿔싸!
내가 참고한 함수원형은 JAVA의 것이고, C++은 틀린 것이 아닌가..
JAVA에서는 return값이나 n값이 long형인데, C++은 long long 이었다;;
이런.. 문제에서 n은 10^12까지 주어질 수 있기 때문에 C++의 long형에서는 값을 다 처리하지 못한다;
아쉬움을 뒤로하고, Challenge Time이 시작됐는데.. 30초도 안되서, 누군가 내 3번문제를 Challenge Succeeded를 했다; 보나 안보나 long형 넘는 값을 넣었을 것이다.. 이론;
내가 짠 소스를 통과한 사람들 소스랑 비교해보니, long long으로 안한 문제와 함께, 다른사람들은 한번 구한값을 map같은데다 보관해 뒀다가, 다시 재귀를 안돌리고, 바로 리턴하게 알고리즘을 짜놨더라..
이걸 좀 찾아보니 그 유명한 DP알고리즘에 속하는거였다. 알고리즘 책을 공부할 필요성을 다시 한번 각인하는 계기가 됨.(DP알고리즘 안써서 올려보니, 큰값을 넣으면 수행시간 2초가 초과되었다고 나옴. topcoder에서 문제에는 명시되어있지 않지만, 수행시간 제한도 있는듯.. 효율적인 알고리즘을 항상 고려해야할듯 ㅎ;)
나도 Challenge해볼까 하고 다른사람들 소스를 보는데.. Challenge는 좀더 topcoder에 익숙해져야 가능할듯해서 패스..
아침에 회사와서 Topcoder rating을 조회해보니 오 그래도 1035점으로 녹색으로 아이디가 바껴있네.. ㅎㅎ
Topcoder 첫 매치의 경험은 아주 재미있었다. 그리고, 알고리즘이나 코딩연습에 대한 자극도 많이 된 거 같고, 앞으로 당분간 계속 참여해야 겠다..
DP알고리즘 검색하다가 김창준님의 좋은 글귀가 있어 기록해 둔다.
내가 하고 있는 학습방법이 제대로 가고 있구나 하는 걸 느낄 수 있는 좋은 자극제였음.
http://eminency.springnote.com/pages/843158
ps. 3번 문제 다시 풀어서 소스기록(이미 계산된 수는 map에 넣어서 바로 리턴하도록 변경)
----------------------------------------------------------------------------------------
#include <vector>
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
map<long long, long long> np;
class InfiniteSequence
{
public:
long long recul(long long n, int p, int q)
{
if(n == 0 ) return 1;
if(np.find(n) != np.end()) return np[n];
np[n] = recul(n/p, p, q) + recul(n/q, p, q);
return np[n];
}
long long calc(long long n, int p, int q)
{
if(n == 0) return 1;
return recul(n/p, p, q) + recul(n/q, p, q);
}
};
반응형