전체 글

문제 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘, 정렬 문제에서 행성 사이의 가중치 후보는 x좌표, y좌표, z좌표의 차의 절댓값이다. 행성의 수는 최대 100,000개 이므로 각 행성에서 다른 모든 행성에 대해 탐색한다면 시간초과와 메모리 초과가 발생한다. 그러므로, 행성 사이의 가중치 후보를 줄여서 계산해야 한다. 행성 사이의 거리는 x, y, z 좌표 차이 중 최솟값이므로, 각 좌표를 나눠서 처리한다. A, B, C 행성의 ..

문제 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 직접 작성한 코드는 모든 노드의 부모 노드가 발전소 노드일 때까지 크루스칼 알고리즘을 진행하며, 각 노드가 이미 발전소와 연결되어있는 간선은 선택하지 않는 방식으로 작성했다. 다른 코드를 보니, 발전소 노드를 미리 하나의 그룹으로 묶어서 크루스칼 알고리즘을 진행하는 방식으로 문제를 해결하였다. 이렇게 하면 모든 노드가 발전소와 연결되었는지 확인할 필요도 없고, 한..

문제 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 미리 입력받은 학교의 성별에 따라, 간선이 입력되어야 하는 간선인지 아닌지를 선별한다. 간선의 각 학교의 성별이 서로 다른 성별일 경우에만 입력을 받는다. 입력받은 간선으로만 크루스칼 알고리즘을 실시한다. 연결된 간선의 수가 (학교의 수 - 1)보다 작다면 모든 학교가 연결되지 않았다는 뜻이므로, -1을 출력한다. 코드 #include #include #includ..

문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 너비 우선 탐색, 구현, 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 문제의 2차원 배열에서 각 섬은 너비 우선 탐색으로 섬의 수와 위치를 파악할 수 있다. 배열에 섬의 위치와 섬의 번호를 설정하였다면, 섬과 섬 사이의 간선의 길이를 파악해야 한다. 섬의 모든 점에서 부터 상하좌우로 움직이며 다른 섬에 도달하였을 경우 거리를 파악하여 간선으로 vector에 넣는다. 점의 수가 최대 100이므로 시간초과는 발생하지 않는다. 해당 ..

문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. 다른 최소 스패닝 트리 문제와 달리, 간선이 아닌 노드를 입력으로 받는다. 그러므로 각 노드에서 다른 노드로의 간선을 구해야 한다. 간선의 비용은 노드끼리의 거리이다. 모든 간선을 구한 다음 크루스칼 알고리즘으로 최소 스패닝 트리를 만든다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; float dis..

RPC 네트워크를 통한 함수 리플리케이션 지정하기 입니다. docs.unrealengine.com RPC (Remote Procedure Call)은 로컬에서 호출되지만 (호출하는 머신과는) 다른 머신에서 원격 실행되는 함수를 말한다. RPC 함수는 매우 유용하게 사용될 수 있으며, 네트워크 연결을 통해 클라이언트와 서버 사이에 메시지를 전송할 수 있다. 자세한 사항은 위의 공식 문서에서 살표보자. 현재 상황은 땅에 떨어진 AWeapon을 주워서 장착해야 하는 상황이다. 이러한 실행은 멀티 플레이 게임의 특성 상 서버에서 실행되어야 올바르다. 즉, 클라이언트에서 장착 함수를 호출하면 서버에서 해당 함수가 실행되어야 하기에 RPC가 필요하다. // RPC 함수, UFUNCTION(Server)로 했기에, ..

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 최소 스패닝 트리, 크루스칼 알고리즘 문제이다. [백준][C++] 1197: 최소 스패닝 트리 문제 풀이 크루스칼 알고리즘을 이용하였다. 가중치가 작은 순서대로 검사할 수 있도록 간선을 가중치의 오름차순으로 정렬한다. 검사하는 간선이 사이클을 만들지 않다면 간선을 선택한다. 간 kantatatam.tistory.com 최소 스패닝 트리, 크루스칼 알고리즘의 기본 문제로 위의 문제와 풀이가 같다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2..

문제 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 다익스트라 문제이다. 다익스트라를 한번 실시하고, 최단 경로를 제거한 다음, 다시 다익스트라를 한번 실시하는 방식으로 풀어야 한다. 처음에는 최단 경로를 모두 제거될 때까지 반복해서 다익스트라를 실시 -> 경로 제거를 실시하였다. 이렇게 계속해서 다익스트라를 실시하면 시간초과가 발생한다. 한번의 다익스트라로 최단 경로를 모두 표시할 수 있도록 path 배열을 사용하였다. if (next_dist < dist[next_no..

문제 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 풀이 다익스트라, 우선순위 큐 문제이다. 처음에는 특정 노드에 도착할 때마다 벡터에 현재 비용을 추가하는 방식으로 접근했다. 하지만 이렇게 하면, 특정 노드에는 k번 도달하지 않고 다익스트라가 종료될 수 있다. 그렇다고, 노드에 도착할 때마다 다익스트라를 돌리는 우선순위 큐에 값을 추가하면 다익스트라가 끝나지 않는다. 다익스트라에 추가적으로 우선순위 큐(내림차순)를 추가하여 풀 ..

멀티플레이어 게임에서 특수한 판정은 모두 서버에서 계산된 다음, 클라이언트에게 Replicate되어야 한다. 이 Replicate는 코드상에서 어떻게 구현되어야 하는지 알아보자. 현재 땅에 떨어진 무기를 픽업을 위해서 무기의 SphereComponent에 Overlap되었을 때, 위젯 컴포넌트를 표시해야 한다. 여기서 Overlap 판정은 서버에서 실행되어야 한다. 현재 ENetRole을 검사해서 ROLE_Authority인 경우에만, Overlap 델리게이트를 바인드한다. AWeapon::AWeapon() { bReplicates = true;// replcate가 필요하므로(AreaSphere 판정) true로 설정한다. } void AWeapon::BeginPlay() { Super::BeginPl..