문제보기


11053 가장 긴 증가하는 부분수열


을 참고하면 된다.


달라진 것은 하나다. 


D[i] < D[j]+1

일때 +1 의 의미는 수열의 길이가 1증가 한다는 것이다. 

여기서 +1 -> A[i]로 바꿔준다면 값들을 더하면서 증가하는 수열이 될것이다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package Problems;
 
/**
 * 
 * 백준 11055 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11055dp {
    public static int n, arr[], d[];
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
        
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = arr[i];
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] +arr[i]) {
 
                    d[i] = d[j] + arr[i];
 
                }
            }
 
 
        }
        
        int max = d[0];
        
        for(int i = 0; i < n; i++) {
            if(max < d[i]) {
                max = d[i];
            }
        }
        
        System.out.println(max);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03

문제보기


부분수열 문제이다. 


그리고 동적계획법이지만 이것은 LIS풀이가 적용되었다. 

'수열 A가 주어졌을때, 가장 긴 증가하는 부분수열을 구하라'  이다.

즉, 수열마다 이게 몇번째 수열인지 최대값으로 체크한다. 

수열이 존재할때 각각의 위치의 해석은 

A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이이다.


조건은 이러하다


A[i]가 있을때, i 보다 작은 index들(ex. 0~j)의 값들을 A[i]와 비교한다. 그리고 A[i]가 A[j]가 '증가하는 수열'이므로 길이를 비교한다.

조건 : j<i , A[j] < A[i] 

또 하나의 조건이 더 있다. 만약 D[i]가 4인데, D[j]가 2이면 A[j]와 A[i]가 부분수열이여도 길이를 바꿔줄 필요가 없다. 

그래서 이러한 조건이 붙는다. 


D[i] < D[j]+1


끝이다. 코드를 보면 이해가 될 것이다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package Problems;
 
/**
 * 
 * 백준 11053 LIS
 * 
 * 
 */
 
import java.util.Scanner;
 
public class Boj11053dp {
    public static int n, arr[], d[], max = 0;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        n = in.nextInt();
 
        arr = new int[n];
        d = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
 
        for (int i = 0; i < n; i++) {
            d[i] = 1;
 
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && d[i] < d[j] + 1) {
 
                    d[i] = d[j] + 1;
 
                }
            }
 
            if (max < d[i]) {
 
                max = d[i];
            }
 
        }
        
        System.out.println(max);
 
    }
 
}
 
cs
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39



 

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03


문제보기


문제를 살펴보면 이러하다.


1. 한번에 1~2계단 갈 수 있다. 

2. 연속3개는 밟을 수 없다. 

3. 그리고 밟았을때, 포도주 문제와 달리 선택/미선택의 결정을 할 수 없다. 


경우를 나눠보자 


첫 번째, 1개 연속 밟았을 경우 

i 번째 일때 , i-1을 밟지 못한다. 그리고 i-2번째를 밟고 올라온다 

-- > D[i-2]+A[i]


두 번째, 2개 연속 밟았을 경우 

i번째 일때, i-1을 밟아야한다. 하지만 i-2번을 밟으면 규칙에 위배되므로 밟지 않는다. 

그리고 D[i-3]을 더한다.(여기는 뭘해도 상관없다. 규칙에 영향을 안받음)


점화식은 아래와 같다. 

 dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);

2차원 배열의 경우 점화식 : D[i][1] = Math.max(D[i-2][2],D[i-2][1])+A[i]

D[i][2] = D[i-1][1] + A[i]

Math.max(D[N][1],D[N][2])

<전체코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package Problems;
/**
 * 
 * 백준 2579 계단오르기 
 * 
 * 동적계획법 
 * 
 * 
 */
import java.util.Scanner;
public class Boj2579dp {
    public static int n,arr[],dp[];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        arr = new int[n+1];
        dp = new int[n+1];
        
        for(int i = 1; i <=n; i++) {
            
            arr[i] = in.nextInt();
        }
        
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        for(int i = 3; i <=n; i++) {
            
            dp[i] = Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
            
        }
        
        System.out.println(dp[n]);
    }
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02 
* 다시 풀어볼 : 파티 
* (26)추가 리스트 : 1916(Boj1916dij2) , 9465(Boj9464), 1261(Boj1261dp2) 
* (27)추가 리스트 : 1904(Boj1904dp2), 2139(Boj2139dp) ,2638(Boj2638dfs2)
* (28)추가 리스트 : 7576(Boj7576bfs2), 11403(Boj11403floyd2)
* (29)추가 리스트 : 2665(Boj2665dij)
* (29)추가 리스트 : 2156(Boj2156dp2), 1915(Boj1915dp2)
* <11월> 
* (01)추가 리스트 : 11051(Boj11051dp),2362(Boj2362dp2),1012(Boj1012dfs2)
* (02)추가 리스트 : 1699(Boj1699dp2), 1238(Boj1238dij2)
* (03)추가 리스트 : 9095, 1463, 11726, 11727

2017.11.03 ** 금요일 ** Solution - 1463(1로만들기)

풀이방법: 동적계획법

DP를 풀 수 있다면 쉬운문데 ,

우리는 1로 만들것이고

문제에서는 이미 3개의 케이스를 줬다.

N의 케이스를 나눠보자

3으로 나누면 N의 상태는 N/3이된다.

2로 나누면 N/2

1을 빼면 N-1

이렇게 3개를 나눠서 최소값을 찾으면 되는 문제이다.

점화식 : 

dp[1] = 0;

        for(int i = 2; i < N+1; i++) {

            dp[i] = dp[i-1] + 1;

            if(i%3==0&&dp[i] > dp[i/3]+1) {
                dp[i] = dp[i/3] + 1;
            }

            if(i%2==0&&dp[i]>dp[i/2]+1) {
                dp[i] = dp[i/2] + 1;
            }


        }

—————————————————————————————————————

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02
백준 11051 이항 계수2  (0) 2017.11.01 
* 다시 풀어볼 : 파티 
* (26)추가 리스트 : 1916(Boj1916dij2) , 9465(Boj9464), 1261(Boj1261dp2) 
* (27)추가 리스트 : 1904(Boj1904dp2), 2139(Boj2139dp) ,2638(Boj2638dfs2)
* (28)추가 리스트 : 7576(Boj7576bfs2), 11403(Boj11403floyd2)
* (29)추가 리스트 : 2665(Boj2665dij)
* (29)추가 리스트 : 2156(Boj2156dp2), 1915(Boj1915dp2)
* <11월> 
* (01)추가 리스트 : 11051(Boj11051dp),2362(Boj2362dp2),1012(Boj1012dfs2)
* (02)추가 리스트 : 1699(Boj1699dp2), 1238(Boj1238dij2)
* (03)추가 리스트 : 9095, 1463, 11726, 11727

2017.11.03 ** 금요일 ** Solution - 11726,11727 (2Xn타일링,2)

풀이방법: 동적계획법


개인적으로 처음에 해맷다 , 일단 그리는게 너무 싫다..

돌리고 돌리고, 이상한 그림도 나오고..

마음잡고 다시 풀었을때

추가되는 것에 집중해봤다.

예제로 2x4까지 그리면 충분히 규칙을 찾을 수 있다.


타일의 종류는 2개가 있다.

그리고 이것을 마지막에 배치할때 두 가지 방법이 있다.

마지막에 일단 배치시켜보자

앞에는 2x(N-1) , 2x(N-2) 구역만 챙기면 된다.

즉, n-1 번째에는 1x2가 하나씩 더 붙는거고

n-2번째에는 2*1이 두개가 붙는다.


끝이다. 

    dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n+1; i++) {

        dp[i] = dp[i-1] + dp[i-2];
        dp[i] %= 10007;

        }


—————————————————————————————————————


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02
백준 11051 이항 계수2  (0) 2017.11.01
백준 1915 가장 큰 정사각형  (0) 2017.11.01

2017.11.02 ** 목요일 ** Solution - 1238(파티)
백준 1238 파티

풀이방법: 다익스트라

특정한 장소에 최단시간으로 모두 갔다오고, 그 중 가장 오랜시간 걸린 사람을 찾는 문제이다.

풀이방식

문제를 읽고 두 가지 풀이가 생각났다.

1.플로이드
2.다익스트라

처음에는 플로이드로 하면 금방할 것 같아 했는데 , 뭔가 오류가난다. 시간이 초과되고 그러는것 같다.

그래서 플로이드의 조건을 바꾸느냐? 아니면 다익스트라로 다시푸느냐...

다시하는게 빠를것 같아 다익스트라로 풀었다.

그냥 다익스타로 하기전에 고민을 좀 더 해봤다.

다시 생각해보면 우리는 X의 지점만 왓다리 갓다리 하면된다.

문제에서 보면 1 -> 2 가 4인데 이것을 뒤집으면 2 -> 1이된다. 보기에는 다르겠지만 의미는 같다.

따라서 두 가지의 방식을 사용하면된다.

일반적인 거리배열을 이용한것과 위처럼 뒤집은 배열을 사용한것 이 결과 두개를 더하면된다.

또한 우리는 기준이 되는 점을 알고 있기 때문에 기준점을 활용한다.

dist[i] = map{x}{i} + d[x]를 점화식으로 세운다.

나머지는 다른 다익스트라와 같다. (우선순위 큐쓰고,, 넣고 와일문 돌리고등.)

함수의 매개변수를 (int x, int{}{}map, int{} dist) 이렇게 받아주고 계산하면된다.(쓴 이유는 아래에 있다)

그리고 우리는 함수를 2번 호출한다. 왜냐하면 우리는 2개씩 배열을 만들것이기 떄문!

안뒤집은 배열, 뒤집은 배열, 안뒤집은 거리, 뒤집은 거리 이렇게 4개를 활용한ㄷ.

뒤집은 것을 넣게되면 아까 말한것처럼 1->2 를 2->1로 계산할 수 있다.

출력할때는

제일 큰 dist[i] + redist[i] 하면된다. 모두 x까지 왕복한 거리들이기 떄문이다.
코드 전체 보기

: 풀다가 잣다.. 어려웡.

'알고리즘(추가예정) > 다익스트라' 카테고리의 다른 글

백준 2665 미로만들기  (0) 2017.10.30

2017.11.02 ** 목요일 ** Solution - 1699(제곱수의 합)
백준 1699 제곱수의합

풀이방법: 동적계획법

엄청 시간이 걸렸던 문제다.

처음에 생각했던 것은 d[2-1] = d[1]+1.. 이런식으로 했었다.

그런데 여기서 4=2의 제곱이 되니 카운트가 바껴야 하는데 그 포인트를 못구했다.

그래서 중간에 월드시리즈 7차전을 잠깐보고 다시 문제를 풀었다.

오늘따라 다저스 타자들이 힘이 없어 보였다..나처럼 ㅜ

풀이방식

한번 생각해보자 ,

처음에 생각했던 방식 d[N - (N-1)] = d[N-1]+1 에 대해서 한번더 생각해보았다.

이렇게 하다보면 d[4]일때가 1차적으로 문제가 생기는데 ,

d[4-4] = d[0]+1을 만들어 줘야하기 때문이다.

자세히 식을 들여다보니 4 =2*2 가 된다. 그렇다면 1은 1x1이 된다는 것을 알 수 있다.

이제 반복문에 대해서 생각을 해보았다.

먼저 우리는 동적계획법을 할꺼고 bottom-up 방식을 사용하기 때문에 1부터 n까지 계산을

해줘야 된다.

for(int i = 1; i < n+1; i++) 로 시작하여

for(int j = 1l; j*j<i; j++)를 만든다. jxj < i 가 포인트인데 이유는

이렇게 하면 2의 제곱은 4부터 등장하게 되고, 처음 방식을 하면서 문제였었던 8은

d[8-4] = d[4] +1 = d[0] +1 +1 = 2가 될 수 있다.

따라서 조건에 의해 제곱수의 범위를 잘 나눌 수 있다. (손으로 해보는 것을 추천한다.)

점화식은 간단하다.

d[i] = Math.min(d[i],d[i-j*j]+1)

여기서 답을 놓칠뻔했다.

왜냐하면 d[i]를 초기화 해주지 않았다. d[i]의 초기화는 모두 d[i]=i로 해야된다.

이유는 모든 수는 1의 제곱으로 구성되어있기때문에, 1의 개수가 최대 개수가 된다.
코드 전체 보기

: 알고리즘은 항상 어렵다.

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 11051 이항 계수2  (0) 2017.11.01
백준 1915 가장 큰 정사각형  (0) 2017.11.01

2017.11.01 ** 수요일 ** Solution - 1012(유기농배추)
백준 1012 유기농배추

풀이방법: dfs


문제 해석

알고보니 예전에 틀렸던 문제이다, 왜 틀렸을까..

어렵지는 않다.

상하좌우 움직임 / dfs 만 알면된다.


풀이방식

한번 생각해보자 ,

지렁이는 움직인다. 지렁이가 이동하면서 모든 배추를 보호한다.

=> 다시말해서, 1이 모여있는 구역당 지렁이가 한마리면 된다.

상하좌우로 움직인다.

=> x,y가 움직일 두 개의 이동배열을 만든다.

int nx = x + dx[i];

int ny = y + dy[i];

1일때 dfs탐색을 시작한다.

=> map{i}{j}==1이면 탐색을 시작한다. 탐색을 시작할때마다 카운팅한다.

for (int i = 0; i < M ; i++) {

for (int j = 0; j < N ; j++) {

if (mapi == 1&&!visitedi) {

visitedi = true;

dfs(i, j);

cnt++;

}

}

}

방문했던것은 방문하지 않는다. (안하면 스택오버플로우)

=> 각 칸당 boolean 타입의 visited배열을 만들어 방문하면 true바꿔준다.

if (isRange(nx, ny)&& !visitednx&&mapnx==1) {

visitednx = true;

dfs(nx,ny);

}

이게 전부다. 그리고 재귀해주자,

코드 전체 보기

: 예전엔 왜 틀렸을까.. 중간에 10분정도 오류를 못찾았다.. 이유는..예제를 카운팅하면서 6으로 숫자를 세가지고

왜 5가 안되는거지 하면서 고민했다. 맞다 바보다..

2017.11.01 ** 수요일 ** Solution - 11051(이항 계수2)
백준 11051 이항 계수2

풀이방법: 동적계획법


문제 해석

이항 계수 문제이다. 고등학교때 수학을 배웠다면, 쉽게 생각할 수 있다.

단 .. 기억을 하고있다면 ...

역시 나는 기억하지 못하고 있었다(공부는 못해도 수학은 좀 했다 신승범짱!)

네이버 검색을 해서 이항계수의 공식을 보는데 이렇게 풀면 되겠구나 하는게 있었다.


출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98


이 공식을 보고 풀이를 시작했다.

풀이방식

한번 생각해보자 ,
우리는 n과 k를 안다.
두가지로 나눠져있다.

=> 두개의 경우로 나눠서 합치자!

순열,조합을 풀다보면 항상 재귀를 떠올리게 된다.

이것 또한 재귀적 방법으로 풀면된다. 또한 메모이제이션을 통해 효율성을 높여주면된다.

그리고 공식에서는 우측이 n+1이지만, 우리는 굳이 저렇게 할필요없다. 모든 항목을 -1해주자

이제 끝이다. 뽑기만 하면된다.

그리고 베이스 케이스 설계를 해야되는데, 한 번 생각을 해보자, 뽑을때마다 각 케이스 별로 -1씩을 해줄것이다.

dp {n}[k} = solution(n-1,k-1) + solution(n-1,k);

이렇게 식을 세우게 되면 어느순간 k==n 또는 k==0이된다. 수학시간에 배웠다. nCn =1 , nC0 = 1이다.

그러면 우리는 베이스 케이스를 설계 할 수 있다.

if(n==k||k==0) return 1;

이렇게 설계하면 될 것이다.

그리고 메모이제이션

if(dp{n}{k}>0) return dp{n}{k}

이제 끝이다 !

이렇게 3줄이면 끝난다. 검증을 하고 싶다면 예제를 손으로 하면된다. 5분도 안걸린다.
코드 전체 보기

: 나이를 먹더니 수학을 다 까먹은 것 같다..

'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02
백준 1915 가장 큰 정사각형  (0) 2017.11.01
2017.10.31 ** 화요일 ** Solution - 1915(가장 큰 정사각형)

풀이방법: 동적계획법



문제 해석

기억난다.. 처음 풀었던 당시에 엄청 끙끙..거렸다는 것을..
알고보면 상당히 쉬운 문제이나 , 당시에 그 아이디어까지 가는데
머리가 좋지 않아서 2시간정도 걸렸던것 같다..

그 당시 풀이보다 시간복잡도가 반이나 줄어서 이렇게 포스팅하게 되었다.
(더 익숙해졌길래 의아했는데 , 알고보니 카카오 모의테스트 였구나..)



풀이방식

처음 이 문제를 접했을때는, 무식하게 완탐하려고했다.. 그렇게 시간이 흐르고 흘러

코드를 보니 엄청 더럽고, 내가 잘못하고 있다는 것을 알게되어 생각을 더하게 되었다.

문제를 잘보면 직관적으로 1로 이루어진 4각형이 보인다. 우리는 저 크기를 골라 내야한다.

처음에 시도했던 방법은 왼쪽위의 끝점(0,0)부터 계산해야하나 했다. 그런데 그렇게 하다보면

어떻게 사각형을 판별해야하는지 의문이 생긴다.

그래서 그 다음으로는 매핑되는 점을 선택해서 돌려보았다. 뭔가 사각형으로 마지막점까지 갈 수가 있어졌다.

그렇다면 어떻게 계산을 할지 고민해보았다. 예제에 있는 사각형을 보고 좀 전에 사각형 판별법과 같이 생각해보면

판별되는 숫자를 1로 감싸고 있다. ?!-> 아 변이 2다 ..그렇다면 1은 변이 1로 생각할 수 있겠다!




그렇다면 판별되는 숫자를 2로 바꿔주면 2가 될것같다.

다시 해석해보자면 판별되는 숫자를 기준으로 그 숫자와 나머지 3개가 같으면 +1로 증가시켜준다(정사각형이기때문에!)

하지만 잘생각해보면 0에서 -> 1도 만들어야하고 , 각각 한칸당 넓이가 1인 정사각형이다.

그래서 3개의 공간 ( 왼쪽위 , 바로위 , 왼쪽)을 비교해서 가장 작은 수를 +1시킨다.(그래야 주위에 0이 잇을때 1인 정사각형을 만듬)
->map[i][j] = Math.min(map[i - 1][j - 1], Math.min(map[i - 1][j], map[i][j - 1])) + 1;

그렇게 판별되는 정사각형의 넓이를 계산하여 최대 사각형의 넓이 변수 (maxCnt)와 비교하여 마지막에 출력한다.
->maxCnt = maxCnt < map[i][j] ? map[i][j] : maxCnt;

: 좀 마지막에 시간이 걸렸다.. 오류가 계속났다. 왜 그런지살펴보니 maxCnt*maxCnt가 답인데, 그냥 maxCnt만 출력했다..주의하자..





'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2579 계단오르기  (0) 2017.11.07
백준 1463 1로 만들기  (0) 2017.11.03
백준 11726,11727 2xN타일링 , 2xN타일링2  (0) 2017.11.03
백준 1699 제곱수의 합  (0) 2017.11.02
백준 11051 이항 계수2  (0) 2017.11.01

+ Recent posts

티스토리툴바