부분집합 [C언어]

문제로 풀어보는 알고리즘.

// 부분집합
#include 

void print_arr(int arr[], int arr_len)
{
  int i;
  for (i = 0; i < arr_len; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

/*
부분집합 공식
P(A) = (e*P(A')) U P(A')
e를 포함한 A' 와 e를 포함하지 않는 A'의 합집합
A'는 A' = A - {e} 라고 A에서 집합 {e}를 뺀 것.
그렇지만 코드가 좀 이해가 안된다.
*/
void subset(int set[], int set_size, int n, int index)
{
  if (index == n) {
    print_arr(set, set_size);
    return;
  }
  /*
  set[set_size]가 계속 변경됨.
  index가 올라감에 따라 set[set_size]의 기존 집합이 덮어씌워진다.
  ex) 
  set = [0 1 2] 에서 index가 오르면서
  set = [0 1]
  set = [0 2]
  뭐 이런식으로... 다른 언어였으면 그냥 set같은 걸 사용하면
  좋을 것 같다.
  */
  set[set_size] = index;  // set[size_size]로 집합을 흉내.
  subset(set, set_size+1, n, index+1);  // index(e) 포함한 경우.
  subset(set, set_size, n, index+1);  // index(e)를 포함안한 경우.
}

#define N 100
int main() {
  int set[N], n;
  printf("input n : ");
  scanf("%d", &n);
  subset(set, 0, n, 0);
  return 0;
}

최대 이익 투자 [C언어]

출처 : 문제로 풀어보는 알고리즘

#include 
/*
최대이익투자 : 문제로 풀어보는 알고리즘

4 3  투자금액, 투자 가능 기업의 수
2 3 1  기업별 1만원 투자시 이익
4 5 3  기업별 2만원
7 6 7  기업별 3만원
9 8 9  기업별 4만원

return 10 : 최대이익.
4 3
2 3 1
4 5 3
7 6 7
9 8 9
*/

#define M 100
#define N 100

int r[M][N];
int max_return[M][N];

void calculate_return(int n, int m)
{
  int i, j, k, max, t;

  // dynamic programming을 위해 미리 첫번재 기업을 세팅을 한다. (처음이니까 무조건 max)  
  for (i = 0; i <= m; i++)  {
    // 맨 윗줄.
    max_return[0][i] = r[0][i];
  }
  
  for (i = 0; i < n; i++) {
    for (j = 0; j < m+1; j++) {
      printf("%d ", r[i][j]);
    }
    printf("\n");
    
  }
  
  
  // 두번째줄부터 시작함.
  for (i = 1; i < n; i++)  // i는 기업.
    for (j = 1; j < m+1; j++) {  
    // j는 총 투자할 양 m+1인 이유는 m=0인 경우(투자안한경우)도 다뤄야 하기 때문.
    // 기업의 수(i) 투자할 양(j)를 작은 수로 시작해서 기록-> 큰 수로 간다.
      max = -1;
      for (k = 0; k <= j; k++) {  
// 이전에 투자한 회사와 액수에 대한 내용을 바탕으로 더한다.
// t = 이전 회사에 k를 투자한양과 지금 회사에 j에서 k만큼 이전회사에 투자한 양을 뺀 경우.
// 왜 계속 이전회사만하고만 비교를 하냐면 동적프로그래밍으로 계속 그 최대값이 각 배열마다 누적될 것이다. 
// 그러니 이전 내용과는 비교할 이유가 없다.
        t = max_return[i-1][k] + r[i][j - k];  // 무조건 왼쪽 + 위쪽인데.
        //printf("i=%d, j=%d, k=%d t: %d\n", i,j,k,t);
        if (t > max)
          max = t;
      }
      max_return[i][j] = max;
    }
    

}

int main(void) {
  int m, n, i, j;
  
  scanf("%d %d", &n, &m);
  for (i = 0; i < n; i++)
    r[i][0] = 0;

  for (i = 1; i <= m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &r[j][i]); // 정보를 받아온다.
      
  calculate_return(n, m);
  printf("Max return: %d\n", max_return[n-1][m]);
  return 0;
}

무게가 있는 길찾기 [C 언어]

#include 

#define M 100
#define N 100

int map[M][N];

int max(int x, int y)
{
  if (x > y)
    return x;
  return y;
}

int max_joy(int m, int n)
{
  if (m == 0 && n == 0) {
    return map[0][0];
  }
  // 맨 위인경우.
  if (m == 0) {
    return max_joy(m, n-1) + map[m][n];
  }
  // 맨 왼쪽인경우.
  if (n == 0) {
    return max_joy(m-1, n) + map[m][n];
  }
  // 위,왼 중에 max를 골라서 더함.
  return max(max_joy(m-1, n), max_joy(m, n-1)) + map[m][n];
}

int joy[M][N];
void dynamic_joy(int m, int n)
{
  int i, j;
  
  joy[0][0] = map[0][0]; // 0,0 처음세팅.
  // 맨위,맨왼 세팅
  for (i = 1; i < m; ++i) {
    joy[i][0] = joy[i-1][0] + map[i][0];
  }
  for (j = 1; j < n; ++j) {
    joy[0][j] = joy[0][j-1] + map[0][j];
  }
  
  // 그 사이들 세팅.
  for (i = 1; i < m; ++i)
    for (j = 1; j < n; ++j)
      joy[i][j] = max(joy[i-1][j], joy[i][j-1]) + map[i][j];
}

/*
5 5
1 2 2 1 5
1 4 4 3 1
2 1 1 1 2
1 3 5 1 1
1 5 1 2 2
*/
int main() {
  int m, n, i, j;
  
  scanf("%d %d", &m, &n);
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++)
      scanf("%d", &map[i][j]);
  printf("%d\n", max_joy(m-1, n-1));
  
  dynamic_joy(m, n);
  
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++)
      printf("%d ", joy[i][j]);
    printf("\n");
  }
  return 0;
}

동적프로그래밍 길찾기 [C 언어]

#include 

#define M 100
#define N 100

int map[M][N];

long long num_path(int m, int n)
{
  // 장애물이면 0
  if (map[m][n] == 0) {
    return 0;
  }
  // m=i,n=j에서 0,0으로 갔으면 +1
  if (m == 0 && n == 0) {
    return 1;
  }
  
  return ((m > 0) ? num_path(m - 1, n) : 0)
    + ((n > 0) ? num_path(m, n - 1) : 0);
}

// 와... 값을 리턴하는 것이 아닌 map에 값을 넣는다.
long long path[M][N];
void dynamic_programming_path(int m, int n)
{
  int i, j;  // 이중포문용
  path[0][0] = map[0][0];
  
  
  // 1. 세로 맨 왼쪽은 왼쪽을 더할필요가 없음.
  for(i = 1; i < m; ++i) { //i=0 : path[-1][0]이 없기 때문에 스킵
    if (map[i][0] == 0) {
      path[i][0] = 0;
    } else {
      path[i][0] = path[i-1][0];  // 2. 여기 path[i][0-1]
    }
  }
  // 2. 가로 맨 왼쪽은 위쪽을 더할 필요가 없음.
  for(j = 1; j < n; ++j) { // j=0 은 path[0][-1]가 없기 때문에 스킵
    if (map[0][j] == 0) {
      path[0][j] = 0;
    } else {
      path[0][j] = path[0][j-1]; // 2. 여기 path[0-1][j]
    }
  }

  for (i = 1; i < m; i++) {
    for (j = 1; j < n; j++) {
      if (map[i][j] == 0) {
        path[i][j] = 0;
      } else {
        // 동적프로그래밍 한칸 한칸 나아간다.
        path[i][j] = path[i-1][j] + path[i][j-1];
      }
    }
  }
}


/*
5 5
1 1 1 1 1
1 1 0 0 1
1 1 1 1 1
1 1 1 0 1
0 0 1 1 1
*/
int main(void) {
  int m, n, i, j;

  scanf("%d %d", &m, &n);
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      scanf("%d", &map[i][j]);
    }
  }
  // 반대로 가는듯.
  // printf("%lld\n", num_path(m-1, n-1));
  dynamic_programming_path(m, n);

  return 0;
}

출처: 문제로 풀어보는 알고리즘

수 분할 [C 언어]

#include 
// 수분할

// partition(0, m) =1 
// partition(n,m) = i~m partition(n-i,i)
int partition(int n, int m)
{
  int count = 0, i;
  
  // n/m 수분할은 n/n 수문할과 같으므로 m에 n을 대입한다.
  // 5를 6까지 이용해서 분할할 수는 없으니까
  if (n < m) {
    // printf("n=%d, m=%d\n", n, m);
    m = n;
  }
  if (n == 0) // Base Case 0
    return 1;

  for (i = 1; i <= m; i++) {
    // printf("call partition(%d, %d);\n", n-i, i);
    count += partition(n - i, i);
  }
  return count;
}

#define MAX 1000
int partition_cache(int n, int m)
{
  static int cache[MAX][MAX];
  int count = 0, i;
  
  if (n < m) {
    m = n;
  }
  if (cache[n][m]) {
    return cache[n][m];
  }
  if (n == 0) {
    return cache[n][m] = 1;
  }
  
  for (i = 1; i <= m; i++) {
    count += partition_cache(n - i, i);
  }
  
  return cache[n][m] = count;
}

int main(void) {
  // printf("first %d\n", partition(1000,4));
  printf("second %d\n",  partition_cache(1000, 4));
  return 0;
}

금액계산 경우의 수 [C 언어]

#include 
// 금액 맞추기
// 브루트포스 / 재귀
// 일정금액을 1,2,5,10,20,50 만원으로 계산 가능 가짓수.


void brute(int* bills, int money) {
  int i0, i1, i2, i3, i4; // 각 계산 후 남은 수.
  int count = 0;
  for (i0 = money; i0 >= 0; i0 -=bills[0])
    for (i1 = i0; i1 >= 0; i1 -= bills[1])
      for (i2 = i1; i2 >= 0; i2 -= bills[2])
        for (i3 = i2; i3 >= 0; i3 -= bills[3])
          for (i4 = i3; i4 >= 0; i4 -= bills[4])
            if (i4 % bills[5] == 0)
              count++;
              
  printf("count = %d\n", count);
}

int better(int* bills, int n, int money)
{
  int count = 0, i;
  
  if (n == 1) {
    if (money % bills[0] == 0)
      return 1;
    else
      return 0;
  }

  int len = money / bills[n-1];
  for (i = 0; i <= len; i++) {
    count += better(bills, n-1, money - (bills[n-1] * i));
  }
  
  return count;
}

int main(void) {
  int bills[6] = {1,2,5,10,20,50};
  int money = 100; // res = 4562
  int numberOfBills = 6;
  
  brute(bills, money); 
  // printf("better way : %d\n", better(bills, numberOfBills, money));
  
  return 0;
}

[fibonacci] 피보나치 [C 언어]

피보나치 지긋지긋하다.

#include 
#include 
// 피보나치 수열

long long fibo(int n)
{
  if (n == 1 || n == 2) {
    return 1;
  }
  
  return fibo(n-1) + fibo(n-2);
}

// cache
#define MAXSIZE 100
long long fibo2(int n) {
  static long long cache[MAXSIZE];
  
  if (cache[n])
    return cache[n];
    
  if (n == 1 || n == 2)
    // cache[n] = 1;
    return cache[n] = 1;
    
  // cache[n] = fibo2(n-1) + fibo2(n-2);
  return cache[n] = fibo2(n-1) + fibo2(n-2);
}

// 재귀 없이 풀기
long long fibo3(int n) {
  int i;
  long long f_res, f_a, f_b;
  
  if (n == 1 || n == 2)
    return 1;

  // f(3) = f(2) + f(1);
  // f(n) = f(n-1) + f(n-2)
  f_a = 1;
  f_b = 1;
  for (i = 3; i <= n; ++i) {
    f_res = f_a + f_b;
    f_a = f_b;
    f_b = f_res;
  }
  
  return f_res;
}


int main(void) {
  printf("Hello World\n");
  // printf("%lld\n", fibo(100)); 
  printf("%lld\n", fibo2(100));
  printf("%lld\n", fibo3(100)); 
  return 0;
}

[binomial_coefficient] 이항계수 [C 언어]

// 이항계수
#include 

// nCr = n-1Cr-1 + n-1Cr
long long binomial_coefficient(int n, int r)
{
  if (r == 0 || r == n)
    return 1;
    
  return binomial_coefficient(n-1, r-1) + binomial_coefficient(n-1, r);
}

#define MAX_SIZE 100
// cache
long long binomial_coefficient2(int n, int r)
{
  static long long cache[MAX_SIZE][MAX_SIZE] = { 0, };
  
  if (cache[n][r]) {
    return cache[n][r];
  }
  
  if (r == 0 || r == n)
    return 1;
    
  cache[n][r] = binomial_coefficient2(n-1, r-1) + binomial_coefficient2(n-1, r);
  return cache[n][r];
}
int main(void) {
  printf("Hello World\n");
  //printf("%lld\n", binomial_coefficient(100,52)); // 5C2
  printf("%lld\n", binomial_coefficient2(100,52)); // 5C2
  return 0;
}

[largorithm][mergesort] 머지소트 (C / Python)

C Language

main.c

#include 
#include 
#include "mergesort.h"

void printArray(int value[], int count);

int main()
{
    int values[] = { 80, 75, 10, 60, 15, 49, 12, 25 };
    int count = sizeof(values)/sizeof(int);

    mergesort(values, count);
    printArray(values, count);
    return 0;
}


void printArray(int value[], int count)
{
    int i = 0;
    for(i = 0; i < count; i++) {
        printf("%d ", value[i]);
    }
    printf("\n");
}

mergesort.h

#ifndef MERGESORT_H_INCLUDED
#define MERGESORT_H_INCLUDED

void mergesort(int* arr, int count);

#endif // MERGESORT_H_INCLUDED

mergesort_impl.c

#include 
#include 

#include "mergesort.h"

void _mergesort(int* arr, int* pBuffer, int start, int end);
void _mergesort_division(int* arr, int* pBuffer, int start, int middle, int end);

void mergesort(int* arr, int count)
{
    int* pBuffer = (int*)malloc(sizeof(int) * count);
    if(pBuffer != NULL)
    {
        _mergesort(arr, pBuffer, 0, 7);

        free(pBuffer);
    }
}

void _mergesort(int* arr, int* pBuffer, int start, int end)
{
    int middle = 0;
    if (start < end)
    {
        middle = (start + end) / 2;
        _mergesort(arr, pBuffer, start, middle);
        _mergesort(arr, pBuffer, middle+1, end);
        _mergesort_division(arr, pBuffer, start, middle, end);
    }
}

void _mergesort_division(int* arr, int* pBuffer, int start, int middle, int end)
{
    int i = 0, j = 0, k = 0, t = 0;
    i = start;
    j = middle + 1;
    k = start;

    while(i <= middle && j <= end)
    {
        if(arr[i] <= arr[j])
        {
            pBuffer[k] = arr[i];
            i++;
        }
        else
        {
            pBuffer[k] = arr[j];
            j++;
        }
        k++;
    }

    if(i <= middle)
    {
        for(t = i; t <= middle; t++, k++)
        {
           pBuffer[k] = arr[t];
        }
    }
    else
    {
        for(t = j; t <= end; t++, k++)
        {
            pBuffer[k] = arr[t];
        }
    }

    for (t = start; t <= end; t++)
    {
        arr[t] = pBuffer[t];
    }
}

Python

def merge_sort(arr):
    print('split', arr)
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        merge_sort(left)
        merge_sort(right)

        i, j, k = 0, 0, 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    print('merge', a)
a = [80, 75, 10, 60, 15, 49, 12, 25]
merge_sort(a)
print(a)