#유형 : 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

MYSQL의 DATE_FORMAT(값, 형식)을 사용하면 된다. 서브스트링을 써도 해결할 수 있다.

1
2
3
4
-- DATETIME에서 DATE로 형 변환
SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME, '%Y-%m-%d') AS '날짜'
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC`
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_문자열 압축 - Java 자바  (0) 2020.05.24
#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)  (0) 2020.05.07
#프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2)  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 중성화 여부 파악하기  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 이름에 el이 들어가는 동물 찾기  (0) 2020.04.28

Join 문을 사용해서 병합한 다음, OUTS테이블의 DATETIME - INS테이블의 DATETIME을 뺀 값중 큰 값들을 내림차순으로 정렬하면 된다.

1
2
3
4
5
-- 오랜 기간 보호한 동물(2)
SELECT I.ANIMAL_ID, I.NAME
FROM ANIMAL_INS I LEFT JOIN ANIMAL_OUTS O ON I.ANIMAL_ID = O.ANIMAL_ID
ORDER BY O.DATETIME - I.DATETIME DESC
LIMIT 2
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_길찾기 - Java 자바(2019 KAKAO BLIND RECRUITMENT)  (0) 2020.05.07
#프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 중성화 여부 파악하기  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 이름에 el이 들어가는 동물 찾기  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 루시와 엘라찾기  (0) 2020.04.28

특정한 값에 대하여 다른 값을 매칭시키기 위해 switch문 하고 비슷한 CASE를 사용하였다. 

CASE 

WHEN SEX_UPON_INTAKE like '%Neutered%' or  SEX_UPON_INTAKE like '%Spayed%' THEN 'O'

ELSE 'X' END 이런식으로 사용해주면 된다.

1
2
3
4
5
6
-- 중성화 여부 파악하기
SELECT ANIMAL_ID, NAME, CASE
WHEN SEX_UPON_INTAKE like '%Neutered%' or  SEX_UPON_INTAKE like '%Spayed%' THEN 'O'
ELSE 'X' END AS '중성화'
FROM ANIMAL_INS
 
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_SQL_String, Date - DATETIME에서 DATE로 형 변환  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2)  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 이름에 el이 들어가는 동물 찾기  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 루시와 엘라찾기  (0) 2020.04.28
#프로그래머스_SQL_Join - 보호소에서 중성화한 동물  (0) 2020.04.27

WHERE like '%문자%' 를 통해 해결할 수 있다.

1
2
3
4
5
-- 이름에 el이 들어가는 동물 찾기
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE NAME like '%EL%' and ANIMAL_TYPE = 'Dog'
ORDER BY NAME ASC
 cs

'프로그래머스' 카테고리의 다른 글

#프로그래머스_SQL_String, Date - 오랜 기간 보호한 동물(2)  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 중성화 여부 파악하기  (0) 2020.04.28
#프로그래머스_SQL_String, Date - 루시와 엘라찾기  (0) 2020.04.28
#프로그래머스_SQL_Join - 보호소에서 중성화한 동물  (0) 2020.04.27
#프로그래머스_SQL_Join - 오랜 기간 보호한 동물(1)  (0) 2020.04.27

+ Recent posts

티스토리툴바