알고리즘63 [C++] 백준 1800번 : 인터넷설치 https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1. 접근 다익스트라 + 경로저장으로 풀 수 있을 줄 알았다. 하지만 구하려는 값이 최단 경로의 최소비용이 아닌 모든 경우의 최소비용이기 때문에 틀린 방식이었다. 2. 풀이 결국 검색으로 힌트를 얻고 풀 수 있었다 이분 탐색 + 다익스트라로 푸는 것인데, 이분 탐색으로 비용 상한선을 설정한 뒤, 다익스트라에 적용한다 이 때, K개 연결에 대해서는 무료인 조.. 2021. 9. 10. [C++]백준 1197번 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. 풀이 정직한 최소 스패닝 트리 문제 https://dmzld.tistory.com/34 [자료구조] 3. Graph : MST, 최단거리, Union-Find 0. Graph 노드들과 그 노드들을 연결한 간선에 대한 정보를 저장하는 자료구조 1. Terminology 1) vertex(정점), edge(간선) 2) degree : 한 정점에 간선.. 2021. 9. 9. [C++]백준 8972번 : 미친 아두이노 https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 1. 풀이 시뮬레이션문제 로봇이 이동할 때, 해당 턴에 로봇이 2개 이상 이동한 자리면 터뜨리는 것만 잘 구현하면 될듯 #include #include #include #include #include using namespace std; struct pos{ int y, x; }; int R, C; char map[100][100]; int cntR[100][100]; pos cPos; queu.. 2021. 9. 4. [C++]백준 2234번 : 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. 접근 요구하는게 많았는데 일단 유니온파인드로 푸는 문제인줄 알았지만 bfs로 푸는 문제 2. 핵심 1) 벽 유무를 비트마스킹을 통해 연산(나는 처음에 map[y][x] 값 받자마자 소인수분해로 map[y][x][4] 값을 채웠다) 2) 아래 코드에선 개선하지 않았는데 3번째 요구사항인 벽을 부쉈을 때의 방크기 최대값은 bfs()에서 방 넘버링을 하면 시간을 더 줄일 수 있을 것 같다 #.. 2021. 9. 3. 최단경로 알고리즘 정리 : 다익스트라, 벨만포드, 플로이드-와샬 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 다익스트라 - 음의 가중치로 인한 싸이클 발생 판별 불가능 - 현재까지 탐색된 정점 집합에서 최단 경로를 가지고 있는 탐색되지 못한 정점을 찾아 탐색한 정점 집합에 추가한다. - 그 다음, 탐색된 정점(i)들에 대해 새로 추가한 정점(j)을 거칠 때 발생하는 최단 경로를 업데이트한다. : D[i] = min(D[i], D[j] + W[j][i]) - 반복한다 - 기본문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정.. 2021. 8. 29. [C++]백준 17182번 : 우주탐사선 https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 1. 접근 K행성에서 모든 행성을 방문하는 최단비용을 계산해야하므로 플로이드-와샬 알고리즘을 통해 모든 행성 간의 최단거리를 구한 후, dfs로 전체방문 최소비용을 구한다. #include #include #include #include #include using namespace std; int N, K; int w[10][10]; int chk[10], ans = INT_MAX; void.. 2021. 8. 29. [C++]백준 14466번 : 소가 길을 건너간 이유 https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 1. 접근 : 단순 BFS 원리만 사용해서 성공은 했지만 메모리와 싱행시간이 너무 컸다. 한 마리씩 BFS 돌면서 못 만난 마릿수를 최종결과 값에 더해주고 해당 기준 소는 다음 경우에서 제외 (즉 i번째로 기준 잡은 소는 (K-i)만큼의 소와의 경우를 check, 마지막 소는 check 안해도 된다.) #include #include #include us.. 2021. 8. 28. [C++]백준 15591번: MooTube(Silver) https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 1. 접근 "좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다." 에서 스패닝트리를 쓰는건가 생각해봤지만 그냥 기알고리즘 적용한다기보다 문제에 맞춰 로직을 짜면 됐다. 2. 풀이 스패닝트리 특징을 생각하며 로직을 짜긴했다. 모두 이어져있으니 USADO를 구할 때 Vi.. 2021. 8. 22. [C++]백준 1774번 : 우주신과의 교감 www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 1. 접근 크루스칼 알고리즘으로 입력이 조금 특이해서 2가지 처리를 해서 기반을 만들어주어야 한다. 1) 이미 연결되어 있는 edge 정보를 저장 2) 좌표만 주어지기 때문에 각각의 좌표 간 거리 정보를 구해서 저장 2. 개선 edge의 최소 거리 순으로 MST를 찾아야하기 때문에 관성적으로 pq를 썼는데 그냥 edge를 기본 배열에 넣고 처음에 오름차순으로 정렬 후 순차적으로 탐색하.. 2020. 12. 6. 이전 1 2 3 4 5 6 7 다음
