소스 보러가기
문제 보러가기

사용한 알고리즘 및 자료구조
DFS/BFS, 그래프

풀이

간단한 DFS/BFS 문제이다. 문제를 푸는데 20분도 안 걸렸다. 이번에는 DFS를 이용해서 해당 문제를 풀었다. 이 문제를 읽고 생각을 했던 것은 2차원 배열에서 (n,n) 칸들을 기준으로 좌우 대칭이 된다는 것이다. 또한 각각의 값들이 연결관계를 표현했다. 따라서 처음에 탐색할 때는 1/2만 탐색을 하고 DFS 를 사용할 때는 연결관계를 기준으로 탐색을 하면 된다. 보통의 DFS 문제는 ‘상하좌우’로 움직이면서 문제를 해결했지만, 해당 문제는 배열의 값들이 내포하고 있는 연결관계를 이용해서 DFS 함수를 구현했다.

  1. 초기화
  2. 문제에 해당하는 조건( 배열의 값 : 1 && 아직 탐색하지 않은 칸) 찾기 ,조건을 찾을 때 마다 answer++
  3. 조건 찾고 나서 DFS 함수를 이용해 연결관계를 따라 영역표시하기
  4. 다시 2-3번 반복
  5. Answer 출력

간단한 DFS 문제이다. 실제로 삼성 시험을 봤던 사람들에게는 매우 쉬웠을 거라 생각한다. 다만 이것을 어떻게 해야 더 효율적으로 구현할 수 있을까 고민해보았다. 간단한 문제라 특별하게 적용할 것은 없었으나, 그래도 고민 해보면 좋을 것이다.

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
    public static int SIZE;
 
    // before test, have to delete 'static' keywords
    public static int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[][] visited = new boolean[n][n];
        SIZE = n;
 
        for (int c_idx = 0; c_idx < n; c_idx++)
            for (int r_idx = c_idx; r_idx < n; r_idx++) {
 
                if ((computers[c_idx][r_idx] == 1) && (visited[c_idx][r_idx] == false)) {
                    visited[c_idx][r_idx] = true;
                    dfs(r_idx, visited, computers);
                    answer++;
 
                }
            }
 
        return answer;
    }
 
    public static void dfs(int idx, boolean[][] visited, int[][] computers) {
 
        for (int col = 0; col < SIZE; col++) {
 
            if ((computers[idx][col] == 1) && (visited[idx][col] == false)) {
 
                visited[idx][col] = true;
 
                dfs(col, visited, computers);
 
            }
 
        }
 
    }
 
 
cs

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

[프로그래머스] 124 나라의 숫자  (0) 2020.08.30
[프로그래머스] 2n 타일링  (0) 2020.08.23
백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13

문제 보기


* 몸이 안좋아서 , 짧게 하겠습니다.


4가지 풀이가 있습니다. 


solve1 은 현재칸을 기준으로 전 단계가 될 수 있는 칸들을 계산합니다.


solve2 는 현재칸을 기준으로 현재칸이 갈 수 있는 3가지의 경로를 계산합니다.


solve3는 solve1을 봤을때 대각선으로 바로 이동하는 수는 다른 방법으로 오는 수들 보다 작을 수 밖에 없습니다. 

이유는 모두 0보다 크기때문입니다. 그러기 때문에 수가 줄어들일이 없습니다. solve1 - 대각선 이라고 생각하시면 될 것 같습니다.


solve4는 재귀로 풀어봤습니다. 딱히 어려운건 없습니다.


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package Problems;
 
/**
 * 
 * 
 * 백준 11048 이동하기 
 *  
 *
 */
import java.util.Scanner;
 
public class Boj11048dp {
 
    public static int n, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        int[][] solve4 = new int[n + 1][m + 1];
        
        solve1(arr);
        solve2(arr);
        solve3(arr);
        int temp = solve4(arr,solve4,n,m);
        System.out.println(temp);
 
    }
 
    public static void solve1(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], Math.max(dp[i - 1][j - 1], dp[i][j - 1])) + arr[i][j];
                System.out.println("arr" + arr[i][j] + "    :   dp"  + dp[i][j]);
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static void solve2(int[][] arr) {
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
 
                if ( j + 1 <=m && dp[i][j + 1] < dp[i][j] + arr[i][j + 1]) {
                    dp[i][j + 1] = dp[i][j] + arr[i][j + 1];
                }
 
                if (i + 1 <= n && j + 1 <= m && dp[i + 1][j + 1] < dp[i][j] + arr[i + 1][j + 1]) {
                    dp[i+1][j + 1] = dp[i][j] + arr[i + 1][j + 1];
                }
 
                if (i + 1 <=n && dp[i + 1][j] < dp[i][j] + arr[i + 1][j]) {
                    dp[i+1][j] = dp[i][j] + arr[i + 1][j];
                }
            }
        }
 
        System.out.println(dp[n][m]);
    }
 
    public static void solve3(int[][] arr) {
 
        int[][] dp = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
 
        System.out.println(dp[n][m]);
 
    }
 
    public static int solve4(int[][] arr, int[][] dp, int x, int y) {
 
        if (x == 1 && y == 1) {
            return arr[1][1];
        }
        if (x < 1 || y < 1) {
            return 0;
        }
 
        if (dp[x][y] > 0) {
            return dp[x][y];
        }
 
        dp[x][y] = solve4(arr, dp, x - 1, y) + arr[x][y];
        int temp = solve4(arr, dp, x, y - 1) + arr[x][y];
 
        if (dp[x][y] < temp) {
 
            dp[x][y] = temp;
        }
 
        return dp[x][y];
 
    }
 
}
 
cs


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

백준 1563 개근상  (0) 2017.11.14
백준 1495 기타리스트  (0) 2017.11.13
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07

문제보기 


연속합을 구할때 유의할점은 

음수를 포함해도 답이 될때가 있다는 것이다. 

예를 들어 10 -1 11 일때, 음수를 포함하지 않으면 답이 나오질 않는다. 음수를 포함해서 10 + (-1) + 11 이 되어야만 가장 큰 연속합이된다.


D[i]는 A[i]로 끝나는 최대 연속합을 저장하는 배열이다. 


1. A[i-1]로 끝나는 연속합에 , A[i]가 포함된다. 

2. 1번의 경우보다 A[i]가 큰 경우이다. 


이 두개의 경우로 식을 세우면 된다.


D[i] = Math.max(A[i],D[i-1]+A[i])


시간복잡도는 O(N)이다. 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
36
37
38
39
40
41
42
43
44
package Problems;
/**
 * 
 * 백준 1912 연속합 
 * 
 * 동적 계획
 * 
 */
import java.util.Scanner;
 
public class Boj1912dp {
    
    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+1; i++) {
            arr[i] = in.nextInt();
        }
        
        for(int i = 1; i < n+1; i++) {
            
            dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);
            
        }
        
        int ans = dp[1];
        
        for(int i = 1; i < n+1; i++) {
            
            if(ans < dp[i]) {
                ans = dp[i];
            }
        }
        
        System.out.println(ans);
        
    }
 
}
 
cs


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

백준 1495 기타리스트  (0) 2017.11.13
백준 11048 이동하기  (0) 2017.11.08
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07
백준 11053 가장 긴 증가하는 부분수열  (0) 2017.11.07
백준 2579 계단오르기  (0) 2017.11.07

문제보기


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

Java 9 요약 보러가기

출저: pop it의 심천보님




잘 정리가 되어있는 글을 읽고, 공유하게 되었습니다. 


이번 발표에 대한 가장 충격이었던 부분은 'var 지원'이였습니다. 뭔가 어색하네요 ,


한번 다들 읽어보셔요 ! 

'개발이야기 > Java' 카테고리의 다른 글

Linked List (단순 연결 리스트) 소스  (0) 2017.11.10
GC(가비지 콜렉션)에 대한 공부  (0) 2017.11.03

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.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가 안되는거지 하면서 고민했다. 맞다 바보다..

+ Recent posts

티스토리툴바