'프로그래밍 언어/코딩연습'에 해당되는 글 1건
[Google Code Jam] Round 1A A번 - Minimum Scalar Product[Google Code Jam] Round 1A A번 - Minimum Scalar Product
Posted at 2008. 11. 23. 20:43 | Posted in 프로그래밍 언어/코딩연습문제 : http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiE2QUM
v1 = (x1,x2,x3....xn), v2 = (y1,y2,y3...yn)
이렇게 두 개의 벡터가 주어졌을 때 scalar product 값은
x1*y1 + x2*y2 + x3*y3 + ... + xn*yn 이다.
예를 들어 v1=(1 3 -5) v2=(-2 4 1
그냥 scalar product = 1*-2 + 3*4 + -5*1 = 5 이고
Minimum Scalar Product = -5*4 + 3*-2 + 1*1 = -25 이다.
이 문제는 주어진 인풋에 대해 각 벡터의 Minimum Scalar Product 값을 구하면 된다.
대충 알고리즘은 이렇다.
저렇게 했을 때 최소값이 나온다. 나는 증명 못한다. 증명은 구글에게 물어볼 것.
대충 소스코드는 다음과 같다.(전체 소스코드는 생략함)
하이라이팅 쉽게 하는 법 없을까;
SyntaxHighLighter 는 색이 맘에 안 들고;
vs2005에서 작성된 코드를 복사해서 마소 워드에 붙여넣어 다시 복사하여 블로그에 붙여넣으면 되긴 하는데
html 코드가 매~~~~~~~우 더러워진다. 워드용 xml 까지 덕지덕지 ㄷㄷㄷ
v1 = (x1,x2,x3....xn), v2 = (y1,y2,y3...yn)
이렇게 두 개의 벡터가 주어졌을 때 scalar product 값은
x1*y1 + x2*y2 + x3*y3 + ... + xn*yn 이다.
Minimum Scalar Product는 v1과 v2의 각 요소를 재배치하여
scalar product 값을 최소화 시키는 문제이다.
scalar product 값을 최소화 시키는 문제이다.
예를 들어 v1=(1 3 -5) v2=(-2 4 1
그냥 scalar product = 1*-2 + 3*4 + -5*1 = 5 이고
Minimum Scalar Product = -5*4 + 3*-2 + 1*1 = -25 이다.
이 문제는 주어진 인풋에 대해 각 벡터의 Minimum Scalar Product 값을 구하면 된다.
대충 알고리즘은 이렇다.
1. v1의 각 요소들을 오름차순으로 정렬한다
2. v2의 각 요소들을 내림차순으로 정렬한다.
3. Scalar Product를 수행한다.
2. v2의 각 요소들을 내림차순으로 정렬한다.
3. Scalar Product를 수행한다.
저렇게 했을 때 최소값이 나온다. 나는 증명 못한다. 증명은 구글에게 물어볼 것.
대충 소스코드는 다음과 같다.(전체 소스코드는 생략함)
| void Algorithm() { std::string line; ReadLineFromFile(line); int nCases = atoi(line.c_str()); for(int i=0; i<nCases; i++) // nCases=Minimum Scalar Product 문제 개수 { /* n=v1,v2 벡터에 몇 개의 요소들이 있는가 */ do{ ReadLineFromFile(line); }while(line == ""); int n = atoi(line.c_str()); int* v1 = new int[n]; int* v2 = new int[n]; /* v1 저장 */ for(int j=0; j<n; j++) ReadIntToken(v1[j]); /* v2 저장 */ for(int j=0; j<n; j++) ReadIntToken(v2[j]); /* 오름차순 정렬 (작은값이먼저) */ qsort(v1, n, sizeof(int), MinimumScalarProduct::AscOrder); /* 내림차순 정렬 (큰값이먼저) */ qsort(v2, n, sizeof(int), MinimumScalarProduct::DescOrder); long long sum = 0; /* 각 벡터 요소의 곱이 integer의 범위를 넘기도 한다 */ for(int j=0; j<n; j++) sum += (long long)v1[j]*(long long)v2[j]; /* 출력 형태 맞추기 */ char out[50]; /* %I64d로 출력해야 long long(__int64 출력된다) */ sprintf_s(out, 50, "Case #%d: %I64d", i+1, sum); WriteLineToFile(out); delete[] v1; delete[] v2; } } static int __cdecl AscOrder(const void* a, const void* b) { return (*(int*)a) - (*(int*)b); } static int __cdecl DescOrder(const void* a, const void* b) { return (*(int*)b) - (*(int*)a); } |
하이라이팅 쉽게 하는 법 없을까;
SyntaxHighLighter 는 색이 맘에 안 들고;
vs2005에서 작성된 코드를 복사해서 마소 워드에 붙여넣어 다시 복사하여 블로그에 붙여넣으면 되긴 하는데
html 코드가 매~~~~~~~우 더러워진다. 워드용 xml 까지 덕지덕지 ㄷㄷㄷ
