관심이 가는 개발 보물창고

문제 풀이 숭이는 혜빈이를 위해서 금 빼빼로를 최대한으로 들고 가고 싶어 합니다. 그런데 금 빼빼로를 혜빈이까지 옮기기 위해서는 그만큼의 무게를 견디는 다리가 있어야 하는데요. 어떻게 하면 숭이가 혜빈이까지 움직일 수 있는지 구하는 게 이번 문제입니다. 우선은 최대한 금 빼빼로를 가져다가 주면 좋아하기 때문에, 최대한으로 설정해놓고 움직일 수 있도록 다리를 만들어야 합니다. 기존에 MST를 이용해서 어떻게 하면 최소한의 비용으로 모든 도시들을 연결한 방법이 있었는데, 이것을 반대로 생각해서 최대한의 비용으로 모든 도시들을 연결하게 설정합니다. 왜냐하면 우리는 금 빼빼로를 최대한으로 들고 가야하기 때문입니다. 최대한의 비용으로 그래프를 설계했다면 아래와 같을 것입니다. 노란색으로 색칠한 부분이 우리가 만든..

문제 풀이 모든 두 집 쌍에 대해서 불이 켜진 길로만 서로를 왕래할 수 있도록 해야 하며, 위 조건을 지키면서 절약할 수 있는 최대 액수를 구하는 문제입니다. 모든 두 집 쌍에 대해서 가로등을 켜면서(연결하면서) 최소의 비용으로 만들고 싶다면 MST를 구하라는 문제입니다. 그런데 절약할 수 있는 최대 액수를 물었으므로 [전체의 비용 - MST를 만드는 비용 = 최대 액수]로 구해주면 됩니다. 최종 비용을 계산할 때 보통은 최소의 비용을 구하라고 하지만 반대로 얼마큼 절약할 수 있는지를 물어보는 문제였습니다. 소스 코드 #include #include #include using namespace std; const int MAX = 200001; int parent[MAX]; vector edges; in..

문제 풀이 주어진 별들의 좌표가 주어질 때 최소한의 비용으로 모든 별들을 이어주면 되는 문제입니다. 기존에 풀어왔던 문제들은 (a 노드, b 노드, c 비용)으로 주어져서 edges에 저장하고, 간선들을 비용에 따라 오름차순으로 정렬하여 구현했지만, 이번에 주어지는 것은 2차원 평면 형태로 좌표로 주어집니다. 따라서 2차원 좌표를 (a 노드, b 노드, c 비용) 형태로 만든 후 문제를 해결하면 됩니다. 우선은 모든 좌료를 하나의 배열에 모두 넣어준 다음에 2중 for문을 만든 후 한 좌표에서 다른 좌표까지의 (두 점 사이의 거리)를 구해서 edges 배열에 넣어줍니다. int size = static_cast(stars.size()); // 별들의 좌표를 담은 배열 for (int i = 0; i < ..

문제 풀이 모든 컴퓨터를 연결하는데 최소한의 비용으로 연결하려면 MST 알고리즘을 구현하면 됩니다. MST 중 유명한 알고리즘인 크루스칼 알고리즘을 이용해서 구현하면 해결할 수 있습니다. 소스 코드 #include #include #include using namespace std; const int MAX = 1001; vector edges; int parent[MAX]; int N, M; int findParent(int x) { if (x == parent[x]) return x; return parent[x] = findParent(parent[x]); } void unionParent(int a, int b) { a = findParent(a); b = findParent(b); if (a <..

문제 풀이 문제를 요약하면 다음과 같다. 1. 마을을 연결해야 된다. 그런데 가능한 최소의 비용으로 만들고 싶다. 2. 그런데 마을을 하나의 마을로 연결하는 게 아니라 나는 두 마을로 쪼개고 싶다. 그래도 가능한 최소의 비용으로 하고 싶다. 마을을 하나의 최소한의 비용으로 연결하고 싶었다면 MST 알고리즘인 크루스칼 알고리즘을 사용하면 된다. 그런데 이 문제는 마을을 한 개가 아니고 두 개로 나누고 싶어하기 때문에 고민이 필요하다. 신기한 점은 MST를 이룰 때 노드의 개수가 N개면 최소한의 비용으로 연결하려면 간선의 개수는 N - 1개만 필요하게 된다. 예를 들어 노드 5개가 있을 때 4개의 간선만으로도 5개의 노드를 모두 연결할 수 있기 때문이다. 그러면 마을이 2개라면? 노드의 개수가 N개고, 간선..

문제 풀이 간단하게 MST 알고리즘을 구현할 수 있는지 물어보는 문제다. 그중에서도 크루스칼 알고리즘을 이용해서 풀었다. 크루스칼 알고리즘은 유니온 파인드와 정렬을 이용해서 MST를 구상하게 된다. 따라서 기본적인 크루스칼 알고리즘을 구현하면 문제를 해결할 수 있다. 소스 코드 #include #include #include using namespace std; const int MAX = 10001; int V, E; vector edges; int parent[MAX]; int findParent(int x) { if (x == parent[x]) return x; return parent[x] = findParent(parent[x]); } void unionParent(int a, int b) {..

문제 풀이 약간만 생각하면 생각보다 쉽게 풀리는 문제다. 기존에 다익스트라를 통해서 한 정점에서 각 정점들의 최단 경로를 구했다면, 한 정점에서 시작해서 도착 정점까지의 경로들을 나열해야 한다. 어떻게 하면 나열할 수 있을까? 다익스트라의 원리를 보면 해결할 수 있다. 경로를 갱신할 때, 그때가 그 최단 경로이기 때문에 그 경로를 저장해주면 된다. 마치 'Union-Find'처럼 나의 부모가 누군지 저장해가면서, 최종적으로 역순으로 나열하면 그것이 최단 경로를 가지는 도시의 순서다. 출력할 때 약간 지저분할 수 있지만, 정리하면 다음과 같다. 1. 도착 지점까지의 최소 비용 = dist[도착 도시] 2. 도시의 개수 = 최단 경로를 가지는 도시의 순서의 도시를 카운트하면 된다. 3. 도시의 순서 = 도착..

문제 풀이 간단하게 BFS로 작성하고 제출하면 틀렸다고 나온다. 수빈이는 0초에 순간이동으로 현재 지점 x -> 2x로 움직일 수 있고, 1초에 -1 혹은 1로 움직일 수 있다. 그런데 BFS 라는 알고리즘은 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다. 이 문제 같은 경우는 동일하지 않은 가중치가 존재한다. 이러한 문제를 해결하기 위해서는 상식적으로 현재 공간에서 순간이동, 후진, 전진 중 시간 소모가 없는 순간이동부터 하는 것이 최단 경로다. 그런데 어떤 경우에서는 순간 이동보다 후진 혹은 전진이 먼저 큐에서 나올 수 있기 때문에 큐에 넣을 때 간선의 가중치가 훨씬 적은 순간이동부터 최우선으로 넣어야하는 것만 주의하면 된다. 이런 알고리즘을 0-1 BFS라고 한다. 0-1 BF..

문제 풀이 생각보다 조건이 되게 많은 문제다. 간단하게 생각해보면 현실에서 로봇 청소기를 생각해보자. 현재 위치와 방향에서 앞에 벽이 없다면? 아마도 전진한 다음 그곳을 청소한다. 현재 위치와 방향에서 앞에 벽이 있다면? 왼쪽이나 오른쪽으로 돌아 선 다음 그곳에서 다시 벽을 체크할 것이다. 이렇게 내가 로봇 청소기라면 어떻게 판단할지 생각하면서 문제를 다시 보자. 이제 하나씩 조건을 보면서 생각해보자. 1) 현재 위치를 청소한다. 말 그대로 현재 위치를 청소했다고 방문처리를 하고 청소 횟수를 +1 하면 된다. (주의할 점이 로봇이 처음 주어진 좌표도 청소해야 되므로 초기값은 1이다.) 2) 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다. 말이 긴데 요약하면 현재 위치에서..

문제 풀이 생각보다 어려웠고, 알고 나니까 정말 괜찮은 문제라고 생각된다. 나중에 다시 풀어봐야겠다. 문제를 요약하면, 자신의 집에서 출발하는데 50미터씩 걸어갈 때마다 맥주를 마셔야 한다. 최대 가지고 다닐 수 있는 맥주의 개수는 20개라 총 1000미터를 다닐 수 있다. 중간에 편의점에 도착하면 맥주의 개수를 다시 20개로 충전할 수 있으므로 중간에 편의점을 만나면 그때부터 다시 1000미터 반경으로 갈 수 있다. 페스티벌에 도착할 수 있다면 해피를 아니면 세드를 표시한다. 문제에서는 (x, y) 좌표로 주어진다. 보통 좌표나 연결된 노드가 주어져서 그래프 자료구조를 구현해서 문제를 풀었지만 좌표 형태로 푸는 것은 생소한 경험이라 어려웠다. 간단히 생각해보면 집에서 출발했을 때 최대로 갈 수 있는 지..