<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
int isVisited[101];
int N;
vector<int> adj[101];
int ans[101][101];
void dfs(int, int);
int main()
{
    int tmp;
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
        {
            scanf("%d", &tmp);
            if (tmp)
                adj[i].push_back(j);
        }
    for (int i = 1; i <= N; ++i)
    {
        memset(isVisited,0,sizeof(isVisited));
        isVisited[i] = 1;
        dfs(i,i);
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j)
            printf("%d ", ans[i][j]);
        printf("\n");
    }
}
void dfs(int r,int i)
{
    int s = adj[i].size();
    for (int k = 0; k < s; ++k)
    {
        int toi = adj[i][k];
        ans[r][toi] = 1;
        if (!isVisited[toi])
        {
            isVisited[toi] = 1;
            dfs(r, toi);
        }
    }
}
 
cs


<풀이>

각 노드를 시작점으로 모두 dfs를 돌렸다. 한 번 방문한 노드는 다시 볼 필요가 없다.

dfs의 인자로 시작점을 계속해서 넘겨주고 [시작점][현재노드]=1 로 갱신시켰다.



저작자표시

'알고리즘 풀이 > DFS' 카테고리의 다른 글

백준 10819 차이를 최대로  (0) 2018.07.27
백준 10974 모든 순열  (2) 2018.07.24
KOITP 큰수만들기  (0) 2018.07.23
백준 11724 연결 요소의 개수 :: 들짐승  (0) 2018.07.23
백준 1240 노드사이의 거리 ::들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
queue<int> q;
vector<pair<int, int>> adj[10001];
int s, d;
int bfs(int);
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    scanf("%d%d", &s, &d);
    int ans = 0;
    int l = 1, r = 1000000000;
    int m;
    while (l <= r)
    {
        m = (l + r) / 2;
        int to = bfs(m);
        if (to) {
            if (ans < m)
                ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d", ans);
}
int bfs(int weight)
{
    int isVisited[10001] = { 0, };
    q = queue<int>();
    isVisited[s] = 1;
    q.push(s);
    
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (cur == d)
            return 1;
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int to = adj[cur][i].first;
            int cost = adj[cur][i].second;
            if (!isVisited[to] && cost >= weight)
            {
                isVisited[to] = 1;
                q.push(to);
            }
        }
    }
    return 0;
}
    
 
cs


<풀이>

이분탐색 + BFS문제이다.

A도시에서 B도시까지 넘겨줄 수 있는 최대중량을 이분탐색으로 찍는다.

이분탐색은 답을 찍어볼 때 굉장히 유용하다는 것을 다시 한번 느꼈다.


2018/07/22 - [알고리즘 풀이/이분탐색] - 백준 3079 입국심사 :: 들짐승


찍는 값의 범위는 1~1000000000 이다.

찍은 값으로 BFS를 돌린다. 

현재 노드와 인접해있고, 방문하지 않았으며, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 넘어갈 수 있으므로 큐에 넣어준다.

도착지가 발견되면 더이상 가지를 뻗을 필요가 없으므로 리턴한다.

이 때, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 이라는 조건 때문에 도착지를 발견못하고 큐가 비어버렸을 때는

0을 리턴해주고,

도착지를 찾은 경우 1을 리턴한다.


● 0이 리턴된 경우 : 찍어봤던 중량을 더 줄여봐야하기 때문에 right=mid-1

● 1이 리턴된 경우 : 찍어봤던 중량이 가능하다는 뜻이므로 최적의 값을 찾기 위해 더 큰 중량으로 실행해본다. left=mid+1

이 때, 정답을 갱신한다.


<시간복잡도>

이분탐색시간 :

 


BFS시간 : 인접리스트로 구현했기 때문에


따라서 최대 3300,000 이 걸리기 때문에 1초 안에 가능하다.

 



저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2018.08.30
백준 13423 Three Dots  (0) 2018.08.02
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

한번 나왔던 기울기에 속하는 좌표는 다시는 보일수없다
x/y 가 기울기이다. 

예를 들면 x가 2, y가 8일때 기울기는 2/8이 되는데 이는 이미 1/4에서 나왔기 때문에 보일수없다. 
x가 3, y가 5일때는 같은 기울기가 나왔을 수 없기 때문에 보인다. 


정리하면 
1/y 
2/y 
... 
y/y 
중에서 좌표끼리 분수를 만들고 약분되면 그 좌표는 보일 수가 없다.  
이전에 이미 같은 기울기가 나왔다는 뜻이기 때문이다. 
따라서 분모와 분자의 최대공약수가 1일때만 더해나가면된다.


<소스코드>

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
#include<stdio.h>
int ans[1001] = { 0,2 };
int gcd(int, int);
int main()
{
    for (int i = 2; i <= 1000; ++i)
    {
        int n = 0;
        for (int j = 1; j <= i; ++j)
        {
            if (gcd(i, j) == 1)
                ++n;
        }
        ans[i] = ans[i - 1] + n;
    }
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        printf("%d\n", ans[N] * 2 - 1);
    }
}
int gcd(int a, int b)
{
    while (a%b != 0)
    {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return b;
}
cs


저작자표시

'알고리즘 풀이 > 기타' 카테고리의 다른 글

백준 10973 이전 순열  (0) 2018.07.24
백준 10972 다음 순열  (1) 2018.07.24
백준 9011 순서 :: 들짐승  (1) 2018.07.22
백준 8982 수족관1 :: 들짐승  (0) 2018.07.22
백준 5624 좋은 수 :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

그냥 무작정 찍기로 총 걸린 시간을 찍는다. 이 때 이분탐색으로 찍는다.
최대시간은 제일 오래걸리는 심사대*인원수 이다. (초기 right 값)

l=1  
r=60 
mid  = 30 
tot = 30/7 + 30/10 = 7 //총 걸린시간으로 몇명이 지나갔는지 확인 ( 30분동안 최대 몇명이 지나갈수있는가 ) 
->몫만 있으면 됨 
이시간안으로는 총인원이 턱도없으면 
시간을 늘려줘야되고 

총인원보다 많은인원을 통과시킬수있으면 시간을 줄이고 
총인원보다 같더라도 시간을 줄여봐야한다. 왜냐하면 어느게이트에 갔냐에 따라서 시간이 더 줄어들수있기 때문 


right= 29 
left=1 
mid=15 
tot=15/7+15/10=3 //모자름 

r=29 
l=16 
m=22 
tot=22/7+22/10 = 5 //모자름 

r=29 
l=23 
m=26 
tot=26/7+26/10=5 //모자름 

r=29 
l=27 
m=28 
tot=28/7+28/10=6 //충분 

r=27 
l=27 
m=27 
tot=27/7+27/10=5 // 모자름 

●이분탐색 : 답을 찍어보는 경우에 사용된다
●이분탐색 다음 타겟 정하기 : 

최적의 해를 구하는 과정에서 
내가 구한값이 너무 작으면 더큰게 필요하니까 left=mid+1 해주고 
구한값이 너무 크면 더 작은게 필요하니까 right=mid-1 해주고 
구한값으로 만족하다면 ? (==일때는) -> 최적의해가 최소값이라면 right=mid-1 해서 더 줄여서 시도해본다. 
최적의 해가 최대값이라면 left=mid+1 해주면된다. 
어차피 이분탐색은 반복되더라도 l<=r일때까지만 하고 logN의 시간복잡도이기 때문에 끝까지 가봐도 시간이 충분하다.

저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2018.08.30
백준 13423 Three Dots  (0) 2018.08.02
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23

<링크>

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


<풀이>

해시맵을 하나 만들고
key=책이름
value=등장한 횟수


이미 해시맵에 키가 있으면 등장횟수를 올려주고
없으면 새로 집어넣으면서 횟수를 1로 맞춤

나중에 등장횟수를 쭉 비교하면서 max값을 찾는데, 이 때 max값과 같은애가 등장하면
책이름을 비교하여 오름차순으로 더 앞선 놈을 답으로 결정한다.


<소스코드>


1
2
3
4
5
6
7
8
9
10
String s;
s=br.readLine();
if(!hm.containsKey(s)){
    hm.put(s, 1);
}
else {
    int n=hm.get(s);
    hm.remove(s);
    hm.put(s, n+1);
}
cs


저작자표시

'알고리즘 풀이 > 라이브러리' 카테고리의 다른 글

백준 10820 문자열 분석 :: 들짐승  (0) 2018.07.22
백준 11580 Footprint :: 들짐승  (0) 2018.07.22

+ Recent posts

티스토리툴바