#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
 
int solution(vector<int> arrows) 
{
    int roomCnt = 0;
    map<pair<int, int>, int> vertex_visited;
    map<pair<pair<int, int>, pair<int, int>>, int> edge_visited;
 
    int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
    
    int x = 0;
    int y = 0;
    vertex_visited[{x, y}] = 1;
    for(int i = 0; i < arrows.size(); i++)
    {
        // X자의 교차 형태도 세줘야해서 2배
        for(int j = 0; j < 2; j++)
        {
            int xpos = x + dx[arrows[i]];
            int ypos = y + dy[arrows[i]];
            
            if(vertex_visited[{xpos, ypos}] == 1)
            {
                if(edge_visited[{{x, y}, {xpos, ypos}}] == 0 || edge_visited[{{xpos, ypos}, {x, y}}] == 0)
                {
                    roomCnt++;
                }
            }
 
            // vertex 체크
            vertex_visited[{xpos, ypos}] = 1;
            
            // edge 체크
            edge_visited[{{x, y}, {xpos, ypos}}] = 1;
            edge_visited[{{xpos, ypos}, {x, y}}] = 1;
            
            x = xpos;
            y = ypos;            
        }   
    }
 
    return roomCnt;
}
cs
저작자표시 (새창열림)
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int graph[110][110];
int N;
int ans;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(graph[i][k] == 1 && graph[k][j] == 1)
                {
                    graph[i][j] = 1;
                }
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> results) 
{
    N = n;
    
    for(int i = 0; i < results.size(); i++)
    {
        graph[results[i][0]][results[i][1]] = 1;
    }
    
    floyd();
    
    for(int i = 1; i <= N; i++)
    {
        int cnt = 0;
        
        for(int j = 1; j <= N; j++)
        {
            if(graph[i][j] == 1 || graph[j][i] == 1)
            {
                cnt++;
            }
        }
        
        if(cnt == N-1)
        {
            ans++;
        }
    }
    
    return ans;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 길찾기 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 3] 매칭 점수 (C/C++)  (0) 2020.03.01
[프로그래머스 3] 가장 먼 노드 (C/C++)  (0) 2020.02.05
[프로그래머스 3] 입국 심사 (C/C++)  (0) 2020.01.27
[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
 
vector<pair<int, int>> map[20010];
int d[20010];
 
void dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    d[start] = 0;
 
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(d[now] != nowCost)
        {
            continue;
        }
        
        for(int i = 0; i < map[now].size(); i++)
        {
            int next = map[now][i].first;
            int nextCost = map[now][i].second;
            
            if(d[next] > nowCost + nextCost)
            {
                d[next] = nowCost + nextCost;
                pq.push({d[next], next});
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> edge) 
{
    for(int i = 1; i <= n; i++)
    {
        d[i] = 99999999;
    }
    
    for(int i = 0; i < edge.size(); i++)
    {
        map[edge[i][0]].push_back({edge[i][1], 1});
        map[edge[i][1]].push_back({edge[i][0], 1});
    }
    
    dijkstra(1);
    
    int Max = 0;
    for(int i = 1; i <= n; i++)
    {
        if(Max < d[i])
        {
            Max = d[i];
        }
    }
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(Max == d[i])
        {
            cnt++;
        }
    }
   
    return cnt;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 매칭 점수 (C/C++)  (0) 2020.03.01
[프로그래머스 3] 순위 (C/C++) (★★)  (0) 2020.02.05
[프로그래머스 3] 입국 심사 (C/C++)  (0) 2020.01.27
[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
[프로그래머스 3] 등굣길 (C/C++)  (0) 2020.01.14
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
 
int N, M;
long long Max;
long long tree[1000010];
 
long long cal(long long mid)
{
    long long sum = 0;
    
    for(int i = 1; i <= N; i++)
    {
        if(mid < tree[i])
        {
            sum += tree[i]-mid;
        }
    }
    
    return sum;
}
 
int main(void)
{
//    freopen("B2805_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> tree[i];
    }
    
    sort(tree+1, tree+N+1);
    
    long long left = 1;
    long long right = tree[N];
    
    while(left <= right)
    {
        // 절단기의 높이 
        long long mid = (left + right) / 2;
        
        // 자른 나무길이의 합 
        long long sum = cal(mid);
        
        if(sum >= M)
        {
            left = mid+1;
            
            if(mid > Max)
            {
                Max = mid;
            }
        }
        else
        {
            right = mid-1;
        }
    }
    
    cout << Max;
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Search' 카테고리의 다른 글

[백준 2110] 공유기 설치 (Binary Search) (C/C++) (★★★)  (0) 2020.03.31
[백준 2512] 예산 (Binary Search) (C/C++) (★)  (0) 2020.03.31
[백준 2869] 달팽이는 올라가고 싶다 (Binary Search) (C/C++)  (0) 2020.03.31
[백준 1654] 랜선 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
 
int K, N;
long long Max;
long long lan[10010];
 
int cal(int mid)
{
    int cnt = 0;
    
    for(int i = 1; i <= K; i++)
    {
        cnt += lan[i] / mid;
    }
    
    return cnt;
}
 
int main(void)
{
//    freopen("B1654_input.txt", "r", stdin);
    
    cin >> K >> N;
    
    for(int i = 1; i <= K; i++)
    {
        cin >> lan[i];
    }
    
    sort(lan+1, lan+K+1);
    
    long long left = 1;
    long long right = lan[K];
    
    while(left <= right)
    {
        // 랜선의 길이 
        long long mid = (left + right) / 2;
        
        // 나눈 랜선의 총 갯수 
        int divideCnt = cal(mid);
        
        if(divideCnt >= N)
        {
            left = mid+1;
            
            if(mid > Max)
            {
                Max = mid;
            }
        }
        else
        {
            right = mid-1;
        }
    }
    
    cout << Max;
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Search' 카테고리의 다른 글

[백준 2110] 공유기 설치 (Binary Search) (C/C++) (★★★)  (0) 2020.03.31
[백준 2512] 예산 (Binary Search) (C/C++) (★)  (0) 2020.03.31
[백준 2869] 달팽이는 올라가고 싶다 (Binary Search) (C/C++)  (0) 2020.03.31
[백준 2805] 나무 자르기 (Binary Search) (C/C++) (★)  (0) 2020.01.28
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int N;
int islandCnt;
int Min = 9999999;
int map[110][110];
int visited[110][110];
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
// 섬 색칠
void paint(int x, int y, int color)
{
    q.push({x, y});
    map[x][y] = color;
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == -1)
            {
                q.push({xpos, ypos});
                map[xpos][ypos] = color;
            }
        }    
    }
}
 
void find()
{
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            // 바다로 가는 경우 
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y] + 1;
            }
            // 다른섬에 도착하는 경우 = 최소 
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 0 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                
                int bridgeLen = visited[xpos][ypos] - 2;
                
                if(bridgeLen < Min)
                {
                    Min = bridgeLen;
                }
                
                return;
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B2146_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            // 섬을 번호순대로 색칠하기위해 -1로 맵 수정 
            if(map[i][j] == 1)
            {
                map[i][j] = -1;
            }
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(map[i][j] == -1)
            {
                paint(i, j, ++islandCnt);
            }
        }
    }
    
    for(int k = 1; k <= islandCnt; k++)
    {
        // 초기화 
        queue<pair<int, int>> temp;
        q = temp;
        memset(visited, 0, sizeof(visited));
        
        // 다리 계산 
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                // k번 섬의 좌표 삽입 
                if(map[i][j] == k)
                {
                    q.push({i, j});
                    visited[i][j] = 1;
                }
            }
        }
        
        find();
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > BFS' 카테고리의 다른 글

[백준 1167] 트리의 지름 (BFS, Tree) (C/C++) (★)  (0) 2020.02.16
[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2178] 미로 탐색 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int row, col;
int map[110][110];
int visited[110][110];
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(int x, int y)
{
    q.push({x, y});
    visited[x][y] = 1;
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 1 && visited[xpos][ypos] == 0)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y] + 1;
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B2178_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
    
    BFS(0, 0);
    
    cout << visited[row-1][col-1];
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > BFS' 카테고리의 다른 글

[백준 1967] 트리의 지름 (BFS, Tree) (C/C++)  (0) 2020.02.16
[백준 2146] 다리 만들기 (BFS) (C/C++)  (0) 2020.01.28
[백준 7576] 토마토 (BFS) (C/C++)  (0) 2020.01.26
[백준 1707] 이분 그래프 (BFS) (C/C++) (★)  (0) 2020.01.26
[백준 1525] 퍼즐 (BFS) (C/C++) (★★)  (0) 2019.12.13

완전탐색의 정의

  • 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘을 말한다.

  • Brute Force 알고리즘 이라고도 불린다.

  • 모든 경우를 전부 찾기때문에 정확한 답을 찾을 수 있다.

  • 모든 경우를 전부 찾기때문에 시간초과에 걸릴 가능성이 높다 -> 이를 해결하기 위해 백트래킹 사용

완전탐색의 종류

① for문을 통한 완전탐색

더보기

 

합이 10인 순서쌍을 구하는 문제

 

 

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    int sum = 10;
    int cnt = 0;
    
    for(int i = 0; i <= 10; i++)
    {
        for(int j = 0; j <= 10; j++)
        {
            if(i + j == sum)
            {
                cnt++;
            }
        }
    }
    
    cout << cnt;
    
    return 0;
}
 
 cs

② 재귀함수를 통한 완전탐색 -> 순열, 조합

더보기

 

조합 문제 - 일곱 난쟁이 https://www.acmicpc.net/problem/2309

 

 

#include <stdio.h>
 
int height[7];
int input[9];
int flag;
 
void combination(int sum, int cnt, int idx)
{        
    if(cnt == 7)
    {        
        if(sum == 100)
        {
            flag = 1;
            return;
        }
        else
        {
            return;
        }
    }
    
    for(int i = idx; i < 9; i++)
    {
        height[cnt] = input[i];
        combination(sum + height[cnt], cnt+1, i+1);
        if(flag == 1)
        {
            return;
        }
    }
}
 
int main(void)
{
//    freopen("B2309_input.txt", "r", stdin);
    
    for(int i = 0; i < 9; i++)
    {
        scanf("%d", &input[i]);
    }
    
    combination(0, 0, 0);
    
    // 버블 정렬 -> 오름차순 출력을 위해 
    for(int i = 6; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(height[j] > height[j+1])
            {
                int temp = height[j];
                height[j] = height[j+1];
                height[j+1] = temp;
            }
        }
    }
    
    for(int i = 0; i < 7; i++)
    {
        printf("%d\n", height[i]);
    }
    
    return 0;
}
 c

③ 라이브러리를 통한 완전탐색 -> 순열, 조합

   C++ :  https://twpower.github.io/90-combination-by-using-next_permutation

 

   PYTHON : https://ghwlchlaks.github.io/permutation-combination-python

프로그래머스 완전탐색 문제

숫자 야구 (조합 응용)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int num[3];
int result[3];
int visited[10];
int answer;
 
vector<vector<int>> copy_baseball;
 
int strike()
{
    int strikeCnt = 0;
    
    for(int i = 0; i < 3; i++)
    {            
        if(result[i] == num[i])
        { 
            strikeCnt++;
        }
    }
    
    return strikeCnt;
}
 
int ball()
{
    int ballCnt = 0;
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if(i == j)
            {
                continue;
            }
 
            if(result[i] == num[j])
            {
                ballCnt++;
            }
        }
    }
    
    return ballCnt;
}
 
void DFS(int cnt)
{
    if(cnt == 3)
    {   
        for(int i = 0; i < copy_baseball.size(); i++)
        {
            // 자리수별로 num에 저장
            int temp = copy_baseball[i][0];
            for(int j = 2; j >= 0; j--)
            {
                num[j] = temp % 10;
                temp /= 10;
            }
            
            // 스트라이크
            if(strike() != copy_baseball[i][1])
            {
                return;
            }
            
            // 볼
            if(ball() != copy_baseball[i][2])
            {
                return;
            }    
        }
        
        answer++;   
        
        return;
    }
    
    for(int i = 1; i <= 9; i++)    
    {
        if(visited[i] == 0)
        {
            visited[i] = 1;
            result[cnt] = i;
            DFS(cnt+1);   
            visited[i] = 0;
        }
    }
}
 
int solution(vector<vector<int>> baseball) 
{
    copy_baseball = baseball;
    
    DFS(0);
    
    return answer;
}
 cs

추천문제

https://www.acmicpc.net/problem/2529 (순열)

 

https://www.acmicpc.net/problem/10819 (순열) 

 

https://www.acmicpc.net/problem/2309 (조합) 

 

https://www.acmicpc.net/problem/15686 (조합) -> 삼성 코테 기출

 

저작자표시 (새창열림)

'Algorithm' 카테고리의 다른 글

지역변수로 크기가 큰 배열 선언 시 문제점  (0) 2019.09.27
Prim vs Dijkstra (프림 다익스트라 비교)  (4) 2019.09.23
Dijkstra vs Floyd-Warshall (다익스트라 플로이드 비교)  (0) 2019.09.23

+ Recent posts

티스토리툴바