#유형 : 위상 정렬

#난이도 : 골드 4

# 큐를 통해 위상 정렬 알고리즘을 구현하면 되는 문제였다. 위상 정렬 알고리즘이란 싸이클이 허용되지 않는 가정하에 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다. 진입 차수가 0인 노드를 큐에 넣어가며 선행 처리가 끝난(진입 차수가 0이된)노드에서 방문 가능한 노드들을 차례로 방문해주며 시간을 더해주면 된다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2056 {
    static int N;
    static int cost[], arr[], pre[];
    static ArrayList<Integer> arrList[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N+1];
        arr = new int[N+1];
        pre = new int[N+1];
        arrList = new ArrayList[N+1];
        for(int i=0; i<=N; i++)
            arrList[i] = new ArrayList<>();
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i] = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            for(int j=0; j<val; j++) {
                int prev = Integer.parseInt(st.nextToken());
                arrList[prev].add(i);
                pre[i]++;
            }
        }
        
        
        bfs();
        int maxValue = 0;
        for(int i : arr) {
            maxValue = Math.max(maxValue, i);
        }
        System.out.println(maxValue);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        
        Queue<Integer> queue = new LinkedList<Integer>();
        
        // 진입 차수가 0인 노드를 큐에 넣어준다.
        for(int i=1; i<=N; i++) {
            if(pre[i] == 0) {
                queue.add(i);
                arr[i] = cost[i];
            }
        }
        
        while(!queue.isEmpty()) { 
            int num = queue.poll();
            // 진입 차수가 0 인 노드를 선행으로 갖는 노드들에 대해 수행해준다.
            for(int i=0; i<arrList[num].size(); i++) {
                int next = arrList[num].get(i);
                if(arr[next] < arr[num] + cost[next])
                    arr[next] = arr[num] + cost[next];
                if(--pre[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2473 세 용액 - Java 자바  (0) 2020.05.11
#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02

#유형 : 조합, 콤비네이션

#난이도 : 실버 2

# 수학 조합 공식 nCm => n! / (n-m)!m!

# 푸는 방식은 여러가지가 있을텐데, 재귀로 접근했지만 시간초과가 발생하고, long 타입으로도 범위를 받아들일 수 없다. 따라서 BigInteger를 사용하여 문제를 해결하면 된다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class p2407 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n,m;
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        BigInteger num1 = BigInteger.ONE;
        BigInteger num2 = BigInteger.ONE;
        for(int i=0; i<m; i++) {
            num1 = num1.multiply(new BigInteger(String.valueOf(n-i)));
            num2 = num2.multiply(new BigInteger(String.valueOf(i+1)));
        }
        
        System.out.println(num1.divide(num2));
    }
    
    
}    
 
 cs

'백준' 카테고리의 다른 글

#백준_1149 RGB거리 - Java 자바  (0) 2020.05.06
#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_11758 CCW - Java 자바  (0) 2020.05.01

#유형 : 투포인터 알고리즘

#난이도 : 골드 V

# 단순 반복문을 사용하면 아마도 시간초과가 발생할 것이다. 흔한 투포인터 문제였고, 해당 방식으로 접근하여 해결하였다. 

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class p2467 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N =Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        Point po = null;
        
        int start = 0, end = N-1;
        int val = Integer.MAX_VALUE;
        
 
        while(start < end) {
            
            int v1 = arr[start];
            int v2 = arr[end];
            
            if(Math.abs(v1+v2) < val) {
                val = Math.abs(v1+v2);
                po = new Point(start, end);
            }
            
            if(v1 + v2 < 0)
                start++;
            else
                end--;
        }
        System.out.println(arr[po.x] + " " +arr[po.y]);
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2056 작업 - Java 자바  (0) 2020.05.05
#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30

#유형 : CCW, 다각형의 넓이

#난이도 : 골드 V

#다각형의 넓이는 벡터의 외적으로 구할 수 있다 => 삼각형으로 쪼개서 외적을 누적하여 합하면 된다.

==다각형을 이루는 점 하나를 중심으로 잡고, 그 점을 중심으로 CCW를 돌리며 다각형을 삼각형으로 나누고, 삼각형의 면적을 구할 수 있다. 

방향과 관련있는 외적이기 때문에 구할 때마다 절대값을 씌우면 안되고, 마지막에 절대값을 씌워야한다.

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2166 {
    static int N;
    static Po[] p;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        p = new Po[N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            p[i] = new Po(x,y);
        }
        long res = 0;
        for(int i=2; i<N; i++) {
            res += ccw(p[1], p[i], p[i+1]);
        }
        
        res = Math.abs(res);
        if(res % 2 == 0) {
            System.out.println(res/2+".0");
        }else
            System.out.println(res/2+".5");
    }
    
    public static long ccw(Po p1, Po p2, Po p3) {
        //CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
        return ((p1.x*p2.y) + (p2.x*p3.y) + (p3.x * p1.y)) - ((p1.y*p2.x) + (p2.y*p3.x) + (p3.y*p1.x));
        
    }
    
    public static class Po{
        long x;
        long y;
        public Po(long x, long y) {
            this.x=x;
            this.y=y;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2407 조합 - Java 자바  (0) 2020.05.04
#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30
#백준_1865 웜홀 - Java 자바  (0) 2020.04.28

#유형 : 벡터의 외적, CCW

#난이도 : 골드 V

# CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)을 활용하여 쉽게 해결할 수 있던 문제.

# CCW는 Counter Clockwise의 약자로써, 평면 위에 놓여진 세 점의 방향관계를 구할 수 있는 알고리즘입니다.

먼저 한 줄로 요약하자면, CCW는 점 를 순서대로 봤을때 반시계방향으로 놓여 있으면 양수를, 시계방향이면 음수를, 평행하게 놓여있으면 0을 반환하게 됩니다.

 

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p11758 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Point[] po = new Point[3];
        StringTokenizer st;
        
        for(int i=0; i<3; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            po[i] = new Point(x,y);
        }
        
        
        System.out.println(ccw(po));
    }
    
    public static int ccw(Point[] p) {
        //CCW 공식 (x1y2+x2y3+x3y1)−(y1x2+y2x3+y3x1)
        // CCW는 점 A,B,C를 순서대로 봤을때 반시계방향으로 놓여 있으면 양수를, 시계방향이면 음수를, 평행하게 놓여있으면 0을 반환하게 됩니다.
        int result = ((p[0].x*p[1].y) + (p[1].x*p[2].y) + (p[2].x * p[0].y)) - ((p[0].y*p[1].x) + (p[1].y*p[2].x) + (p[2].y*p[0].x));
        if(result < 0)
            return -1;
        else if(result > 0)
            return 1;
        else
            return 0;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2467 용액 - Java 자바  (0) 2020.05.03
#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30
#백준_1865 웜홀 - Java 자바  (0) 2020.04.28
#백준_16593 A → B - Java 자바  (0) 2020.04.27

#유형: 최단경로, 다익스트라

#난이도: 골드 V

# 우선순위큐를 바탕으로 다익스트라 알고리즘을 구현하면 된다. 보통  A번째 도시에서 B번째 도시까지 가는데 드는 최소비용은 최단거리 문제이며, 정점을 기준으로 다익스트라인지 플로이드와샬인지, 음수 포함여부에 따라 벨만포드 등으로 나뉘어진다.

이 문제는 다익스트라 문제이며, 우선순위큐를 이용해 풀었고 주석을 달아놓았다.

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class p1916 {
    static int N,M;
    static ArrayList<Point>[] arrList;
    static int dist[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        arrList = new ArrayList[N+1];
        dist = new int[N+1];
        for(int i=1; i<=N; i++)
            dist[i] = 987654321;
        for(int i=1; i<=N; i++) {
            arrList[i] = new ArrayList<>();
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            arrList[u].add(new Point(v, value));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        solve(start);
        System.out.println(dist[end]);
    }
    
    public static void solve(int start) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(start, 0));
        dist[start] = 0;
        
        while(!pq.isEmpty()) {
            Point po = pq.poll();
            if(dist[po.x] < po.y)
                continue;
            
            // 현재 인덱스와 연결 된 모든 버스 확인
            for(int i=0; i<arrList[po.x].size(); i++) {
                Point p = arrList[po.x].get(i);
                // start 에서 p.x 도시 까지 가는 최단거리 갱신
                if(dist[p.x] > dist[po.x] + arrList[po.x].get(i).y) {
                    dist[p.x] = dist[po.x] + arrList[po.x].get(i).y;
                    pq.add(new Point(p.x, dist[p.x]));
                }
            }
        }
        
    }
    
    
    public static class Point implements Comparable<Point>{
        int x;
        int y;
        public Point(int x, int y) {
            this.x=x;
            this.y=y;
        }
        // 우선순위큐에서 가까운 값이 우선순위로 계산되게 하는 
        @Override
        public int compareTo(Point o) {
            if(this.y - o.y < 0)
                return 1;
            else
                return 0;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2166 다각형의 면적 - Java 자바  (0) 2020.05.02
#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1865 웜홀 - Java 자바  (0) 2020.04.28
#백준_16593 A → B - Java 자바  (0) 2020.04.27
#백준_1600 말이 되고픈 원숭이 - Java 자바  (0) 2020.04.26

#유형 : SPP, 벨만 포드

#난이도 : 골드 4

#  음수 사이클이 존재하는지 체크하는 문제이다. 있으면 YES 출력, 아니면 No 출력이다.  => 문제 조건에 비용이 음수인 경로가 존재한다(웜홀) 따라서 벨만포드 알고리즘(음의 사이클 체크 가능)으로 접근하면 된다. 아래의 벨만포드 알고리즘 특성 1번인 V-1개의 간선만 사용할 수 있다를 활용한다면, V-1번의 반복문을 돌고난 후에도 최단경로가 발생된다면(cnt >= N) 음의 가중치, 즉 웜홀을 통해 시간이 되돌아가는 경우 => 문제에서 요구하는 바이다. 또한 2번 특성도 활용하여 업데이트가 되는 노드가 없으면 반복문을 종료한다.

 

** 벨만포드 알고리즘 특성 **

1.최단 경로는 사이클을 포함할 수 없다. 따라서 최대 |V|-1개의 간선만 사용할 수 있다. 
2.최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해준다. 이때 만약 음의 값을 가지고 있는 간선으로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 

 

** 최단 경로를 구하는 SPP 알고리즘인 다익스트라에서는 그리디 기법을 기반으로 하기 때문에 추후에 가중치가 감소하는 음수 가중치에 대해서는 처리를 못하였다.

** 하지만 벨만포드 알고리즘은 그것을 보완한 방식으로써 음의 가중치를 계산할 수 있다. 그러나 모든 정점에서 간선을 다 보아야 하기 때문에 시간 복잡도가 높다.

 

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
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p1865 {
    static int tc, N, M, W;
    static ArrayList<Point>[] arrList;
    static int dist[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        for(int t=1; t<=tc; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            
            arrList = new ArrayList[N+1];
            dist = new int[N+1];
            
            for(int i=0; i<=N; i++)
                dist[i] = 987654321;
            
            for(int i=0; i<=N; i++)
                arrList[i] = new ArrayList<>();
            
            //도로의 정보
            for(int i=0; i<M; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int time = Integer.parseInt(st.nextToken());
                arrList[start].add(new Point(end, time));
                arrList[end].add(new Point(start, time));
            }
            //웜홀의 정보
            for(int i=0; i<W; i++) {
                st = new StringTokenizer(br.readLine());
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int time = Integer.parseInt(st.nextToken());
                arrList[start].add(new Point(end, -time));
            }
            
            boolean isPossible = true;
            dist[1] = 0;
            int cnt = 0;
            
            // cnt 가 N과 같거나 N보다 크다면 음의 사이클이 존재하는 것이다 && 더이상 업데이트가 없으면 종료한다.
            while(isPossible && cnt < N) {
                isPossible = false;
                cnt++;
                for(int v=1; v<=N; v++) {
                    for(Point po : arrList[v]) {
                        if(dist[v] + po.y < dist[po.x]) {
                            dist[po.x] = dist[v] + po.y;
                            isPossible = true;
                        }
                    }
                }
            }
            if(cnt == N)
                System.out.println("YES");
            else
                System.out.println("NO");
            
        }
        
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_11758 CCW - Java 자바  (0) 2020.05.01
#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30
#백준_16593 A → B - Java 자바  (0) 2020.04.27
#백준_1600 말이 되고픈 원숭이 - Java 자바  (0) 2020.04.26
#백준_13549 숨바꼭질 3 - Java 자바  (0) 2020.04.25

#유형 : 그래프 탐색, BFS

#난이도 : 골드 V

# 맨처음엔 그냥 boolean 형 배열로 통해 접근하려했으나, 10^9 값때문에 메모리 초과가 발생했다. 따라서 HashMap 자료구조를 활용하여 접근하여 해결하였다. 이 때 val 접근을 int 로 하면 끝에 1을 붙이는 연산으로 자료형 오류가 발생, 즉 런타임오류가 발생한다. 따라서 long 타입으로 접근하여 해결하면 된다.

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p16953 {
    static int A,B;
    static HashMap<Long, Integer> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        int val = bfs();
        if(val == -1)
            System.out.println(val);
        else
            System.out.println(val+1);
        
    }
    public static int bfs() {
        
        Queue<Po> queue = new LinkedList<Po>();
        queue.add(new Po(A,0));
        while(!queue.isEmpty()) {
            Po p = queue.poll();
//            System.out.println(po.x + " " +po.y);
            if(p.val == B) {
                return p.cnt;
            }
            if(p.val * 2 <= B && !map.containsKey(p.val*2)) {
                map.put(p.val*2, p.cnt+1);
                queue.add(new Po(p.val*2, p.cnt+1));
            }
            if(p.val*10 + 1 <= B && !map.containsKey(p.val*10 +1)) {
                map.put(p.val*10 + 1, p.cnt+1);
                queue.add(new Po(p.val*10 + 1, p.cnt+1));
            }
        }
    
        return -1;
    }
    public static class Po{
        long val;
        int cnt;
        public Po(long v, int c) {
            this.val=v;
            this.cnt=c;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1916 최소비용 구하기 - Java 자바  (0) 2020.04.30
#백준_1865 웜홀 - Java 자바  (0) 2020.04.28
#백준_1600 말이 되고픈 원숭이 - Java 자바  (0) 2020.04.26
#백준_13549 숨바꼭질 3 - Java 자바  (0) 2020.04.25
#백준_12851 숨바꼭질 2 - Java 자바  (0) 2020.04.24

+ Recent posts

티스토리툴바