반응형

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


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

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

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


두 문제 똑같이 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
반응형

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


위상정렬을 처음 이해하고 문제를 푸는데 어려웠다. 머리속에 문제를 이해는 했는데 코드는 잘 안짜지는 느낌?


풀이

1. 값을 저장해준다. List를 이용하여. 

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

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

4. 끝


의 과정 반복이다.

문제가 안풀리면 위상정렬을 공부하고 다시 보면 될것이다.

맞다. 이문제는 PriorityQueue를 사용해야한다. 왜냐하면 Queue에 같이 들어있을 때, 쉬운문제(번호가 작은 순)으로 풀어야 하기 때문

Queue를 사용하면 선입선출이기 때문에 값이 다르게 나온다.


소스

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.FileInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
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];    //LinkedList 사용해도 상관 없음
        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]++;    //자신을 가르키고 있는 화살표의 갯수
        }
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        
        for(int i=1; i<=N; i++){
            //indegree가 0인 값들 모두 큐에 넣어준다.
            if(indegree[i]==0){
                q.add(i);
            }
        }
        while(!q.isEmpty()){
            //indgree가 0인 값을 큐에서 뽑는다.
            int current = q.poll();
            System.out.print(current+" ");
            //뽑힌 곳에서 갈 수 있는 곳들을 검색하여 indegree를 -1한다.(자신을 가르키는 화살표가 하나 사라졌기 때문에)
            for(int i=0; i<list[current].size(); i++){
                int next = list[current].get(i);
                indegree[next]--;
                //indegree가 0이라면 큐에 넣는다.
                if(indegree[next]==0){
                    q.add(next);
                }
            }
        }
    }
 
}
cs


반응형
저작자표시 (새창열림)

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

[BOJ] 백준 1516 - 게임 개발 (자바)  (0) 2018.02.06
[BOJ] 백준 2252- 줄 세우기 (자바)  (0) 2018.02.06
[BOJ] 백준 1267 - 핸드폰 요금 (자바)  (0) 2018.02.05
[BOJ] 백준 1697 - 숨바꼭질 (자바)  (0) 2018.02.05
[BOJ] 백준 2979 - 트럭 주차 (자바)  (0) 2018.02.03
반응형

설명도 필요없는 문제

근데 합격률이 극악인 이유는 문제가 제대로 명시되지 않았기 때문에...

동점일 경우 어떻게 출력되어야 하는지 나와있지 않음.


풀이

1. 영식이는 30분 마다 이므로 나누기 30 으로 계산 후 10원 청구이므로 곱하기 10

1. 민식이는 60분 마다 이므로 나누기 60 으로 계산 후 15원 청구이므로 곱하기 15

끝


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K;
        int YoungSik = 0, MinSik = 0;
        for (int i = 0; i < N; i++) {
            K = sc.nextInt();
            YoungSik += ((K / 30) + 1) * 10;
            MinSik += ((K / 60) + 1) * 15;
 
        }
        if (YoungSik == MinSik) {
            System.out.println("Y M " + YoungSik);
        } else if (YoungSik < MinSik) {
            System.out.println("Y " + YoungSik);
        } else if (YoungSik > MinSik) {
            System.out.println("M " + MinSik);
        }
    }
}
cs


반응형
저작자표시 (새창열림)

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

[BOJ] 백준 2252- 줄 세우기 (자바)  (0) 2018.02.06
[BOJ] 백준 1766- 문제집 (자바)  (0) 2018.02.06
[BOJ] 백준 1697 - 숨바꼭질 (자바)  (0) 2018.02.05
[BOJ] 백준 2979 - 트럭 주차 (자바)  (0) 2018.02.03
[BOJ] 백준 1012 - 유기농 배추 (자바)  (0) 2018.02.03
반응형

BFS? DFS?


알고리즘 분류에는 DFS도 나와있는데, DFS로는 어떻게 풀지 모르겠다. 

DFS로 푸니까 스택오버플로우가.....................................

므즈건 BFS로 푸는게 나을거 같다.


풀때는 굉장히 어려운 문제였는데 풀고나니까 쉬워보인다. 그렇게 어려운 문제는 아님;


풀이

1. 다음에 이동할 위치 앞으로 한칸 (+1), 뒤로 한칸 (-1), 순간이동 (x2) 을 생각해준다.

2. 조건에 맞는지 확인한다. 조건이란 배열을 벗어나지 않았는지, 이전에 방문했던점이 아닌지 이다. 모든 배열을 -1로 놓고 변하지 않았다면 이동 X

선입선출이므로 해당 위치에 먼저 도착한놈이 무조건 빠르거나 같다. (이동 횟수가 작다) 그렇기 때문에 이전에 방문했던점이면 굳이 갈 필요가 없다.

나는 이조건에서 헤맴..

3. 조건에 맞다면 이동할 위치 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
import java.util.Arrays;
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(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] Min = new int[100005];
        Arrays.fill(Min, -1);    //초기값을 다 -1로 설정
        System.out.println(BFS(N, K, Min));
 
    }
 
    public static int BFS(int N, int K, int[] Min) {
        int nextN = N;
        int[] status = new int[3];
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(nextN);
        Min[nextN] = 0;
 
        while (!q.isEmpty() && nextN != K) {
 
            nextN = q.poll();
            //다음에 이동할 좌표들
            status[0] = nextN - 1;     //뒤로 한칸
            status[1] = nextN + 1;    //앞으로 한칸
            status[2] = nextN * 2;    //순간이동
 
            for (int i = 0; i < 3; i++) {
                //배열을 벗어나지 않았는지 확인
                if (status[i] >= 0 && status[i] <= 100000) {
                    //이전에 방문했는지 확인
                    if (Min[status[i]] == -1) {
                        //처음 간 곳이라면 큐에 넣고 상태를 전 위치값 +1 을 해준다.
                        q.add(status[i]);
                        Min[status[i]] = Min[nextN] + 1;
 
                    }
                }
            }
        }
        return Min[K];
    }
}
cs


반응형
저작자표시 (새창열림)

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

[BOJ] 백준 1766- 문제집 (자바)  (0) 2018.02.06
[BOJ] 백준 1267 - 핸드폰 요금 (자바)  (0) 2018.02.05
[BOJ] 백준 2979 - 트럭 주차 (자바)  (0) 2018.02.03
[BOJ] 백준 1012 - 유기농 배추 (자바)  (0) 2018.02.03
[BOJ] 백준 1475 - 방 번호 (자바)  (0) 2018.01.30

+ Recent posts

티스토리툴바