BOJ : https://www.acmicpc.net/problem/2098

github : https://github.com/junho0956/Algorithm/blob/master/2098/2098/%EC%86%8C%EC%8A%A4.cpp

 

BOJ 10971번 외판원 순회2 (https://junho0956.tistory.com/172)을 통해 풀이하였습니다. 

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
#define INT_MAX 99999999
 
int arr[16][16];
int dp[16][1 << 16];
int N, visit_check;
 
int TSP(int start, int visit) {
    if (visit == visit_check) {
        if (arr[start][0] == 0) return INT_MAX;
        else return arr[start][0];
    }
 
    int& result = dp[start][visit];
    if (result) return result;
 
    int len = INT_MAX;
    for (int i = 1; i < N; i++) {
        if (arr[start][i] != 0 && (visit & (1 << i)) == 0)
            len = min(len, arr[start][i] + TSP(i, visit | (1 << i)));
    }
 
    return result = len;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
 
    visit_check = (1 << N) - 1;
 
    cout << TSP(0, 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 12781번 PIZZA ALVOLOC  (0) 2020.02.02
BOJ 16991번 외판원 순회3  (0) 2020.02.02
BOJ 10971번 외판원 순회2  (0) 2020.02.02
BOJ 12813번 이진수 연산  (0) 2020.02.02
BOJ 2143번 두 배열의 합  (0) 2020.02.02

BOJ : https://www.acmicpc.net/problem/10971

github : https://github.com/junho0956/Algorithm/blob/master/10971/10971/%EC%86%8C%EC%8A%A4.cpp

 

TSP, 외판원 순회는

한 정점에서 모든 정점을 중복없이 방문하고 다시 첫 정점으로 되돌아오는 최단거리를 의미합니다

 

일반적으로 TSP를 해결하기 위해서는 정점이 N 개일때 N! 이라는 시간이 필요하게 됩니다.

이 문제에서는 정점이 최대 10개이기 때문에 10! = 3628800번의 시간복잡도가 필요하게 됩니다.

시간제한도 2초이기 때문에 완전탐색으로 10! 으로 문제를 해결할수도 있습니다

하지만 정점이 커질수록 TLE 가 될수밖에 없기 때문에 제대로된 방법을 알아보겠습니다

(2098번 외판원 순회 https://www.acmicpc.net/problem/2098 의 경우 16! = 20조이상의 시간복잡도가 필요하게됩니다)

 

먼저 외판원을 순회할때의 시작정점은 어떤 정점이든 상관없습니다.

방향트리를 가정하고 있기 때문에 시작정점에 따라 값이 다를 수 있다 생각할 수 있는데,

결국 최단거리인 TSP를 찾게되면 그 정점들은 사이클이 생기기 때문입니다

(ex 1 -> 2 -> 3 == 2->3->1 == 3->1->2) 

 

알고리즘 수업시간 때 배운 TSP에 대해서 설명해보겠습니다.

TSP는 시간복잡도를 줄이기 위해서 동적계획법에 의한 계산을 하게 됩니다

 

기본적인 DP의 점화식은 다음과 같습니다

위에서 시작정점은 어디든 상관없다고 말씀드렸으니, 시작정점은 1이라고 가정하고

{V} 를 방문하지 않은 정점이라고 가정하겠습니다.

"dp[i][{V} 의 의미는 정점 i 에서 출발해서 아직 방문하지 않은 정점집합V 를 거쳐 정점 1로 되돌아오는 최단거리"

를 의미하게 됩니다.

 

결국 dp[v1][{V-v1}] = min (2<=j<=k) (cost[1][j]+DP[j][{V-v1,vj}] 라는 점화식을 만들 수 있게 됩니다.

 

하지만 이 DP는 단순하게 구현하려면 엄청나게 많은 메모리가 필요하게 됩니다.

정점 1 2 3 4 5 가 있을 때

정점 1에서 출발하여 만들어볼 수 있는 DP는

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

1 2 5 4 3

1 3 . . .

이렇게 DP는 어떤 정점에서 어떤 정점을 거쳤는지에 대한 순서와 값들을 알고 있어야되는 것입니다

 

이걸 단순히 배열로만 다 표현하려면 엄청나게 많은 메모리가 들 수 밖에 없습니다

그렇기때문에 이 순서들을 DP로 표현하기 위해서는 비트마스킹을 이용해야 합니다

그렇게되면 좀더 수월하게 이 집합의 순서와 값들을 유지하면서 DP를 계산할 수 있습니다

 

풀이과정은 다음과 같습니다.

배열은 최대정점이 N일때 1<<N 의 크기가 필요하다

현재 출발하려는 정점이 start 이고, 지금까지 방문한 정점들의 순서를 비트마스킹을 이용해서 visit으로 표현한다

비트마스킹 visit이 모든정점을 방문했다면 현재 도착한 마지막 정점에서 정점1로 가는 값을 반환합니다

모든 정점을 방문하지 않았다면 현재까지 정점에 대한 DP 값을 확인합니다

만약 DP 가 초기값이 아니라면, 이는 이미 이 순서에 대한 최단거리를 가지고 있는 것이므로 반환합니다

만약 DP 가 초기값이라면, 현재 정점부터 정점1을 제외한 방문할 수 있는 모든 정점을 확인합니다

 

비트마스킹으로 풀이하면, 현재 방문한 값과 순서는 visit에 담겨있습니다

정점 i 를 방문했는지 확인하는 방법

-> (visit & (1<<i)) == 0 이면 방문하지않음, ==1 이면 방문함

다음 방문할 정점에 대해 지금까지 방문한 값 visit을 갱신하는 방법

-> (visit | (1<<i)

 

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
#include <iostream>
#include <algorithm>
using namespace std;
 
#define INT_MAX 99999999
 
int arr[10][10];
int dp[10][1 << 10];
int N, visit_check;
 
int TSP(int start, int visit) {
    if (visit == visit_check) {
        if (arr[start][0] == 0) return INT_MAX;
        else return arr[start][0];
    }
 
    int& result = dp[start][visit];
    if (result) return result;
 
    int len = INT_MAX;
    for (int i = 1; i < N; i++) {
        if (arr[start][i] != 0 && (visit&(1 << i)) == 0)
            len = min(len, arr[start][i] + TSP(i, visit | (1 << i)));
    }
 
    return result = len;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
 
    visit_check = (1 << N) - 1;
 
    cout << TSP(0, 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 16991번 외판원 순회3  (0) 2020.02.02
BOJ 2098번 외판원 순회  (0) 2020.02.02
BOJ 12813번 이진수 연산  (0) 2020.02.02
BOJ 2143번 두 배열의 합  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02

BOJ : https://www.acmicpc.net/problem/12813

github : https://github.com/junho0956/Algorithm/blob/master/12813/12813/%EC%86%8C%EC%8A%A4.cpp

 

문제에서 요구하는 그대로 구현해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#pragma warning(disable:4996)
#define len 100000
 
int main() {
    
    int a[len], b[len];
    for (int i = 0; i < len; i++) scanf("%1d", &a[i]);
    for (int i = 0; i < len; i++) scanf("%1d", &b[i]);
 
    for (int i = 0; i < len; i++) printf("%d", a[i] & b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] | b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] ^ b[i]);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", a[i] ? 0 : 1);
    printf("\n");
    for (int i = 0; i < len; i++) printf("%d", b[i] ? 0 : 1);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2098번 외판원 순회  (0) 2020.02.02
BOJ 10971번 외판원 순회2  (0) 2020.02.02
BOJ 2143번 두 배열의 합  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02

BOJ : https://www.acmicpc.net/problem/2143

github : https://github.com/junho0956/Algorithm/blob/master/2143/2143/%EC%86%8C%EC%8A%A4.cpp

 

정올 2001 고등부1번 문제입니다

 

이 문제는 따로 떨어져 있는 경우도 되는 것이 아닌

'부배열' = 연속된 값들로만 해결해야 하는 문제입니다.

makeA, makeB 함수는 연속된 부분집합의 합을 구하는 함수이고, 범위는 1000이기 때문에 충분히 완탐으로 해결됩니다

 

그후에 이분탐색을 이용해서 경우의 수를 구해주시면 됩니다.

 

 

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> va, vb;
int ans, n, m;
int a[1001];
int b[1001];
 
void makeA(int idx, int len) {
    if (idx + len > n) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += a[i];
    va.push_back(sum);
    makeA(idx, len + 1);
}
 
void makeB(int idx, int len) {
    if (idx + len > m) return;
 
    int sum = 0;
    for (int i = idx; i < idx + len; i++) sum += b[i];
    vb.push_back(sum);
    makeB(idx, len + 1);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> ans >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++) cin >> b[i];
 
    for (int i = 0; i < n; i++) makeA(i, 1);
    for (int i = 0; i < m; i++) makeB(i, 1);
 
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
 
    long long cnt = 0;
    for (int i = 0; i < va.size(); i++) {
        int res = ans - va[i];
        int l = lower_bound(vb.begin(), vb.end(), res) - vb.begin();
        int u = upper_bound(vb.begin(), vb.end(), res) - vb.begin();
        cnt += u - l;
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10971번 외판원 순회2  (0) 2020.02.02
BOJ 12813번 이진수 연산  (0) 2020.02.02
BOJ 3474번 교수가 된 현우  (0) 2020.02.02
BOJ 2632번 피자판매  (0) 2020.02.02
BOJ 7453번 합이 0인 네 정수  (0) 2020.02.01

+ Recent posts

티스토리툴바