코딩테스트 - 1

총 6문제 중에 3문제는 풀었다라고 말할 수 있고, 1문제는 이론적으로는 이해 했지만, 결과가 잘 나오지 않았고 마지막 2문제는 시간이 없어서 풀지를 못했다. 백준 스타일의 문제보다는 학교 과제 스타일의 문제 여서 이해하는데는 문제가 없었다.

Test 1

첫번째 문제는 Matrix Multiplication optimization 문제였다. OpenCV에 있는 library와 비교해서 더 빠른 matrix multiplication function을 만드는 거다.

OpenCV에 있는 Matrix Multiplication library는 찾아보니, for loop을 두번써서 모든 어레이를 다 traverse한다. Brute force하게 답을 찾는 거 같은데, Dynamic Programming으로 답을 찾을 수 있지않을까라는 생각만 하고 다른 문제로 넘어가서 실제로 풀지는 못했다.

Test 2

Array의 값들의 연속적인 합이 최대인 구간과 합을 구하는 알고리즘 문제였다. Maximum subarray problem이라고 leetcode에서 봤던 기억이 있지만 우선 제일 첫 번째로 생각난건 brute force 방식이 었다. for문을 두번 써서, 모든 subarray의 조합의 합을 구해서 다 비교하는 방식이다.

    int A[] = {12, -2, -24, 20, -2, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int B[] = {2, 2, -5, 4, 0};

    int final_max = -1;
    int max_up_til_now = 0;
    int initial_index = 0;
    int s = 0;
    int final_index;
    int n = (sizeof(A) / sizeof(A[0]));

    // Brute Force O(N^2)

    for(int i = 0; i<n; i++){
        max_up_til_now = 0;
        for(int j = i; j<n; j++){
            max_up_til_now += A[j];
            if(final_max < max_up_til_now){
                final_max = max_up_til_now;
                final_index = j;
                initial_index = i;
            }

        }
    }
    printf("Brute: max sum of contiguous subarray  = %d, from %dth index to %dth index.\n", final_max, initial_index, final_index);

합을 구한뒤, 합의 최대 값을 가지고 있는 final_max 와 비교 하여 값이 크다면, i (start index와) j (final index) 구간을 구해준다.

Brute force 방식은 제일 직관적이고 쉽게 생각할 수 있지만, 효율적이지는 않다. for문 두번을 써서 모든 조합을 찾는거니까.

두번째 방식은 Kaden's Algorithm(DP)이다. 쉽게 설명해서, 우선 current max에 인덱스의 값을 더한 다음, 0보다 작으면, 신경 쓰지 말고, 0 보다 크면 max와 비교한 다음, 합의 최대값을 확인한다. 이 경우 for문을 한번 써서 array를 한번만 traverse 해서 max subarray의 값을 얻을 수 있다.

그런데 이 경우 start 구간은 어떻게 얻을지 고민 해보았다. 마지막 구간은 max보다 더 큰 값이 들어왔을때의 i의 값이다. Start의 구간은 합의 값이 0보다 작을때 그 다음 인덱스를 임의 start로 정해주고, 0 보다 작은 값이 안 생길때 까지 계속 기록 해둔다.

  //Kadane's Algorithm O(N)
 for (int i = 0; i < n; i++)
    {
        max_up_til_now = max_up_til_now + A[i];

        if (max_up_til_now < 0)
        { //if value is negative, just make it zero
            max_up_til_now = 0;
            s = i + 1; //next ith value is our start point
        }
        else if (final_max < max_up_til_now)
        {
            final_max = max_up_til_now;
            initial_index = s;
            final_index = i;
        }
    }
 
    printf("Kadens :   Subarray of congiguous max = %d, from %dth index to %dth index.\n", final_max, initial_index, final_index);

마지막 해결 방벙은 Divide and conquer 방식인데, 쉽게 말해서 recursive하게 array를 반으로 쪼갠뒤, 다시 붙여가면서, 최대 합을 찾는 거다. 이 방식은 merge sort에서도 볼 수 있는 방식인데, 나는 솔직히 직관적이지 않아서 크게 좋아하지는 않는다.

int maximum(int a, int b, int c)
{
  if (a>=b && a>=c)
    return a;
  else if (b>=a && b>=c)
    return b;
  return c;
}

// function to find maximum sum of subarray crossing the middle element
int middle(int ar[], int low, int mid, int high)
{
  
  int left_sum = -9999;
  int sum = 0;
  int i;

 
  for (i=mid; i>=low; i--)
  {
    sum = sum+ar[i];
    if (sum>left_sum)
      left_sum = sum;
  }

  int right_sum = -9999;
  sum = 0;

  for (i=mid+1; i<=high; i++)
  {
    sum=sum+ar[i];
    if (sum>right_sum)
      right_sum = sum;
  }


  return (left_sum+right_sum);
}

// function to calculate the maximum subarray sum
int max_sum_subarray(int ar[], int low, int high)
{
  if (high == low) // only one element in an array
  {
    return ar[high];
  }

  // middle element of the array
  int mid = (high+low)/2;

  // maximum sum in the left subarray
  int maximum_sum_left_subarray = max_sum_subarray(ar, low, mid);
  
  // maximum sum in the right subarray
  int maximum_sum_right_subarray = max_sum_subarray(ar, mid+1, high);
 
  // maximum sum in the array containing the middle element
  int maximum_sum_crossing_subarray = middle(ar, low, mid, high);


  // returning the maximum among the above three numbers
  return maximum(maximum_sum_left_subarray, maximum_sum_right_subarray, maximum_sum_crossing_subarray);
}