Problem

https://www.acmicpc.net/problem/10211

Summary

연속한 수열에서 최대 합을 찾는 문제 1 <= N <= 1000, -1000 <= arr[i] <= 1000

Idea

d[n] = max(d[n], d[n-1] + arr[n])

복잡도: O(n)

대략적으로 존재하는 부분 문제의 수 x 한 부분 문제를 풀 때 필요한 반복문의 수행 횟수

부분집합의 합

03 Sep 2016

Creating all possible k combinations of n items in Java

private static void combination(ArrayList<Integer> list, int n, int k) {
    if (k == 0) {
        System.out.println(list);
        return;
    }
    int smallest = list.isEmpty() ? 0 : list.get(list.size() - 1) + 1;
    for (int i = smallest; i < n; i++) {
        list.add(i);
        comb(list, n, k - 1);
        list.remove(list.size() - 1);
    }
}

Similarly, there is a algorithm to generate all possible permutations of a list.

private static void permutaion(ArrayList<Integer> list, int n) {
    if (list.size() == n) {
        System.out.println(list);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (visited[i] == false) {
            visited[i] = true;
            list.add(i);
            permu(list, n);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }
}

사전

https://www.acmicpc.net/problem/1256

연구소

https://www.acmicpc.net/problem/14502

30 Aug 2016

a+b+c=n 조건을 만족하는 경우의 수

void f(int a1, int a2, int a3) {
  // base
  if (a1+a2+a3 == n) {
      if (visited[a1][a2][a3] == 0) {
          //solution++;
      }
      visited[a1][a2][a3] = 1;
      return;
  }
  f(a1+1, a2, a3);
  f(a1, a2+1, a3);
  f(a1, a2, a3+1);
}

좀더 일반화를 해보자.

a+b+c=3 일 경우, 마지막 c는 a,b가 정해지면 알 수 있다.

a+b=3, a+b=2, a+b=1, a+b=0

a+b=3 은 다시

a=3, a=2, a=1, a=0 으로 분류

a1+a2+a3 …+ ak = n일 때 ( 0 <= ak <= n)

int f(int n, int k) {
    // base
    if (k == 1) {
        return 1;
    }
    int solution = 0;
    for (int i = 0; i <= n; i++) {
        solution += f(n-i, k-1);
    }
    return solution;
}

15 Aug 2016

A Full and Comprehensive Style Test

Test post for style

style

Below is just about everything you’ll need to style in the theme. Check the source code to see the many embedded elements within paragraphs.

1. Header

Header 1

Header 2

Header 3

Header 4

Header 5

Header 6

1-1. Header Alignment

Left(Default)

Center

Right

2. Body Text

Lorem ipsum dolor sit amet, test link adipiscing elit. This is strong. Nullam dignissim convallis est. Quisque aliquam. This is emphasized. Donec faucibus. Nunc iaculis suscipit dui. 5³ = 125. Water is H₂O. Nam sit amet sem. Aliquam libero nisi, imperdiet at, tincidunt nec, gravida vehicula, nisl. Underline. Maecenas ornare tortor. Donec sed tellus eget COPY filename sapien fringilla nonummy. Mauris a ante. Suspendisse quam sem, consequat at, ~~Dinner’s at 5:00.~~ commodo vitae, feugiat in, nunc. Morbi imperdiet augue mark element quis tellus.

3. Images

Large example image Medium example image Small example image

3-1. Image Alignment

Center example image

4. Blockquotes

Lorem ipsum dolor sit amet, test link adipiscing elit. Nullam dignissim convallis est. Quisque aliquam.

5. List Types

Unordered List

Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Nam ultrices nunc in nisi pellentesque ultricies. Cras scelerisque ipsum in ante laoreet viverra. Pellentesque eget quam et augue molestie tincidunt ac ut ex. Sed quis velit vulputate, rutrum nisl sit amet, molestie neque. Vivamus sed augue at turpis suscipit fringilla.
Integer pretium nisl vitae justo aliquam, at varius nisi blandit.
1. Nunc vehicula nulla ac odio gravida vestibulum sed nec mauris.
2. Duis at diam eget arcu dapibus consequat.
Etiam vel elit in purus iaculis pretium.

Ordered List

Quisque ullamcorper leo non ex pretium, in fermentum libero imperdiet.
Donec eu nulla euismod, rhoncus ipsum nec, faucibus elit.
Nam blandit purus gravida, accumsan sem in, lacinia orci.
- Duis congue dui nec nisi posuere, at luctus velit semper.
- Suspendisse in lorem id lacus elementum pretium nec vel nibh.
Aliquam eget ipsum laoreet, maximus risus vitae, iaculis leo.

Definition Lists

kramdown: A Markdown-superset converter
Maruku: Another Markdown-superset converter

6. Tables

Header1	Header2	Header3
cell1	cell2	cell3
cell4	cell5	cell6
cell1	cell2	cell3
cell4	cell5	cell6
Foot1	Foot2	Foot3

7. Code Snippets

Highlighted Code Blocks

#container {
  float: left;
  margin: 0 -240px 0 0;
  width: 100%;
}

Standard code block

<div id="awesome">
  <p>This is great isn't it?</p>
</div>

01 Jan 2016

DP is....what the

다 해보는 타입

어떤게 최적인지 모를 때

1로 만들기 f(n): n을 세가지 연산(%3, %2, -1) 으로 1을 만드는 최소 횟수 큰수로 먼저 나누는게 이득인지 알 수 없다 f(n) = min(f(n%3) + 1, f(n%2) + 1, f(n-1) + 1)
동전교환 f(k): k을 만들기 위한 동전 n개의 최소개수

큰수로 먼저 빼는게 이득인지 알 수 없다

f(k) = f(k - coins[i]) + 1

붕어빵 판매하기 오르막 수 붕어빵 판매하기

제곱 수의 합 f(n): n을 만드는 1 ~ n 까지의 각 제곱수들의 합의 최소 연산 수