[codility][python] max counter

codility max counter

https://app.codility.com/demo/results/trainingUBUCBJ-RVE/

def solution(N, A):
  res = [0] * N
  max_counter = 0

  for a in A:
    if a <= N:  # N카운터 존재
      res[a-1] +=1  # 카운터 올림
      if max_counter < res[a-1]: # max_counter 보다 크면 현재 카운터를 tmp_max로 변경
        max_counter = res[a-1] 
    else: # max counter 실행
      for i in enumerate(res):  # 전부 max_counter로 덮어씌운다.
        res[i] = max_counter
  return res

빅오노테이션이 O(MxN) 인 관계로 이중포문에서 하나를 없애야 한다.

# N 카운터가 있음. 0으로 세팅
# max counter : 모든 카운터들이 아무 카운터의 최대 값으로 세팅됨.

# A[K] = X 이면, K오퍼레이션은 X를 증가시킨다.
# -> 값이 X면 X를 증가시킴 (X범위 1<=X<=N)
# A[K] = N + 1 이면 K는 max counter  (??? K가 N보다 크면 max??)
# 아아아 max counter라는 걸 실행함!!!

def solution(N, A):
  res = [0] * N
  max_counter = 0
  tmp_max = 0
  for a in A:
    if a <= N:  # N카운터 존재
      if max_counter > res[a-1]:  # 1 max_counter가 더 크면 max_counter가 갱신된 것
        res[a-1] = max_counter  # 2 max_counter 값으로 변경해준다.
      res[a-1] +=1  # 3 그리고 그 다음에 카운터 시킨다
      if tmp_max < res[a-1]:  # 4 tmp_max보다 크면 현재 카운터를 tmp_max로 변경
        tmp_max = res[a-1]

    else:  # max_counter 에 현재 tmp_max를 넣는다. (max_counter는 그때그때 실행할 것이다.)
      max_counter = tmp_max

  # 아직 max_counter가 변경 된 이후에 counter가 변경된 이력이 없으면 max_counter로 덮어씌워준다.
  # 물론 max_counter보다 작은 경우.
  for idx, _ in enumerate(res):  
    if (res[idx] < max_counter):
      res[idx] = max_counter

  return res

a = [3,4,4,6,1,4,4]
N = 5

print(solution(5, a))

[hackerrank][python]Journey to the Moon

hackerrank: Journey to the Moon

1st attempt

# Determine how many pairs of astronauts from different countries they can choose from.
# UN 연합은 달에 사람들을 보내려고 한다.
# 그들은 이 사람들이 서로 다른 나라였으면 한다.
# 당신은 두 쌍의 우주조종사 id 리스트를 받을 것이다.
# 각 쌍은 같은 나라 우주조종사 id의 두 쌍으로 이루어져 있다.
# - 얼마나 많은 조종사 쌍을 만들 수 있는지 말해라.

# n : number of astronaut
# p : the number of pairs
from collections import defaultdict

# 일단 연결된 것들을 만든다.
def dfs(graph, start):
  visited, stack = set(), [start]
  while stack:
    v = stack.pop()
    visited.add(v)
    # 해당 정점에 연결된 것들을 stack에 넣는다.
    # 방문한 것은 제외
    stack.extend(graph[v] - visited)
  # 연결된 것들을 리턴.
  return visited

def journeyToMoon(n, ast_pairs):
  graph = defaultdict(set)
  asts = set()
  # 그래프 연결...
  for a1, a2 in ast_pairs:
    graph[a1].add(a2)
    graph[a2].add(a1)
    asts.add(a1)
    asts.add(a2)
  
  # 고립된 애들이 있을 수 있나? 일단 받아놔... (있는듯...)
  iso_asts = set([i for i in range(n)]) - asts
  
  groups = []  # divied by contry
  while asts:
    ast = asts.pop()
    connected_asts = dfs(graph, ast)
    groups.append(connected_asts)
    # 한번 방문한 팀은 다시 방문하지 않는다.
    asts = asts - connected_asts
  
  for i in iso_asts:
    groups.append({i})
  
  idx1, idx2 = 0, 1
  group_sum = 0
  while idx1 < len(groups)-1:
    idx2 = idx1 + 1
    while idx2 < len(groups):
      group_sum += len(groups[idx1]) * len(groups[idx2])
      idx2 += 1
    idx1 += 1
 
  return group_sum
    
  
n, p = list(map(int, input().strip().split(' ')))
ast_pairs = []
for _ in range(p):
   astronaut = [int(a) for a in input().strip().split(' ')]
   ast_pairs.append(astronaut)
   
result = journeyToMoon(n, ast_pairs)
print(result)

def dfs(graph, start):
  visited, stack = set(), [start]
  while stack:
    v = stack.pop()
    visited.add(v)
    stack.extend(graph[v] - visited)
  return visited

def journeyToMoon(n, ast_pairs):
  graph = defaultdict(set)
  asts = set()
  for a1, a2 in ast_pairs:
    graph[a1].add(a2)
    graph[a2].add(a1)
    asts.add(a1)
    asts.add(a2)
  
  iso_asts = set([i for i in range(n)]) - asts
  
  groups = []  # divied by contry
  while asts:
    ast = asts.pop()
    connected_asts = dfs(graph, ast)
    groups.append(connected_asts)
    # 한번 방문한 팀은 다시 방문하지 않는다.
    asts = asts - connected_asts
  
  for i in iso_asts:
    groups.append({i})
  
  # 뒤에 추가된 것들을 따로 분리해야 한다. 그래야 추가된 녀석들이 만드는
  # 패턴을 알 수 있다.
  # A*B + A*C + B*C -- A*B + A*C + B*C -- A*B + (A+B)*C 
  # A*B + A*C + A*D + B*C + B*D + C*D 
  # - A*B + (A+B)*C (A+B+C)*D
  # A*B + A*C + A*D + A*E + B*C + B*D + B*E + C*D + C*E + D*E
  # - A*B + (A+B)*C + (A+B+C)*D + (A+B+C+D)*E 
  idx1, idx2 = 0, 1
  group_sum = 0
  tmp_sum = 0
  while idx1 < len(groups):
    group_sum += tmp_sum*len(groups[idx1])
    tmp_sum += len(groups[idx1])

    # group_sum += tmp_sum*(len(groups[idx1 + 1]))
    idx1 += 1
  
  return group_sum
    
  
n, p = list(map(int, input().strip().split(' ')))
ast_pairs = []
for _ in range(p):
   astronaut = [int(a) for a in input().strip().split(' ')]
   ast_pairs.append(astronaut)
   
result = journeyToMoon(n, ast_pairs)
print(result)

동적설계법 배낭문제 - 2

package algorithm;

import java.util.Arrays;

public class Knapsack {

    static final int MAX_N = 100;
    static int[][] dp = new int[MAX_N][MAX_N];
    static int W;
    static int[] v;
    static int[] w;
    static int n;

    public static void main(String[] args) {

        n = 4;
        w = new int[] {2, 1, 3, 2};
        v = new int[] {3, 2, 4, 2};
        W = 5;
        // Arrays.fill(dp, -1);  error!
        for (int[] row : dp)
            Arrays.fill(row, -1);

        // int res = solve(0,W);
        // System.out.println(res);
        solve2();
    }

    private static int solve(int idx, int weight) {
        if (dp[idx][weight] >= 0) {
            return dp[idx][weight];
        }
        int res;
        if (idx == n) {
            res = 0;
        } else if ( weight < w[idx]) {  // skip
            res = solve(idx+1, weight);
        } else {  // 넣는 경우, 넣지 않는 경우.
            int a = solve(idx + 1, weight);
            int b = solve(idx + 1, weight - w[idx]) + v[idx];  // 이 경우에만 물건을 넣는 경우 v[idx]로 이때만 추가된다.
            res = Math.max(a, b);
        }

        return dp[idx][weight] = res;
    }

    private static void solve2() {  // i=idx, j=weight
        for (int[] row : dp)
            Arrays.fill(row, 0);  // -1이 아님을 주의. 캐시를 하는 것이 아니라. 전부 더할 것이다.

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= W; j++) {
                if (j < w[i]) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
                }
            }
        }

        for (int i = 0; i <= W; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(dp[0][W]);
    }
}

동적설계법 - 배낭문제 -1

package algorithm;

import java.util.Arrays;

public class Knapsack {

    static final int MAX_N = 100;
    static int[][] dp = new int[MAX_N][MAX_N];
    static int W;
    static int[] v;
    static int[] w;
    static int n;

    public static void main(String[] args) {

        n = 4;
        w = new int[] {2, 1, 3, 2};
        v = new int[] {3, 2, 4, 2};
        W = 5;
        // Arrays.fill(dp, -1);  error!
        for (int[] row : dp)
            Arrays.fill(row, -1);

        int res = solve(0,W);

        System.out.println(res);

    }

    private static int solve(int idx, int weight) {
        if (dp[idx][weight] >= 0) {
            return dp[idx][weight];
        }
        int res;
        if (idx == n) {
            res = 0;
        } else if ( weight < w[idx]) {  // skip
            res = solve(idx+1, weight);
        } else {  // 넣는 경우, 넣지 않는 경우.
            int a = solve(idx + 1, weight);
            int b = solve(idx + 1, weight - w[idx]) + v[idx];  // 이 경우에만 물건을 넣는 경우 v[idx]로 이때만 추가된다.
            res = Math.max(a, b);
        }

        return dp[idx][weight] = res;
    }
}

동적설계법 - 배낭문제 0

/**
동적설계법
01 배낭문제(Knapsack problem) - 0

n = 4
(w, v) = {(2,3),(1,2),(3,4),(2,2)}
W = 5
ouput : 7

유명한 배낭 문제이다. 일반적인 방법으로 각 물건에 대해 (넣는다/넣지않는다)로 두 가지 상태로 나눠서 탐색한다.

**/
import java.io.*;
import java.lang.*;
class Main {

  static int W;
  static int[] v;
  static int[] w;
  static int n;
  
  public static void main(String[] args) throws IOException {
    //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = 4;
    w = new int[] {2, 1, 3, 2};
    v = new int[] {3, 2, 4, 2};
    W = 5;

    int res = solve(0,W);
    System.out.println(res);
  }

  
  static int solve(int i, int W) {
    if (i == n) {
      return 0;
    } else if ( W < w[i]) {
      //skip
      return solve(i+1, W);
    } else {
      // 넣지 않는 경우, 넣는 경우 조사.
      int a = solve(i+1, W);
      int b = solve(i + 1, W - w[i]) + v[i];
      return Math.max(a, b);
    }

  }
}

부분집합 [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;
}

[java] 탐욕알고리즘 연습 - 3

// Fence Repair p.68
/**
널빤지 N개를 자르려고 한다. 필요한 길이는 L1, L2, L3는 배열로 주어진다.
널빤지 N개의 Ln의 길이로 자르려고 할 때 최소 비용을 구하라.
N = 3, L = {8,5,8}
21을 13 과 8로 자르는 비용은 21
13을 5, 8로 자르는 비용 13
총 비용은 34다

탐욕 알고리즘으로 풀 수 있다. 
- 가장 짧은 널빤지 노드와 그 다음으로 짧은 널빤지의 노드는 형제면 된다.

**/
import java.io.*;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int ans = 0, N = 3;
    int[] L = {8, 5, 8};

    // 널빤지가 1개가 될때까지 
    while (N > 1) {
      // 가장 짧은 널빤지 mil1, 다음으로 짧은 널빤지 mil2를 구함.
      int mil1 = 0, mil2 = 1;
      if (L[mil1] > L[mil2]) {
        int tmp = mil1;
        mil1 = mil2;
        mil2 = tmp;
      }

    //3번째 배열부터 또 mil1, mil2보다 작은 것들이 있는지 확인하고 있다면 위치를 갱신한다.
    for (int i = 2; i < N; i++) {
      if (L[i] < L[mil1]) {
        mil2 = mil1;
        mil1 = i;
      }
      else if (L[i] < L[mil2]) {
        mil2 = i;
      }
    }

    // L[mil1] + L[mil2] 병합 (제일 작은 서로를 합침)
    int t = L[mil1] + L[mil2];
    ans += t;
    bw.write("ans : " +  ans + "\n");
    if (mil1 == N - 1) {
      int tmp = mil1;
      mil1 = mil2;
      mil2 = tmp;
    }

    L[mil1] = t;  // mil1을 합친값을 넣어서 커지게 만든다. (합쳐졌으니.)
    L[mil2] = L[N-1];  // mil2는 가장 큰 값을 넣는다. (왜지??)
    N--;
    }

    bw.write("ans : " +  ans + "\n");
    bw.close();
    br.close();
}

탐욕알고리즘 - 2

// 구간 스케줄링 p.59
/**
  n개의 강의가 있다. 각 강의 시간은 si에서 ti까지다.
  가장 많은 강의에 참가하고 싶은 경우, 몇 개의 강의에 참가하는 것이 가능할까?

**/
import java.io.*;
// import java.util.TreeMap;
import java.util.*;

class Main {
  public static void main(String[] args) throws IOException {
    
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int MAX_N = 100000;  // 비교 최대값
    int N = 5;
    int[] S = {1,2,4,6,8};
    int[] T = {3,5,7,9,10};
    Map map = new TreeMap<>();

    for(int i = 0; i < N; i++) {
      map.put(T[i], S[i]); // 종료시간순으로 정렬한다.
    }

    int ans = 0;
    int t = 0;
    for (int i = 0; i < N; i++) {
      if (t < map.get(T[i])) {
        ans++;
        t = T[i];
        bw.write("선택한 강의 : " + (i+1) + "\n");
      }
    }

    bw.write("ans : " +  ans + "\n"); // 출력 3 (1, 3, 5 선택)
    bw.close();
    // br.close();
  }
  public static int min(int a, int b) {
    if (a > b) return b;
    else return a;
  }
}

탐욕알고리즘 - 1

// 코인문제 p.57
/**
  1, 5, 10, 50, 100, 500원짜리가 각각 C1, C5, C10, C50, C100, C500개씩 있다.
  A원을 지불하려면 몇 개의 동전이 있어야 할까. 지불 방법은 적어도 1개는 존재한다고 가정한다.
  **/
import java.io.*;

class Main {
  public static void main(String[] args) throws IOException {
    int ans = 0;
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final int[] V = {1,5,10,50,100,500};
    int[] C = {3,2,1,3,0,2};
    int A = 620;

    // 큰 것부터 넣는다. 탐욕알고리즘
    for (int i = 5; i >= 0; i--) {
      int t = min(A / V[i], C[i]); // 
      A -= t * V[i];
      ans += t;
    }
   
    bw.write("ans : " +  ans + "\n"); // 출력 6(500x1, 50x2, 5x2 합계 6개)
    bw.close();
    // br.close();
  }
  public static int min(int a, int b) {
    if (a > b) return b;
    else return a;
  }
}

[python][hackerrank] Repeated String

https://www.hackerrank.com/challenges/repeated-string/problem

strings = input()

# number_of_a = len(''.join(x for x in strings if x == 'a'))
number_of_a = strings.count('a')

n = int(input())

_div, _mod = divmod(n, len(strings))
res = _div * number_of_a

for s, m in zip(strings, range(_mod)):
  if s == 'a':
    res += 1
    
print(res)

조합/중복조합 [파이썬]

역시 파이썬이 더 재미있다.

def factorial(n):
  if n <= 1:
    return 1
  else:
    result = 1
    for i in range(2, n+1):
      result *= i
    return result

# nCk = n! / (n-k)! * k!
def comb_slow(n, k):
  return factorial(n) / (factorial(k)*factorial(n-k))
  
print(comb_slow(6,3))

def comb_fast(n, k):
  numerator = 1
  denominator = 1
  k = min(n-k, k)  # nCk에서 더 적은 수로 계산하기 위해서.
  den_list = []
  num_list = []
  for i in range(k):  # 기존 소스에서 이곳을 변경함.
    denominator *= i + 1
    numerator *= n-i
    den_list.append(i+1)
    num_list.append(n-i)
  print('den_list={}'.format('*'.join(str(x) for x in den_list)))
  print('num_list={}'.format('*'.join(str(x) for x in num_list)))
  
  return numerator/denominator
  
print(comb_fast(6,3))

# 번외 중복조합
# nHr = n+r-1Cr
def ham(n, k):
  return comb_fast(n+k-1, k)
  
print(ham(6, 3))

# 참고문헌 : https://smlee729.github.io/python/algorithm/2015/03/08/1-nchoosek.html

최대 이익 투자 [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;
}

factorial 두가지 방법 [C 언어]

#include 

int factorial(int n)
{
  int res, i;
  
  res = 1;
  for(i = 2; i <= n; i++) {
    res *= i;
  }
  return res;
}

int factorial2(int n)
{
  if (n == 1)
    return 1;
    
  return n * factorial2(n - 1);
}

int main(void) {
  printf("Hello World\n");
  printf("%d\n", factorial(5));
  printf("%d\n", factorial2(5));
  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)