반응형

DFS 백트래킹 ,, 비트연산


백트래킹과 비트연산 2가지 모두 풀었다.

모든 경우의 수만 구하면 문제는 쉽게 풀린다.


풀이

1. 모든 경우의 수를 구한다.

2. 경우의 수를 value[] 배열에 0과 1로 저장한다.

3. 반으로 나눠야 하므로 1의 개수가 value[]의 크기 /2 일때 그 다음 과정을 수행할 수 있다.

4. 스타트팀과 링크팀을 나눠야 하는데 value의 조건에 따라 start[]팀과 link[]팀으로 나눈다.

5. start[], link[] 배열에 저장되는 것은 팀원이다.

(1,2 가 스타트팀 3,4 가 링크 팀일 경우 start[0] = 0, start[1] = 1, link[0] = 2, link[1]= 3 이 저장된다. [0부터 시작될 경우])

6. start[], link[] 배열을 (n/2) (n/2) 탐색하여 arr[][] 배열을 통해 값을 얻어 스타트팀의 최종 점수와 링크 팀의 최종 점수를 구한다.

7. 두 값의 차이가 최소를 정하고 출력한다.



소스 

(비트연산)

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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        //Scanner sc = new Scanner(new FileInputStream("input.txt"));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
 
        int[] start = new int[n];
        int[] link = new int[n];
        int min = Integer.MAX_VALUE;
 
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
 
        for (int i = 1; i < 1 << n; i++) {
            int[] value = new int[n];
            int count = 0;
 
            int bit = i;
            for (int j = 0; bit != 0; j++, bit >>= 1) {
                if ((1 & bit) == 0) {
                    continue;
                }
                value[j] = 1;
            }
 
            for (int k = 0; k < n; k++) {
                if (value[k] == 1) {
                    count++;
                }
            }
            //-----------경우의 수를 구하고 난 후----------------//
            
            //팀의 인원이 정확히 2로 나누어졌을 때 만 다음과정을 실행 할 수 있다.
            if (count == n / 2) {
                int start_sum = 0;
                int link_sum = 0;
                int start_cnt = 0;
                int link_cnt = 0;
                //value[] 값이 1이면 스타트팀, 0이면 link 팀이 된다.
                for (int k = 0; k < n; k++) {
                    if (value[k] == 1) {
                        //start_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                        start[start_cnt++] = k;
                    } else {
                        //link_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                        link[link_cnt++] = k;
                    }
                }
                
                //두팀이 가질 수 있는 점수를 다 구한다.
                //(1,1) (2,2) 등이 발생할 때 값은 0이므로 따로 조건을 만들지 않았다.
                for(int x=0; x<n/2; x++){
                    for(int y=0; y<n/2; y++){
                        start_sum += arr[start[x]][start[y]];
                        link_sum += arr[link[x]][link[y]];
                    }
                }
                //최소값 구함
                if(min > Math.abs(start_sum- link_sum)){
                    min = Math.abs(start_sum- link_sum);
                }
            
            }
 
        }
 
        System.out.println(min);
 
    }
 
}
 
cs


(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
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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
class Main {
    static int[][] arr;
    static int[] result;
    static int N;
    static int count;
    static int[] start;
    static int[] link;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
 
        arr = new int[N][N];
        result = new int[N];
        start = new int[N];
        link = new int[N];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                // arr[i] = integer.parseint(str[i + 1]);
            }
        }
        DFS(0, 0);
        System.out.println(min);
    }
 
    public static void DFS(int start, int depth) {
 
        for (int i = start; i < N; i++) {
            result[i] = 1;
            count++;
 
            DFS(i + 1, depth + 1);
            result[i] = 0;
            count--;
        }
        //-----------경우의 수를 구하고 난 후----------------//
 
        if (count == N / 2){
            //print();
            calc();
        }
 
    }
 
    public static void print() {
        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
 
    public static void calc() {
        int start_sum = 0;
        int liNk_sum = 0;
        int start_cNt = 0;
        int liNk_cNt = 0;
        //value[] 값이 1이면 스타트팀, 0이면 link 팀이 된다.
        for (int k = 0; k < N; k++) {
            if (result[k] == 1) {
                //start_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                start[start_cNt++] = k;
            } else {
                //link_cnt는 0부터 스타트 팀에 사람이 들어올때마다 1씩 증가한다.
                link[liNk_cNt++] = k;
            }
        }
 
        //두팀이 가질 수 있는 점수를 다 구한다.
        //(1,1) (2,2) 등이 발생할 때 값은 0이므로 따로 조건을 만들지 않았다.
        for (int x = 0; x < N / 2; x++) {
            for (int y = 0; y < N / 2; y++) {
                start_sum += arr[start[x]][start[y]];
                liNk_sum += arr[link[x]][link[y]];
            }
        }
        //최소값 구함
        if (min > Math.abs(start_sum - liNk_sum)) {
            min = Math.abs(start_sum - liNk_sum);
        }
 
    }
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 9465 - 스티커 (자바)  (0) 2018.02.10
[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)  (0) 2018.02.10
[BOJ] 백준 1759 - 암호 만들기 (자바)  (0) 2018.02.09
[BOJ] 백준 1890 - 점프 (자바)  (0) 2018.02.09
[BOJ] 백준 6603 - 로또 (자바)  (2) 2018.02.09
반응형

DFS 백트래킹


시작과 동시에 배열을 정렬해줘야햔다. 이거 안봐서 왜틀렸는지 몰랐네;;

그리고 자음 모음 갯수 함수를 반대로해줘야 하는데 똑같이 해서 왜 틀렸는지 몰랏네;;


풀이

1. 백트래킹 형식으로 풀면된다.

2. 자음과 모음 갯수를 파악하면 된다.

3. result[] 배열을 사용해서 선택된 문자가 무엇인지 저장한다.


백트래킹은 하나씩 찍어보면서 푸는게 가장 좋은 것 같다.



소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    static char[] arr;
    static int[] result;
    static int N;
    static int M;
 
    public static void main(String[] args) throws Exception {
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new char[M];
        result = new int[M];
        str = br.readLine().split(" ");
        for (int i = 0; i < M; i++) {
            arr[i] = str[i].charAt(0);
        }
 
        Arrays.sort(arr); // 문제를 보면 정렬되어 있어야한다....
        DFS(0, 0, 0, 0);
    }
 
    // 시작점, 선택된 문자갯수, 자음갯수, 모음갯수
    public static void DFS(int start, int depth, int ja, int mo) {
 
        for (int i = start; i < M; i++) {
            result[i] = 1; // 선택된 문자 확인용
            // 자음과 모음 갯수를 파악해서 다음으로 넘겨준다.
            DFS(i + 1, depth + 1, ja + (!check(arr[i]) ? 1 : 0), mo + (!check(arr[i]) ? 0 : 1));
 
            result[i] = 0; // 0이면 선택 안됨
        }
        // 문자갯수가 N개이며 자음과 모음의 갯수가 규칙에 맞을때만 출력한다.
        if (depth == N && ja >= 2 && mo >= 1) {
            print();
        }
    }
 
    public static void print() {
        for (int i = 0; i < M; i++) {
            // result가 0이라면 선택되지 않았기 때문에 넘긴다.
            if (result[i] == 1)
                System.out.print(arr[i]);
        }
        System.out.println();
    }
 
    // 자음 모음 파악 함수
    public static boolean check(char a) {
        if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
            return true;
        else
            return false;
    }
 
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)  (0) 2018.02.10
[BOJ] 백준 14889 - 스타트와 링크 (자바)  (2) 2018.02.09
[BOJ] 백준 1890 - 점프 (자바)  (0) 2018.02.09
[BOJ] 백준 6603 - 로또 (자바)  (2) 2018.02.09
[BOJ] 백준 11048 - 이동하기 (자바)  (0) 2018.02.07
반응형

DP


DP 말고 큐랑 클래스 써서 별 지랄을 하면서 풀려고 했는데 실패..

완벽히 돌아갈게 할려고 만들면 시간초과, 시간초과 안나게 만들려니 틀렸습니다..


그냥 과감히 접고 DP로 넘어왔다.

게임판의 크기가 100 * 100 이므로 전체탐색 충분히 가능하다.

단, 런타임 에러나 무슨 오류가 날지는 모르지만 

경로의 개수는 263-1보다 작거나 같다. 라는 문구가 있기때문에 

경로 개수를 찾는 DP[][] 배열은 long 으로 만들어야한다.


전체 탐색이 가능한 이유는 이동방향이 오른쪽과 아래이기 때문에 그 다음이동에 영향을 미치지 않는다. (순차적으로 접근하기 때문)

Queue를 사용할려 했을 때는 순차접근이 안되서 계속 값이 바뀔때마다 고치고 했어야 해서 시간초과 났다.


풀이

1. 0,0 부터 N,N 까지 방문하여 다음 갈곳 경로의 횟수를 추가 해준다. (dp[i][j+next], dp[i+next][j] = dp[i][j];)

2. 단 N,N일때는 경로가 추가되면 안된다. 그리고 다음 이동할 경로가 게임판을 넘어가면 안된다. ㅎ


소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
class Main {
    static int N;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
 
        N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];
        long[][] dp = new long[N + 1][N + 1];
        String str[];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
 
            }
        }
        dp[0][0]=1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i==N-1&&j==N-1) continue;
                int next = arr[i][j];
                if (i + next < N) {
                    dp[i + next][j] += dp[i][j];
                }
                if (j + next < N) {
                    dp[i][j + next] += dp[i][j];
                }
                //print(dp);
                //System.out.println();
            }
        }
        System.out.println(dp[N-1][N-1]);
    }
    public static void print(long[][] dp){
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                System.out.print(dp[i][j]+" ");
            }
        System.out.println();
        }
        
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 14889 - 스타트와 링크 (자바)  (2) 2018.02.09
[BOJ] 백준 1759 - 암호 만들기 (자바)  (0) 2018.02.09
[BOJ] 백준 6603 - 로또 (자바)  (2) 2018.02.09
[BOJ] 백준 11048 - 이동하기 (자바)  (0) 2018.02.07
[BOJ] 백준 1753 - 최단경로 (자바)  (3) 2018.02.07
반응형

백트래킹..  비트연산..


나는 비트연산으로 한번 풀고 백트래킹으로 한번 풀었다.

근데 이 문제처럼 사전순으로 정렬해서 출력해야 한다는 가정이 나와있는 문제는 백트래킹이 훨씬 풀기 쉬운거 같다.

백트래킹의 경우 순차적으로 접근하기 때문


두 문제 똑같이 result[] 배열와 arr[] 배열을 사용했다.

result[] 배열의 경우, 갯수 6개가 되는 경우의 수를 파악하기 위해 이용된다. ( 배열 안에는 0과 1 로 구성되어있다.)

arr[] 배열의 경우, 출력할 때 필요한 값들을 가지고 있다. 출력할 때 값이 손상되면 안되므로 result[] 배열을 사용했다.


풀이

1. result[] 배열을 통해 경우의 수를 구한다. (4자리라면 0000 부터 1111까지 모든 수를 구한다.)

2. 모든 수중에 1의 개수가 원하는 개수(로또 문제에서는 6개) 일 때 출력한다.

3. 개수를 체크하는 방법은 비트연산에서는 count 변수를 사용했고, 백트래킹 같은 경우 함수를 들어갈때 depth 인자로 사용했다.

4. 출력시에 result[] 배열이 1인 부분만 출력하되 출력은 arr[] 배열을 출력한다.

끝


비트연산시에 result[] 배열은 사전순으로 출력해야 되기 때문에 반대로 저장해야한다.


소스

(비트연산)

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            String[] str = br.readLine().split(" ");
            int N = Integer.parseInt(str[0]);
            int[] arr = new int[N];
            int[] result = new int[N];
 
            if (N == 0) {
                break;
            }
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(str[i + 1]);
            }
 
            for (int i = (1<<N)-1; i >=0; i--) {
                Arrays.fill(result, 0);
                int count = 0;
                int bit = i;
                for (int j = 0; bit != 0; j++, bit >>= 1) {
                    if ((1 & bit) == 0) {
                        continue;
                    }
                    // 사전순 정렬을 해야하기 때문에 반대로 출력해줘야한다.
                    result[Math.abs((N-1)-j)] = 1;
                    count++;
                }
                if (count == 6) {
                    for (int k = 0; k <N; k++) {
                        if(result[k]==1)
                        System.out.print(arr[k] + " ");
                    }
                    System.out.println();
                }
            }
            System.out.println();
        }
 
    }
 
}
cs



(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
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
    static int N;
    static int[] arr;
    static int[] result;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while (true) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]);
            arr = new int[N];
            result = new int[N];
 
            if (N == 0) {
                break;
            }
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(str[i + 1]);
            }
            DFS(0,0);
            System.out.println();
        }
 
 
    }
    public static void DFS(int start, int depth){
        if(depth==6){
            print();
        }
        for(int i=start; i<N; i++){
        result[i] = 1;
        DFS(i+1,depth+1);
        result[i] = 0;
        }
        
    }
    public static void print(){
        for(int i=0; i<N; i++){
            if(result[i]==1)
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    
}
 
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1759 - 암호 만들기 (자바)  (0) 2018.02.09
[BOJ] 백준 1890 - 점프 (자바)  (0) 2018.02.09
[BOJ] 백준 11048 - 이동하기 (자바)  (0) 2018.02.07
[BOJ] 백준 1753 - 최단경로 (자바)  (3) 2018.02.07
[BOJ] 백준 14888 - 연산자 끼워넣기 (자바)  (0) 2018.02.07
반응형

DP?


dp 문제인가?

아주 기초적인 dp 문제인듯

문제에 설명이 다 나와있다. 그냥 따라 하면 됨.


풀이

1. (1,1)칸 부터 위, 왼 ,위왼 중 가장 큰 값이랑 자기자신 값이랑 더하면 된다.

2. (N,M)까지 하면 arr[N][M] 이 정답이 된다.


소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
 
        int[][] arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            str = br.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Integer.parseInt(str[j-1]);
            }
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += Math.max(arr[i][j-1],Math.max(arr[i-1][j], arr[i-1][j-1]));
            }
        }
        System.out.println(arr[n][m]);
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1890 - 점프 (자바)  (0) 2018.02.09
[BOJ] 백준 6603 - 로또 (자바)  (2) 2018.02.09
[BOJ] 백준 1753 - 최단경로 (자바)  (3) 2018.02.07
[BOJ] 백준 14888 - 연산자 끼워넣기 (자바)  (0) 2018.02.07
[BOJ] 백준 2668 - 숫자고르기 (자바)  (0) 2018.02.07
반응형

다익스트라.


맨처음 인덱스 x 인덱스로 했다가 런타임에러.. 메모리 초과 떴다.

20000 * 20000 이므로 400000000 ... 4억이다. 메모리 안되서 땡.

어떻게 짤까 고민하다가 클래스 하나 만들어서 구현했는데

왠걸 시간초과.... 어디서 잘못됬나 봤더니 vertex의 예전값과 비교하는데 더 좋을 경우만 바꾸면 되는데 그렇지 않을 경우도 계속 Queue에 집어넣어서 실패...

다시 구현했는데 연속 3번 틀렸습니다. 문구가 뜨네? 진짜 어디서 틀린지 몰라서 우선순위 큐가 MaxHeap으로 되어야 하나 이생각했는데

틀린부분 찾으니까 내가 부등호 잘못해준곳이 있었네? 음... 아무튼 구현 성공.

확실히 개념 공부하는데는 코딩으로 배우는게 최고긴 하네


풀이

1. 거리를 계산할 distance[] 배열 하나, vertex간 연결과 edge를 저장해줄 Edge클래스와 Arraylist[] 배열 하나, INF를 구별해줄 visited[] 하나 있으면 된다.

2. 출발점으로부터 그 다음값들을 큐에 저장해준다. 가장 Edge가 짧은 노드들로 정렬하는게 성능이 좋단다. 그래서 우선순위 큐를 사용하는 거고. (난 안했네;;)

3. 다음값들을 큐에 저장하기 전에 이전값이 더 작다면(거리가 가깝다면) 굳이 큐에 집어넣어줄 필요 없다.

4. 큐가 빌 때까지 반복하면 끄으읏!


소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(newInputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int vertex = Integer.parseInt(str[0]);
        int edge = Integer.parseInt(str[1]);
        int K = Integer.parseInt(br.readLine());
        int[] distance = new int[vertex + 1];
        // 방문하지 못한점은 INF로 출력해줘야한다.
        boolean[] visited = new boolean[vertex + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        // index by index 배열로 했더니 메모리 초과 나서 ArrayList로 바꿈.
        ArrayList<Edge>[] list = new ArrayList[vertex + 1];
        for (int i = 0; i <= vertex; i++) {
            list[i] = new ArrayList<Edge>();
        }
 
        for (int i = 0; i < edge; i++) {
            str = br.readLine().split(" ");
            list[Integer.parseInt(str[0])].add(new Edge(Integer.parseInt(str[1]), Integer.parseInt(str[2])));
        }
 
        // 우선순위 큐를 사용해야 한다. 성능이 더 좋아짐
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        // 시작점 설정해주고 시작점 - 시작점 거리는 0이다.
        q.add(K);
        distance[K] = 0;
        while (!q.isEmpty()) {
            // 다음에 방문할 vertex 설정
            int current = q.poll();
            // 방문했기 떄문에 true, INF는 아니다.
            visited[current] = true;
 
            for (int i = 0; i < list[current].size(); i++) {
                // 현재 vertex에서 다음 vertex를 차근차근 비교해서 우선순위 큐에 넣어야한다.
                int next = list[current].get(i).end; // 다음 vertex
                int value = list[current].get(i).value; // 현재 - 다음 간 edge값
 
                // 이전에 있던 값이 더 크다면 굳이 다시 방문할 필요가 없다. 이미 그 전이 더 최단 경로이기 때문에
                if (distance[next] > distance[current] + value) {
                    distance[next] = Math.min(distance[next], value + distance[current]);
                    q.add(next);
 
                }
 
            }
        }
        // 출력
        for (int i = 1; i <= vertex; i++) {
            if (visited[i]) {
                System.out.println(distance[i]);
            } else {
                System.out.println("INF");
            }
        }
    }
 
}
 
class Edge {
    int end;
    int value;
 
    Edge(int end, int value) {
        this.end = end;
        this.value = value;
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 6603 - 로또 (자바)  (2) 2018.02.09
[BOJ] 백준 11048 - 이동하기 (자바)  (0) 2018.02.07
[BOJ] 백준 14888 - 연산자 끼워넣기 (자바)  (0) 2018.02.07
[BOJ] 백준 2668 - 숫자고르기 (자바)  (0) 2018.02.07
[BOJ] 백준 1516 - 게임 개발 (자바)  (0) 2018.02.06
반응형

삼성 17하반기 CE/IM 기출  2번문제 ,,,,  DFS


이거 시험장에서 풀었으면 어려웠을 뻔 했다. DFS라는 것을 알고 풀으니 확실히 쉽긴한다.


풀이

1. DFS로 전체 탐색하면 된다.

2. 숫자 (여기서는 x로 가정) 는 +1씩 증가 시켜 인자로 넘겨주면 되고 그 때마다 전체 합인 sum 또한 인자로 넘겨주면 된다.

3. 탐색동안 끝까지 탐색 완료하면 그때의 sum 값을 List에 저장해준다.

4. 모든 탐색이 끝나고 List에 저장된 sum 값중에 최대 값과 최소 값을 출력해주면 된다.


나는 직관적으로 보기 위해 MH 배열을 사용하여 연산자가 어디 들어갈 때 어떠한 숫자가 나오는지 출력하여 봤다.


소스

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
import java.io.FileInputStream;
import java.util.*;
 
class Main {
    static int[] arr;// 숫자 배열
    static int[] op;// 연산자 횟수를 저장할 배열
    static ArrayList<Integer> list; // 최소값과 최대값을 찾기 위해 모든 값들을 저장해줌
    static char[] MH; // 직관적으로 보기위해 (결과에는 영향 X)
    static int N;
    static int count = 0;
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        // Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        arr = new int[N];
        op = new int[4];
        MH = new char[N]; // 직관적으로 보기위해 (결과에는 영향 X)
 
        list = new ArrayList<Integer>();
 
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
 
        for (int i = 0; i < 4; i++) {
            op[i] = sc.nextInt();
        }
 
        DFS(1, arr[0]); // 출발 시작
        Collections.sort(list);
        System.out.println(list.get(list.size() - 1));
        System.out.println(list.get(0));
    }
 
    // x는 다음 숫자이고 sum은 그곳까지 갔을 때 합 이다.
    static void DFS(int x, int sum) {
        // ('+', '-', '*', '/') 연산자들을 한번씩 다 확인해야함 (DFS 전체탐색이니깐)
        for (int i = 0; i < 4; i++) {
            // 각각의 연산자마다 개수를 둬서 모두 0이면 쓸 연산자가 없으므로 통과
            if (op[i] != 0) {
                op[i]--; // 사용된 연산자를 하나씩 뺀다.
                switch (i) {
                case 0:
                    MH[x - 1] = '+'; // 필요없지만 정보확인차
                    DFS(x + 1, sum + arr[x]); // 다음 숫자 계산해야되니깐
                    break;
                case 1:
                    MH[x - 1] = '-'; // 필요없지만 정보확인차
                    DFS(x + 1, sum - arr[x]); // 다음 숫자 계산해야되니깐
                    break;
                case 2:
                    MH[x - 1] = '*'; // 필요없지만 정보확인차
                    DFS(x + 1, sum * arr[x]); // 다음 숫자 계산해야되니깐
                    break;
                case 3:
                    MH[x - 1] = '/'; // 필요없지만 정보확인차
                    DFS(x + 1, sum / arr[x]); // 다음 숫자 계산해야되니깐
                    break;
                }
                MH[x - 1] = 0; // 필요없지만 정보확인차
                op[i]++; // 사용이 끝났으면 다시 추가해준다.
            }
        }
 
        // 카운트가 입력값과 같아질 때 출력 (모든 숫자를 다 사용했을 경우)
        if (x == N) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
                System.out.print(MH[i] + " ");
            }
 
            System.out.println("= " + sum);
            list.add(sum);
        }
    }
 
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 11048 - 이동하기 (자바)  (0) 2018.02.07
[BOJ] 백준 1753 - 최단경로 (자바)  (3) 2018.02.07
[BOJ] 백준 2668 - 숫자고르기 (자바)  (0) 2018.02.07
[BOJ] 백준 1516 - 게임 개발 (자바)  (0) 2018.02.06
[BOJ] 백준 2252- 줄 세우기 (자바)  (0) 2018.02.06
반응형

DFS


풀었다. 하고 출처 봤는데 초등부 문제...... 초등학생들이 이런 문제를 푼단 말인가....?


나는 아주 단순하게 풀었다. 그래서인지 성능이 별로인거 같다.


풀이

1. 1~7까지 숫자가 있으므로 각 숫자마다 DFS() 를 해준다.

2. 사이클이 완성된다면 숫자 고르기 성공. 사이클이 실패면 위, 아래의 값이 달라지기 때문에 숫자를 고를 수 없다.

3. 단, 이전에 방문했던 점을 다시 방문하게 되면 무한재귀현상에 빠지게 된다. 그래서 이전에 방문했던 점들을 visited[] 배열로 체크해준다.

4. 1~7 숫자, 하나씩 DFS를 해준후 방문했던 점들 visited[] 배열을 초기화 시켜준다.


소스

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    static int[] arr;
    static boolean[] visited;
    static int last;
    static ArrayList<Integer> list;
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        int N = sc.nextInt();
        arr = new int[N + 1];
        visited = new boolean[N + 1];
        list = new ArrayList<Integer>();
        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            visited[i] = true;    //무한 재귀에 빠지면 안되므로 첫 시작점도 방문으로 체크
            last = i;
            DFS(i);
            visited[i] = false; //다음 숫자 DFS를 해야하므로 초기화 시켜준다.
        }
        Collections.sort(list);    // 작은수 부터 출력해야하므로 젖ㅇ렬
        System.out.println(list.size());
        for (int i : list) {
            System.out.println(i);    //list들을 하나씩 출력해준다.
        }
    }
 
    public static void DFS(int i) {
        
        if (!visited[arr[i]]) {     //이전에 방문한 점이 아니여야한다.
            visited[arr[i]] = true;     // 방문했으므로 true
            DFS(arr[i]);
            visited[arr[i]] = false; // 다음 DFS들을 위하여 false
        }
        if (arr[i] == last) {    //마지막 점이 출발점과 같다면 사이클이 완성됐으므로 리스트에 추가
            list.add(last);
        }
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 1753 - 최단경로 (자바)  (3) 2018.02.07
[BOJ] 백준 14888 - 연산자 끼워넣기 (자바)  (0) 2018.02.07
[BOJ] 백준 1516 - 게임 개발 (자바)  (0) 2018.02.06
[BOJ] 백준 2252- 줄 세우기 (자바)  (0) 2018.02.06
[BOJ] 백준 1766- 문제집 (자바)  (0) 2018.02.06
반응형

위상정렬 (Topological Sort) 의 가장 대표적인 문제


위상정렬 뿐 아니라 배열 두개를 더 만들어서 각각의 시간을 저장해야한다.

배열 1 : 원래의 값들(건물 짓는데 걸리는 시간)을 저장하는 배열

배열 2 : 최소의 시간을 구하기 위한 배열 (이전의 건물 짓는데 걸린 시간을 더해야한다. 그로므로 배열 1만 사용하는 것은 불가능.. 코드 괴물들은 가능할지도?)

그리고 이번 위상정렬 문제는 입력을 받을 때 반대로 받아야 Indegree의 값에 혼란이 오지 않는다. 그래야 위상정렬이 가능.


풀이

1. List를 이용하여 값을 저장해준다.(ArrayList, LinkedList 둘다 사용 가능) 

2. indegree가 0인 값을 큐에 모두 집어 넣는다.

3. 큐가 빌때까지 0인 값을 하나씩 빼서 그 다음 값을 다시 큐에 집어 넣는다. (단 그때 화살표 값인 Indegree를 하나씩 줄인다.)

4. 큐에서 빼고 난 후에 자기 자신까지 가장 오래 걸린 시간을 배열에 저장해야한다. (이전 건물들을 모두 지어야 자기 건물을 지을 수 있기 때문)

4. 끝


소스

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
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        ArrayList<Integer>[] list = new ArrayList[N + 1];
        int[] indegree = new int[N + 1];
        int[] value = new int[N + 1];
        int[] result = new int[N + 1];
        int temp = 0;
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 1; i <= N; i++) {
            value[i] = sc.nextInt();
            temp = sc.nextInt();
            while (temp != -1) {
                //indegree를 temp가 아닌 i 값으로 받아야한다.
                indegree[i]++;
                //리스트에 저장 될 temp 와 i 값도 바껴야 한다.
                list[temp].add(i);
                temp = sc.nextInt();
            }
        }
        
        //-----------입력 칸---------------------
        
        
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
                result[i] = value[i];
 
            }
        }
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                indegree[next]--;
                //자신의 건물을 짓기전 이전에 가장 오랜 시간 걸린 값을 찾아야 한다. 그래야 자신의 건물을 올리지
                result[next] = Math.max(result[next], result[current] + value[next]);
                System.out.println(next);
 
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
 
        }
        for (int i = 1; i <= N; i++) {
            System.out.println(result[i]);
        }
    }
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 14888 - 연산자 끼워넣기 (자바)  (0) 2018.02.07
[BOJ] 백준 2668 - 숫자고르기 (자바)  (0) 2018.02.07
[BOJ] 백준 2252- 줄 세우기 (자바)  (0) 2018.02.06
[BOJ] 백준 1766- 문제집 (자바)  (0) 2018.02.06
[BOJ] 백준 1267 - 핸드폰 요금 (자바)  (0) 2018.02.05
반응형

위상정렬 (Topological Sort)의 대표적인 문제


위상정렬을 안다면 쉽게 풀 수 있는 문제

indegree 방식으로 문제 해결


풀이

1. 값을 저장해준다. List를 이용하여. (ArrayList 든 LinkedList든 상관 없뜸)

2. indegree가 0인 값을 큐에 모두 집어 넣는다.

3. 큐가 빌때까지 0인 값을 하나씩 빼서 그 다음 값을 다시 큐에 집어 넣는다. (단 그때 화살표 값인 Indegree를 하나씩 줄인다.)

4. 끝


소스

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
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[] indegree = new int[N+1];
        ArrayList<Integer>[] list = new ArrayList[N+1];
        for(int i=1; i<=N; i++){
            list[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<M; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            list[x].add(y);
            indegree[y]++;
        }
        
        //-----------입력 부----------------------
        
        //Topological Sorting
        Queue<Integer> queue = new LinkedList<Integer>();
        //indegree가 0일때 큐에 넣는다. indegree는 자신을 가르키고 있는 화살표의 개수
        for(int i=1; i<=N; i++){
            if(indegree[i]==0){
                queue.add(i);
            }
        }
        while(!queue.isEmpty()){
            System.out.println(queue.peek());
            int current = queue.poll();
            
            //자신이 가르키고 있는 좌표들을 방문하여 indegree값을 -1 해주고 만약 0이라면 큐에 넣어준다.
            for(int i=0; i<list[current].size(); i++){
                int next = list[current].get(i);
                indegree[next]--;
                if(indegree[next]==0){
                    queue.add(next);
                }
            }
        }
        
    }
 
}
cs


반응형
저작자표시

'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글

[BOJ] 백준 2668 - 숫자고르기 (자바)  (0) 2018.02.07
[BOJ] 백준 1516 - 게임 개발 (자바)  (0) 2018.02.06
[BOJ] 백준 1766- 문제집 (자바)  (0) 2018.02.06
[BOJ] 백준 1267 - 핸드폰 요금 (자바)  (0) 2018.02.05
[BOJ] 백준 1697 - 숨바꼭질 (자바)  (0) 2018.02.05

+ Recent posts

티스토리툴바