벡터의 외적을 이용하여, 평면상에 세 점이 주어질때, 점들의 위치관계를 파악할 수 있다.


점 세개로 선분 두개를 만들어서 CCW를 적용했을 때, 결과가 양수라면 회전 방향이 시계 방향인 것이다.


(참고로 벡터의 외적은 교환법칙이 성립하지 않는다.)



중학 수학에 사용했던 신발끈 공식을 생각하면 기억하기 쉽다.


또한 CCW를 위와 같이 선분들이 놓여져있는 상태를 파악할 때 사용할 수도 있고, 면적을 구할때도 사용할 수 있다.



특정 다각형의 면적을 구하고자할 때, 외부의 점을 잡고 다각형 상의 두개의 점을 순차적으로 이용해서 CCW를 돌려줘서 더하고, 그 결과에


절댓값을 취한 후에 2로 나누면 넓이를 구할 수 있다.


음수 결과와 양수결과가 중간중간에 상쇄되는 것을 이용한 것이다.



아래의 코드는, 세점의 위치관계를 CCW를 이용해서 파악해보는 것이다.


점 p1, p2, p3가 차례로 입력이 주어지면, 선분 p1p2에 대해서 선분 p2p3가 어떻게 놓여 있는지 알 수 있다.


동일선상에 있으면 0을 반환하고, 반시계 방향으로 위치해있으면 1을 반환한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
 
using namespace std;
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) > 0) return 1;
    else if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) < 0) return -1;
    else
        return 0;
}
 
int main(void) {
 
    int x1, y1, x2, y2, x3, y3;
 
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
    cout << ccw(x1, y1, x2, y2, x3, y3) << '\n';
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

Counting Sort (C++)  (0) 2019.08.23
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17
선분 교차 판별  (0) 2019.08.11
시간복잡도  (0) 2019.08.10

알고리즘의 시간복잡도는 연산의 횟수를 구하는 방법이 주로 쓰인다.


통상 1억 (10^8)번읜 연산을 하면 1초가 걸린다고 생각하여 알고리즘의 수행 시간을 예측한다.


즉 n의 범위가 10000이하라고 했을 때, n^2의 알고리즘을 활용하면 최악의 경우 1초가 걸릴 수 있다는 것이다.



저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

Counting Sort (C++)  (0) 2019.08.23
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17
선분 교차 판별  (0) 2019.08.11
CCW  (0) 2019.08.10

https://www.acmicpc.net/problem/1941



오답에서 적었듯이, 일반적인 dfs로는 해결하기 까다로운 문제이다.



우선, 들어오는 입력만으로는 (y/s)여부 만으로는 그 성분의 자리가 어디인지 알 수 없다.


따라서 자리번호를 매겼다.


그리고 그 자리번호를 7개 선택해서, 뽑힌 7개의 자리번호가 인접한 상태이고, S를 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
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
#include<iostream>
#include<string>
#include<queue>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int seat[6][6];
bool isused[25];
int st = 0, arr[8], dis[6][6], map[6][6];
queue<pair<int, int> > q;
int res = 0;
bool endFlag = false;
 
void process() {
    int idx = 0;
    endFlag = false;
    for (int i = 0; i < 5; i++) { //뽑힌 학생의 자리번호 1로
        for (int j = 0; j < 5; j++) {
            if (seat[i][j] == arr[idx]) {
                map[i][j] = 1;
                idx++;
                //if (idx == 7) return; 이 구문 때문에 아래 카운트가 안먹혀서 시간낭비
            }
        }
    }
 
    int sCnt = 0;
    //소영 카운트
    for (int i = 0; i < 5; i++) 
        for (int j = 0; j < 5; j++) 
            if (map[i][j] == 1 && m[i][j] == 'S') sCnt++;
        
    
    if (sCnt < 4) endFlag = true;
}
void init() {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            map[i][j] = 0; //자리번호 배열 초기화
            dis[i][j] = -1; //방문처리 배열
        }
    
}
 
void bfs(pair<int, int> start) {
    q.push(start);
    dis[start.first][start.second]++;
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
            if (dis[nr][nc] >= 0 || map[nr][nc] != 1) continue;
            q.push({ nr, nc });
            cnt++;
            dis[nr][nc] = cnt;
        }
    }
    
    if (cnt == 6) //7명이 붙어 앉은 경우
        res++;
    
}
 
void pick(int k) {
    if (k == 7) { //1. 자리번호 7개 선택
    
        init(); 
 
        process();
        if (endFlag) return;
 
        for (int i = 0; i < 5; i++) 
            for (int j = 0; j < 5; j++) 
                if (map[i][j] == 1 && dis[i][j] < 0) 
                    bfs({ i, j }); 
        
        return;
    }
    
    if (k == 0) st = 0;
    for (int i = st; i < 25; i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            pick(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int cnt = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            cin >> m[i][j];
            seat[i][j] = cnt;
            cnt++;
        }
    
    pick(0);
    cout << res;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2166 다각형의 면적 C++  (0) 2019.08.10
백준 11758 CCW C++  (0) 2019.08.10
백준 2023 신기한 소수 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09

https://www.acmicpc.net/problem/1941


4방향 dfs 탐색을 활용해서 y가 네개 이하인 경우에만 결과에 포함시키려고 했다.


이렇게 접근하면 자리에 앉아 있는 사람이 y파인지s파인지 말고는 개별적으로 구분할 수 없기 때문에 각자 결과로 나온 문자열을 구분하지 못한다.


가령 sysysys라는 문자열은 맞는 결과이지만, 행렬에서 어떤 위치의 성분을 가져다가 저걸 만들어냈느냐에 따라서 서로 다른 문자열일 수도 있고 같은 문자열일 수도 있다.



아래는 틀린 코드이다.



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
#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
char m[6][6];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
vector<pair<int, int> > v;
set<vector<pair<int, int> > > pos;
set<string> ans;
void dfs(int k, int row, int col, string mem, int ycnt) {
    if (k == 7) {
        cout << mem << '\n';
        cout << "하나\n";
        //ans.insert(mem);
        
        return;
    }
    cout << mem << '\n';
    for (int i = 0; i < 4; i++) {
        int nr = row + dr[i];
        int nc = col + dc[i];
        if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5) continue;
        if (m[nr][nc] == 'Y' && ycnt >= 3) continue;
        
 
 
        if (m[nr][nc] == 'Y') dfs(k + 1, nr, nc, mem + m[nr][nc], ycnt + 1);
        else
            dfs(k + 1, nr, nc, mem + m[nr][nc], ycnt );
    }
    
}
 
int main(void) {
    
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> m[i][j];
 
    string tmp = "";
    
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) {
            int ycnt = 0;
            if (m[i][j] == 'Y') ycnt++;
            dfs(1, i, j, tmp+m[i][j], ycnt);
        }
    //cout << *ans.begin();
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

연산자 우선 순위가 없는 경우 +, -, * 연산 구현  (0) 2019.08.21
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24
백준 1759번: 암호 만들기 (C++)  (0) 2019.07.23
[오답] 백준 9663번: N-Queen (C++)  (0) 2019.07.21

https://www.acmicpc.net/problem/2023



자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.


가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.


처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.



신경써줄 부분은, 소수 판별 함수에서 1은 바로 소수가 아님을 반환하는 것과, 가장 큰 자리의 수가 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
/*특정 수열이 만들어질 때마다
소수 여부 판별해서, 소수 아닐 때만 이어서 진행*/
#include<iostream>
#include<vector>
using namespace std;
int n, arr[10], st = 0;
bool isPrime(int val) {
    if (val == 1) return false; //1은 소수가 아님
    for (int i = 2; i*i <= val; i++)
        if (val % i == 0) return false;
    return true;
}
void backTracking(int k, int num) {
    
    //소수검사
    if (k != 0) 
        if (!isPrime(num)) return;
    
    if (k == n) {
        cout << num << '\n';
        return;
    }
 
    //가장 큰 자리수로 0못오게
    if (k == 0)st = 1;
    else
        st = 0;
 
    for (int i = st; i <= 9; i++) 
        backTracking(k + 1, num * 10 + i);
}
int main(void) {
    cin >> n;
    backTracking(0,0);
    
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11758 CCW C++  (0) 2019.08.10
백준 1941 소문난 칠공주 C++  (0) 2019.08.10
백준 2661 좋은수열 C++  (0) 2019.08.09
백준 2210번: 숫자판 점프 (C++)  (0) 2019.08.09
백준 2589번: 보물섬 (C++)  (0) 2019.08.09

+ Recent posts

티스토리툴바