개발자포럼 입니다.
알고리즘 잘 아시는 분계시나요?21
- [* 비회원 *]
- 등록일 2015-05-14 21:21
- 조회수 3821
|
||
0
추천하기
다른의견
0
|
파워링크 
등록안내
등록안내
|
 0
 0
input array size : 2n (n >=3)
인거죠? 전체 원소 다 더해서 /2 한값에 맞춰서 어레이 분할하면 되는거일테고. /2 값에 유사하도록 큰 원소부터 하나씩 빼서 각각 분할 어레이에 넣는식으로 가는게 정확하지만 시간이 조금 걸릴테고.. O(n) + O(nLog n) + O(n/2) 소요 시간은 이렇게 대충 나올거 같고.. 그게 아니라면 정렬 후 최소 최대 뽑아서 넣고 최소 최대 뽑아서 넣고 하면 오차율은 좀 늘어나지만 좀더 빠르겠네요. |
|
|
0
0
아리엘님
각각의 어레이에 있는 원소의 개수가 같아야 하나요?
어레이의 소의 개수가 같은경우 값들을 크기 별로 분류후 2개의 어레이에 가장 큰값과 2번재 큰값을 각각 추가. 두 어레이의 원소의 합의 크기를 비교하여 작은 어레이에 3번째 큰값을 큰 어레이에 4번째 큰값을 배열 다시 어레이의 원소의 합의 크기 비교후 위와 같은 작업을 반복. 어레의의 소의 개수가 다른 경우 먼저 값들을 크기 별로 분류를 합니다. 제일 작은 값 두개를 더합니다. 그리고 그값을 새로운 하나의 값으로 취급을 한다면 이제 2n개의 원소에서 2n-1개의 원소가 되었습니다. 다시 2n-1개의 원소에 대해서 이전과 같은 과정을 반복합니다. 그러면 결국 2n개의 원소가 결국 2의 원소만 남게 됩니다. 그 2개의 원소가 각각의 어레이의 합이 됩니다. 각각의 어레이를 구성하는 원소도 알아야 한다면 알고리즘이 좀 많이 복잡해지겠네요. 두가지 경우 모두 예외가 발생할수 있는지는 모르겠습니다. 예외가 발생하는 example 을 발견하면 댓글좀 달아주제요~ |
|
|
0
0
viper9
#include
#include #define MAX 10 void bubbleSort(int a[], int size) { int i, j, temp; for (i = size - 1; i>0; i--) { for (j = 1; j <= i; j++) { if (a[j - 1]<a[j]) { temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } } } } int main(void) { int arr_input[MAX] = { 100, 3,2,6,45,3,23,6,4,3}; int arr_a[MAX] = { 0, }; int arr_b[MAX] = { 0, }; int arr_a_last = 0; int arr_b_last = 0; int a = 0; int b = 0; /* srand(time(NULL)); for (int i = 0; i < MAX; ++i) { arr_input[i] = (rand() % 9) + 1; } */ bubbleSort(arr_input, MAX); for (int i = 0; i < MAX; ++i) { if (a <= b) { a += arr_input[i]; arr_a[arr_a_last] = arr_input[i]; // 확인용 ++arr_a_last; // 확인용 } else if (a > b) { b += arr_input[i]; arr_b[arr_b_last] = arr_input[i]; // 확인용 ++arr_b_last; // 확인용 } } std::cout << "1그룹의 합 : " << a << std::endl; std::cout << "2그룹의 합 : " << b << std::endl; std::cout << "그룹간 차 : " << a - b << std::endl; return 0; } 맞는지 모르겠지만 그냥 잠시 해봤네요. C++ 입니다. 1그룹과 2그룹간의 원소의 갯수가 같아야 한다는 조건이 없네요. (버블정렬 함수는 귀찮아서 걍 인터넷에서 퍼왔어요. -_-;;) |
|
|
0
0
 넌나에게목욕감을줬어
S사 다니시는군요...ㅎㅎ
Advanced 나오시길 바랍니다ㅎ |
|
|
0
0
뿡뿡이뿡뽕의뽕뽕
import java.util.ArrayList;
import java.util.Collections; import java.util.List; import java.util.Random; public class NumberSplite { private static final int LIMIT_NUMBER = 10; private List private List private int firstSum = 0; private int secondSum = 0; public static void main(String[] args) { NumberSplite spliteTest = new NumberSplite(); // List // List List System.out.println("정렬 전 숫자:" + list); Collections.sort(list); Collections.reverse(list); System.out.println("정렬 후 숫자:" + list.toString()); spliteTest.calc(list); } private void calc(List if(list == null || list.size() == 0){ System.out.println("첫번째그룹" + firstGroup.toString()); System.out.println("두번째그룹" + secondGroup.toString()); System.out.println("첫번째그룹합=" + firstSum); System.out.println("두번째그룹합=" + secondSum); return; } Integer max = list.remove(0); if(firstSum < secondSum){ firstGroup.add(max); firstSum += max; }else{ secondGroup.add(max); secondSum += max; } calc(list); } public List<Integer> createNumberArray(){ List for(int i = 0 ; i < 10 ; i++){ data.add(new Random().nextInt(LIMIT_NUMBER)); } return data; } } 좀전에 보고 짜봤는데, 맞는지는 모르겠네요. |
|
| 1 2 |
|
|
 |
|
| △ 이전글▽ 다음글 | 목록보기 |
|
우선 array.sort를 하고 array의 개수가 2n이라면 a[0]+a[2n-1] 과 a[1]+a[2n-2]의 값을 비교한 후 각각 다른 행렬에 넣습니다.
다음 cycle에서 a[2]+a[2n-3]과 a[3]+a[2n-4]를 비교하고 아까 비교했던 값 중 큰 쪽에 지금 비교한 값 중 작은 값을 더합니다..
이렇게 하면 될 것 같긴 한데 시간 안에 결과를 내 줄지 모르겠네요.
sort 한 후에 a[0]과 a[1]의 절대값 차이를 계산, a[2]와 a[3]의 절대값 차이를 계산 . 쭉쭉쭉.
그 차이값끼리 다시 비교해서 쭉쭉쭉.
그걸 계속 해서 한 값만 남을 때까지 하면 이게 두 합 사이의 차가 되지 않을까요.
최소합은 전체 합에서 이 차를 뺴준 후 2로 나누면 될 것 같은 느낌적 느낌.,.