[해결] 알고리즘 줄이기..
두 개의 argument를 받아옵니다.
가령 10, 8 이라고 입력하면 10개의 숫자 셋에서 각 2개를 선택하고 그 합이 8과 비슷한 경우를 찾는겁니다.
4 10 이라고 하고
1 2 3 4 를 입력하면
(3,4)가 10에 제일 가까운 7을 출력하므로
10과 합이 비슷한 경우는 1번 나옵니다.
아 물론 자기 자신은 중복하지 않습니다.
그래서 제 알고리즘은
1. quick sort로 주어진 배열을 sort한 다음
2. for 문을 두 번 돌려 각 합과 주어진 수와의 difference 를 구하고.
3. 마지막으로 difference 배열을 sort하여 diff[0] ~ diff[max] 에서 diff[0]과 같은 값을 찾아서 count 해주면 됩니다.
근데 자꾸 이게 잘못된 알고리즘이고 특정 case를 집어넣었을 때 Wrong answer가 된다고 하더군요.
도대체 어떻게 해야 더 나은 알고리즘이 되는지 모르겠습니다. 벌써 이틀이 지나갑니다 ㅠㅠ..
// 추가
혹시 내용의 요지중에 알고리즘을 줄이고 싶기는 한데 접근 방법을 어떻게 해야할지 모르겠습니다.
지금 나와 있는 것은 O(N^2)라 Time complexity가 엄청 커서요. 서버측에 답변을 내봐도 time limit > 3000ms에 걸립니다.
그래서 두가지 방법을 생각해 볼 수 있는데
1. 앞 뒤 피벗을 설정해서 앞에서 구하는 sum과 뒤에서 구하는 sum을 주어진 수와 비교해서 가장 작은 걸 취한다.
2.10 같으면 5 + 5 가 되듯이 주어진 수를 2등분 한 후에 그 수에 가까운 수를 찾는 방법이 있는걸로 생각할 수 있는데
각각을 어떻게 생각해야 할 지 모르겠습니다;
전산을 시작한지 얼마 안되서 잘 안되네요;
정확한 문제는 http://alen.pufs.ac.kr/~shkim/board/board.php?board=kkkgeneral&command=body&no=27 에 있습니다.
테스팅도 해보실 수 있습니다;
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare (const void *a , const void *b)
{
return (*(int *)a - *(int *)b);
}
int main(void)
{
int n, z, q, c, sz, idx=0, idx2, times;
int j, l, m,o, b, k;
scanf("%d",&n);
for (z = 0; z < n; z ++) {
scanf("%d %d",&q , &c);
if (q < 2 || q > 1000000) return 0;
int *set; set = (int*)malloc(sizeof(int)*q);
sz = q;
for (j = 0 ; j < q ; j++)
{
scanf("%d",&set[j]);
if (set[j] < -100000000 || set[j] > 100000000)
return 0;
}
for (j = 0 ; j < q ; j++)
{
for (b = 0; b < q ; b++)
if (b != j && set[b] == set[j])
return 0;
}
int *diff; diff = (int*)malloc(sizeof(int)*l);
l = 0;
times = 0 ;
for(idx = 0; idx < sz; idx++)
{
for(idx2 = idx + 1; idx2 < sz; idx2++)
{
if( idx < idx2 )
{
diff[l] = abs(set[idx] + set[idx2] - c);
l++;
}
}
m = l;
}
qsort(diff, m, sizeof(int), compare);
for (o=0; o<m ; o++){
if (diff[o] == diff[0])
++times;
}
printf("%d\n" ,times);
"\b";
}
return 0;
}
http://kldp.org/node/125550
http://kldp.org/node/125550
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
음; 조금 다른 것 같습니다.이 문제는 2개씩
음; 조금 다른 것 같습니다.
이 문제는 2개씩 짝지은 pair의 합이 원하는 값에 가까운지 알아보는 과정이구요.
그래서 diff[m] = abs(set[idx] + set[dix2] - c); 를 구한겁니다.
오늘도 달린다. :)
np문제라서요.
np문제라서요.
재벌 2세가 재벌이 될 확률과
금메달리스트 2세가 금메달을 딸 확률이 비슷해지도록
자유오픈소스 대안화폐를 씁시다.
아이디의 아이디어 무한도전
http://blog.aaidee.com
귀태닷컴
http://www.gwitae.com
조금 다른데, 거의 같은 문제입니다. 적당한
조금 다른데, 거의 같은 문제입니다.
적당한 휴리스틱 이상은 불가능할것 같네요
피할 수 있을때 즐겨라! http://melotopia.net/b
다른 문제입니다.
cleansugar님과 snowall님께서 이 문제를 예전에 올라온 문제( http://kldp.org/node/125550 )와 같다고 하셨는데,
제가 보기에 다른 문제로 보입니다. 아마 두 분께서 문제 내용에 오해가 있으신 것 같습니다.
질문자께서 문제를 설명하실때
> 4 10 이라고 하고
> 1 2 3 4 를 입력하면
> (3,4)가 10에 제일 가까운 7을 출력하므로
> 10과 합이 비슷한 경우는 1번 나옵니다.
> 아 물론 자기 자신은 중복하지 않습니다.
마지막 문장이 오해를 만든 것 같습니다.
질문하신 분의 의도는
"사용자로부터 두 개의 입력 변수 (q, c)를 받고,
q 개 만큼의 숫자열을 입력 받은 후
그 숫자열에서 2개의 숫자를 뽑을 수 있는 가능한 모든 조합 (combination)들의
숫자 두개의 합과 c의 차의 절대값이 제일 작은 (결국 c에 제일 가까운) 경우가 몇번 나오나"
인 것 같습니다. 즉, q! / 2! 의 조합의 개수 만큼 연산을 수행하면 될 거라 보입니다.
그리고 질문자께서 올리신 소스에 몇가지 문제점이 있습니다.
첫번째로 malloc 으로 할당된 변수는 나중에 free를 해줘야합니다.
안그러면 프로그램이 실행되는 동안에 계속 메모리가 쌓여가겠죠. (이 문제를 메모리 누수라고 부릅니다.)
두번째로 diff 에 malloc을 하실때 변수 l (영문자 "엘')이 초기화가 안 되어있거나 잘못된 값을 가지고 있습니다.
변수 z에 걸린 for문의 첫번째 실행시 변수 l 은 초기화가 안 되어있죠.
해당 for문의 두번째 실행부터는 변수 l 에 들어간 값이 바로 이전에 실행되면서 계산된 값이니까 의미가 없는 값을 가지고 malloc을 하고 있죠.
결국 예상할 수 없는 결과(운 좋게 성공할 수도 있고 실패할 수도 있는) 또는 런타임 에러가 나올 겁니다.
세번째로 quick sort 가 불필요하다고 생각합니다.
이건 질문자께서 고안하신 알고리즘이 quick sort에 기반으로 시작하셨기 때문인걸로 보입니다.
제가 생각하는 알고리즘은 minimum_difference 를 적당히 초기화합니다.
예를 들면 정수 최대값이나 아니면 q개의 숫자열의 첫번째와 두번째의 합에서 c와의 차이를 초기값으로 합니다.
그리고 숫자열에서 가능한 모든 combination의 숫자 두개의 합과 c와의 차이(변수 tmp라고 칭하겠습니다.)를 minimum_difference 와 비교합니다.
이때 가능한 세 가지 경우가 생기죠.
1. tmp == minimum_difference 일 때는 현재까지 알려진 가장 최소 차와 같은 경우가 발견된 것이므로 minimum_count++
2. tmp > minimum_difference 일 때는 현재까지 알려진 가장 최소 차보다 더 큰 경우니까 무시
3. tmp < minimum_difference 일 때는 현재까지 알려진 가장 최소보다 더 작은 것이 발견됬으니까 minimum_difference = tmp 로 갱신하고 minimum_count = 1 로 갱신합니다.
아래 제가 만든 소스 코드를 첨부해드립니다.
그리고 실행시 중간 과정을 알 수 있도록 minimum_difference 또는 minimum_count 가 갱신될 때마다 화면에 텍스트 메시지를 뿌리도록 했습니다.
#include <stdio.h> #include <stdlib.h> int main(int argc, char* argv[]) { int* set = NULL; int minimum_difference = 0; int minimum_count = 0; int n = 0, z = 0; int q = 0, c = 0; int i, j, tmp; scanf("%d", &n); for (z=0; z<n; z++) { scanf("%d %d", &q, &c); if (q < 2) { // check input value printf("warning! 'q' should be greater than 1\n"); z--; continue; } set = (int*)malloc(sizeof(int)*q); if (set == NULL) { // check the result of malloc printf("error! cannot allocate %d byte\n", q); } for (i=0; i<q; i++) { // get 'q' numbers from user scanf("%d", &set[i]); } // initialize minimum_difference and minimum_count minimum_difference = abs(set[0] + set[1] - c); minimum_count = 0; // calculate the difference between 'c' and all combination of 'set' // find the minimum difference and count it printf("####################################\n"); printf("this is input case #%d\n", z); printf("####################################\n"); printf("(value0, value1) current_difference, current_count\n"); for (i=0; i<q; i++) { for (j=i+1; j<q; j++) { tmp = abs(set[i] + set[j] - c); if (tmp == minimum_difference) { minimum_count++; printf("(%6d, %6d) %18d, %13d\n", set[i], set[j], minimum_difference, minimum_count); continue; } if (tmp > minimum_difference) { continue; } // if there is a smaller difference if (tmp < minimum_difference) { minimum_difference = tmp; minimum_count = 1; printf("(%6d, %6d) %18d, %13d (current_difference is updated)\n", set[i], set[j], minimum_difference, minimum_count); continue; } } } printf("\n\n"); if (set != NULL) { free(set); } } return 0; }입력 데이터는 아래와 같습니다.
결과는 다음과 같습니다.
아참!! 그리고 질문자께서 올리신 소스 코드로 유추하건데, 입력되는 q개의 숫자열에서 숫자 중복은 없다고 보는 것 같습니다?!?!
그러니까 "1 2 2 3 4" 같이 같은 숫자가 두번 이상 포함된 경우는 없는걸 확인해줘야하는 것 같은데,
제가 그 부분을 체크하는 걸 깜박했네요. ㅎㅎ
그럼 좋은 주말 되세요.
답변 감사합니다.
매우 섬세한 주석과 답변에 대해서 매우 감사드립니다.
혹시 내용의 요지중에 알고리즘을 줄이고 싶기는 한데 접근 방법을 어떻게 해야할지 모르겠습니다.
지금 나와 있는 것은 O(N^2)라 Time complexity가 엄청 커서요. 서버측에 답변을 내봐도 time limit > 3000ms에 걸립니다.
그래서 두가지 방법을 생각해 볼 수 있는데
1. 앞 뒤 피벗을 설정해서 앞에서 구하는 sum과 뒤에서 구하는 sum을 주어진 수와 비교해서 가장 작은 걸 취한다.
2.10 같으면 5 + 5 가 되듯이 주어진 수를 2등분 한 후에 그 수에 가까운 수를 찾는 방법이 있는걸로 생각할 수 있는데
각각을 어떻게 생각해야 할 지 모르겠습니다;
전산을 시작한지 얼마 안되서 잘 안되네요;
오늘도 달린다. :)
binary search 를 응용해서 N*log(N) 까지 가능할 것 같습니다.
처음엔 이 문제 실행 속도가 크게 중요하지 않을 것 같아서 N^2 으로도 충분할 것 같았는데요.
실행 속도가 중요하면 binary search 를 응용해서 N*log(N)까지 가능할 것 같습니다.
기본 전략은 이 문제를 쪼개서 정복 (divide and conquer) 하는 것입니다.
이해를 돕기 위해서 실례를 들겠습니다.
4 10
1 2 3 4
라는 입력을 예로 들겠습니다. (숫자열은 프로그램에서 오름차순으로 정렬(qsort 사용)한다고 가정합니다.)
여기서 (q, c) = (4, 10) 입니다. 그리고 숫자열에 중복되는 숫자는 없다고 가정합니다.
원본 문제의 내용은
"1 2 3 4 숫자 배열에서 숫자 두개를 선택해서 가능한 모든 조합의 합 중에서 가장 10에 가까운 경우가 몇 가지가 되는지 찾는 문제"
이걸 바꿔서 생각해보면 이미 하나의 숫자가 결정되어있다고 생각하고 두번째 숫자를 고르는 걸로 생각해보면 binary search 문제가 됩니다.
즉 이 문제는 q개의 서브 문제로 분할 될 수 있습니다.
위의 예에서는
"1은(는) 이미 선택되어있다고 가정하고 {2 3 4} 중에서 9에 제일 가까운 수 찾기
2은(는) 이미 선택되어있다고 가정하고 {1 3 4} 중에서 8에 제일 가까운 수 찾기
3은(는) 이미 선택되어있다고 가정하고 {1 2 4} 중에서 7에 제일 가까운 수 찾기
4은(는) 이미 선택되어있다고 가정하고 {1 2 3} 중에서 6에 제일 까까운 수 찾기"
로 바뀝니다.
9, 8, 7, 6 에 가까운 수를 찾게 되는 것은 서브 문제로 분할 할 때,
각각 1, 2, 3, 4은 이미 선택되어있다고 생각했으므로 c 에서 1, 2, 3, 4를 빼준 새로운 값에 가까운 수를 찾는 겁니다.
하지만, 위의 서브 문제는 중복된 조합이 들어갑니다. 예를 들면 첫번째 서브 문제에서 {1,2}라는 조합은
두번째 서브 문제에서 {2,1} 이라는 조합으로 고려가 되는 거죠.
그러므로 서브 문제 분할시에 중복을 고려하면 다음과 같이 바뀝니다.
"1은 이미 선택되어있다고 가정하고 {2 3 4} 중에서 9에 제일 가까운 수 찾기
2은 이미 선택되어있다고 가정하고 {3 4} 중에서 8에 제일 가까운 수 찾기
3은 이미 선택되어있다고 가정하고 {4} 중에서 7에 제일 가까운 수 찾기"
그럼 이제 서브 문제를 푸는 방법은 binary search 를 이용하게 됩니다.
주어진 배열에서 key 값이 어디에 존재하는지 찾는 거죠.
binary search 를 쓰면 log(N)만에 key 값의 위치를 알 수 있습니다.
예제에서 각 서브 문제의 key 값은 9, 8, 7 이죠.
그런데 문제는 9, 8, 7 이 배열에 존재 하지 않을 때입니다.
그렇기 때문에 기존에 bsearch 함수를 쓰면 안 됩니다.
직접 bsearch를 구현하시되 key 가 배열에 존재하지 않을 때를 고려해야하죠.
bsearch를 일반적으로 구현하신다면,
key 값이 배열에 "존재하지 않을 때" key 값에 아주 근접한 값의 위치를 찾을 수 있습니다.
(key 값이 배열에 존재한다면, 바로 해당 위치만 고려하면 됩니다.)
여기서 "아주" 근접하다는 것이 중요합니다.
아래 제가 소스코드를 첨부해드린 곳에서는 그 위치를 mid라는 변수에 저장했습니다.
하지만 아쉽게도 mid 위치가 실제로 가장 근접한 값이 아닐 수도 있죠.
그렇기 때문에 우리는 'mid-1' 과 'mid+1' 의 위치의 값도 검사를 해봐야합니다.
여기서 왜 mid-2, mid-3... 과 mid+2, mid+3.. 의 위치의 값은 볼 필요가 없는가?라는 질문은
이미 그들은 mid-1 또는 mid+1 보다 key 값에서 더 멀어지기 때문이죠.
bsearch 에서 mid를 갱신해나가는 동작 방식이 이걸 보장합니다.
다만 bsearch 가 보장 못하는 것은 mid-1, mid, mid+1 세 군대의 위치 중에서 정말 가장 가까운 값이 어디인가? 입니다.
그렇기 때문에 모두 확인을 해줘야합니다.
각 서브 문제의 결과를 local_minimum_difference, local_minimum_count 라고 생각하고
마지막에 진짜로 전체 문제에서의 minimum_difference 와 (local_minimum_difference 중에서 가장 최소값) 그것의 count를 보여주면 되겠죠.
아래 제 코드를 첨부해드립니다.
#include <stdio.h> #include <stdlib.h> void find_nearest_point(const int* set, const int key, const int start, const int end, int* local_minimum_difference, int* local_minimum_count); int compare(const void* value0, const void* value1); int main(int argc, char* argv[]) { int* set = NULL; int minimum_difference = 0; int minimum_count = 0; int local_minimum_difference = 0; int local_minimum_count = 0; int n = 0, z = 0; int q = 0, c = 0; int key = 0, start = 0, end = 0; // variables for binary search int i, j, tmp, flag_update; scanf("%d", &n); for (z=0; z<n; z++) { scanf("%d %d", &q, &c); if (q < 2) { // check input value printf("warning! 'q' should be greater than 1\n"); z--; continue; } set = (int*)malloc(sizeof(int)*q); if (set == NULL) { // check the result of malloc printf("error! cannot allocate %d byte\n", q); } for (i=0; i<q; i++) { // get 'q' numbers from user scanf("%d", &set[i]); } qsort(set, q, sizeof(int), compare); // calculate the difference between 'c' and all combination of 'set' // find the minimum difference and count it printf("####################################\n"); printf("this is input case #%d\n", z); printf("####################################\n"); printf("local minimum difference and count\n"); printf("(search key, start, end) (local_min_diff, local_min_count) (min_diff, min_count)\n"); for (i=0; i<q-1; i++) { { // this block takes intialization of iteration key = c - set[i]; start = i+1; end = q-1; local_minimum_difference = -1; // to check, initialize this negative number local_minimum_count = 0; flag_update = 0; } // find nearest point using binary search find_nearest_point(set, key, start, end, &local_minimum_difference, &local_minimum_count); if (i == 0) { // set the first result as the initial values of minimum_difference and minimum_count minimum_difference = local_minimum_difference; minimum_count = local_minimum_count; flag_update = 1; } else { // compare with minimum_difference and local_minimum_difference if (local_minimum_difference == minimum_difference) { minimum_count += local_minimum_count; } if (local_minimum_difference > minimum_difference) { // nothing happens } if (local_minimum_difference < minimum_difference) { minimum_difference = local_minimum_difference; minimum_count = local_minimum_count; flag_update = 1; } } printf("(%10d, %5d, %3d) ", key, start, end); printf("(%14d, %15d) ", local_minimum_difference, local_minimum_count); printf("(%8d, %9d) ", minimum_difference, minimum_count); if (flag_update) { printf("minimum_difference is updated"); } printf("\n"); } printf("the final result:\ndifference = %d, count = %d", minimum_difference, minimum_count); printf("\n\n"); if (set != NULL) { free(set); } } return 0; } void find_nearest_point(const int* set, const int key, const int start, const int end, int* local_minimum_difference, int* local_minimum_count) { // find nearest point using binary search int left = start; int right = end; int mid = 0; int tmp[3] = {0, }; int i; if (left > right) { return; } // binary search to find the nearest number(s) while (left <= right) { mid = (left + right) / 2; if (set[mid] == key) { break; } if (key < set[mid]) { right = mid - 1; continue; } if (key > set[mid]) { left = mid + 1; continue; } } // get differences between key and [mid-1, mid, mid+1] // the difference is '-1' when mid-1 (or mid+1) is out of range tmp[0] = (mid - 1 >= start) ? abs(key - set[mid - 1] ) : -1; tmp[1] = abs(key - set[mid]); tmp[2] = (mid + 1 <= end) ? abs(key - set[mid + 1] ) : -1; // if there is a key value in 'set' if (set[mid] == key) { *local_minimum_difference = tmp[1]; *local_minimum_count = 1; return; } // now we need to check [mid-1] and [mid+1] unless there is a key value in 'set' *local_minimum_difference = tmp[1]; *local_minimum_count = 0; for (i=0; i<3; i++) { // find the smallest difference if (tmp[i] != -1 && tmp[i] < *local_minimum_difference) { *local_minimum_difference = tmp[i]; } } for (i=0; i<3; i++) { // count the number of nearest points if (tmp[i] == *local_minimum_difference) { (*local_minimum_count)++; } } } int compare(const void* value0, const void* value1) { return *(int*)value0 - *(int*)value1; }입력 파일입니다.
출력 결과입니다.
감사합니다. 이렇게도 줄일수가 있네요. O(N)으로
감사합니다. 이렇게도 줄일수가 있네요.
O(N)으로 친구가 대회때 줄였다는데; 세상엔 참 여러가지 솔루션들이 많은 것 같습니다.
오늘도 달린다. :)
정렬 안 된 입력을 가지고 O(N)인가요? 우와~
정렬 안 된 입력을 가지고 O(N)인가요? 우와~
$PWD `date`
정렬시키고 O(N)인거 같습니다 -; 착각을
정렬시키고 O(N)인거 같습니다 -; 착각을 불러일으키셨다면 죄송....
오늘도 달린다. :)
아.. 깜빡 잊고, 최종 해결법을 안올렸군요.
이 글을 잊고 있었네요.
정렬이 되어있다는 가정 아래 O(n) 에 해결되는 방법이 있습니다.
오래된 글이지만 왠지 풀다 만 것처럼 보여서 이제라도 답글을 답니다.
우선 처음 접근 방법은 제가 이전에 올린 O(n log n) 방법과 같구요. (이미 하나의 숫자가 결정되어 있다고 보고 그 숫자와 'c'의 차이에 가장 가까운 숫자 찾기)
다만 달라지는 건 binary search 부분입니다.
설명의 편의 상 변수 이름부터 정의하자면,
arr은 오름차순으로 정렬된 배열(arr[i]는 i 번째 값)
n은 배열의 크기,
배열 인덱스 시작은 0부터,
그리고 두 개의 수의 합이 K라는 수에 가장 가까워졌을 때의 거리를 d라고 합니다.
그리고 두 개의 인덱스(i, j)가 필요한데요.
i는 정렬된 배열을 오름차순으로 순행하고,
j는 정렬된 배열을 내림차순으로 순행합니다.
즉, i 는 0에서부터 j-1까지 증가하고
j는 n-1에서 i+1까지 감소합니다.
수정된 O(n) 알고리즘의 의사 코드는 다음과 같습니다.
j = q-1 for i = 0...j-1 // 두 개의 숫자 중에 첫 번째 수는 이미 결정되었다는 가정. tmp = c - arr[i] // c와 이미 결정된 첫 번째 수의 차이(이를 tmp 변수에 저장)에 가장 가까운 수가 두 번째 수가 된다. for j = j...i+1 // 이 반복이 실행될 때마다 j 는 q-1부터 시작할 필요가 없다. // arr가 정렬된 배열이기 때문에 i가 커지면 arr[i] 값도 커진다. 즉, tmp 값이 점점 작아진다. j는 최초 한번만 q-1로 초기화하고 계속 줄어들기만 한다. if tmp > arr[j] d = min( arr[j+1] - tmp, tmp - arr[j] ) // j+1이 배열의 범위를 넘어가는지 오류를 체크해줘야 합니다만.. 코드 간결성을 위해서 스킵~ ㅎㅎ break end end end위의 코드에선 이중 for 문을 쓰지만 결국 반복 횟수는 n이 됩니다. (i 는 0에서 j-1까지 증가하고 j 는 n-1에서 i+1 까지 감소하니까요.)
최종 d의 값은 배열에서 두 수의 합이 K가 가장 가까울 때의 그 차이(거리)가 됩니다.
이전에 올린 O(n log n) 에서 조금만 더 생각하면 금방 떠올랐을 방법인데 제가 생각을 못했네요.
그래서 제 연구실 옆 연구실의 연구원이 ACM 관계자라서 그분께서 제가 이전에 올린 O(n log n) 알고리즘이 이렇게 O(n) 이 될 수 있다는 걸 알려주셨습니다. (감사합니다.)
예를 들어 설명하자면, (q, c) = (4, 10) 라고 하고 입력 값이 다음과 같습니다.
4 10
1 2 5 7
가방싸기 문제인가 싶었는데 "숫자 셋에서 각 2개를
가방싸기 문제인가 싶었는데 "숫자 셋에서 각 2개를 선택하고" 문구 때문에 polynomial 시간에 해결이 가능해지네요. 전산 필수 전공과목 숙제로 딱 좋은 문제군요:-)
글 올리신 분께 왠지 힌트는 드리면 안될 것 같고... 목표를 드리자면, O(n * log n)에도 해결이 가능합니다.
$PWD `date`
ACM-ICPC 대전지역 예선문제였습니다 ㅎㅎ
힌트 감사합니다.
오늘도 달린다. :)
댓글 달기