목록전체 글 (224)
득이공간
문제풀이 다익스트라 알고리즘을 이용해서 푸는 문제입니다.각각의 노드 사이의 이동 시간을 구해서 저장해주고 나면나머지는 일반적인 다익스트라 유형의 문제의 풀이와 동일합니다.각 노드 사이의 이동 시간을 구할 때 시작 노드를 출발 지점으로 놓으면 도착 지점까지 걸어가는 시간으로 구해야 합니다.시작 노드를 제외한 나머지 노드에서 출발 할때는 걸어가는 시간과 대포를 이용한 시간 중 작은 값으로 저장해주면 됩니다.코드#include #include #include #include #include using namespace std;const double Inf = INT_MAX;typedef pair p;typedef pair n;int S, E, N;p Point[102];list Neighbor[102];dou..
15683번: 감시스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감www.acmicpc.net 문제풀이 구현할 것이 많은 시뮬레이션 & 브루트포스 & 백트래킹 유형의 문제입니다. 카메라의 개수는 많지 않기 때문에, 각 카메라의 방향을 완전탐색(브루트포스 & 백트래킹)으로모든 각도에서 지정해보고 그 중 사각지대의 최소값을 구하면 됩니다. 사각지대를 구하기 전에 각 카메라의 방향에 따른 사무실의 상태를 구할 때 많은 구현이 필요합니다.각 카메라가 사무실을 스캔할 때, 카메라의 종류에 따라 먼저 분류하고지정된 스캔 방향, 횟수에 따라서 사무실의 상태를 구..
2470번: 두 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00www.acmicpc.net 문제풀이 적절한 두 용액을 선택하는 과정에서 완전 탐색을 이용하면 $100000 * 100000$번의 연산이 수행되므로 시간초과가 발생합니다.따라서 한 용액을 먼저 선택한 후 다른 용액을 이분 탐색을 이용해서 선택하도록 하면 $100000 * 16.6 (={log_{2}}{100000})$번의 연산만으로 풀 수 있습니다.Start, End 인덱스를 지정할 때는 선택한 두 용액의 합과 0의 크기를 비교해서 조절해주면 됩니다.코드#in..
16234번: 인구 이동N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모www.acmicpc.net 문제풀이 너비 우선 탐색을 이용해서 푸는 시뮬레이션 유형의 문제입니다.미방문 노드에서 BFS를 시작해서 연합 영역을 큐에 저장해주고연합의 크기가 2이상일 때 인구 이동을 시켜주었습니다.인구 이동이 더이상 이뤄지지 않을 때까지 해당 로직을 반복해서 시뮬레이션하도록 구현했습니다.코드#include #include #include using namespace std;typedef pair p;const int..
1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제풀이 DFS 알고리즘 & List 자료구조를 이용해서 풀었습니다. 각 노드 마다 부모 노드를 배열에 저장해주고, 자식 노드는 리스트로 구성해주었습니다. 그리고 삭제 노드를 입력받았을 때 해당 노드의 부모의 자식 리스트에서 제거해주고 루트노드로부터 깊이 우선 탐색을 수행하도록 구현했습니다. 코드 #include #include #include using namespace std; int N, Root, Cnt; int P[50]; list C[50]; v..
3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제풀이 덱 자료구조를 이용해서 뱀 몸의 위치를 기록하는 방법으로 푸는 시뮬레이션 유형의 문제입니다. 각 초마다 문제에서 제시한 조건대로 이동을 구현해주어 풀었습니다. 덱에 push_back으로 머리 이동 위치를 저장해주었고, 사과를 먹지 않았을 때는 pop_front로 꼬리를 이동해주었습니다. 그리고 초가 끝났을 때는 입력받은 X, C 정보에 따라 뱀이 현재 향하고 있는 방향(0:L, 1:R, 2:T, 3:B)을 나타내는 변수를 바꿔주었습니다. 코드 #include ..
16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제풀이 이분 탐색, 유니온-파인드 연산을 이용해서 푸는 문제입니다. 민수의 카드를 오름차순 정렬하고 upper_bownd 함수(이분 탐색)를 사용해서 내야하는 카드를 찾아 출력하면 됩니다. 그런데 한 번 낸 카드는 다시 낼 수 없기 때문에 다음 탐색에서는 제외해야 합니다. 카드의 총 개수가 많기 때문에 이 때 원소를 삭제하는 방식으로 풀면 시간초과가 발생합니다. 따라서 유니온-파인드 연산을 이용해서 한번 낸 ..
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제풀이 N-1개의 에지를 구성하는 최소 비용을 구하는 MST 유형의 문제입니다. 각 에지의 비용을 구할 때, 모든 행성끼리 연결해버리면 O($N^{2}$)으로 시간초과가 발생합니다. 따라서 행성들을 X값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Y값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Z값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개)를 구합니다. 이렇게 되면 3N-3개의 에지만으로 문제를 풀 수 ..
해당 게시물은 이득우 교수님의 '네트웍 멀티플레이 프레임웍의 이해' 강의를 수강하며 학습한 내용을 개인적으로 정리한 글입니다. 📌 목차 - 1장. 언리얼 네트웍 멀티플레이어 프레임웍 기초 1-1. 언리얼 네트웍 멀티플레이어 프레임웍 개요 1-2. 게임 모드와 로그인 1-3. 커넥션과 오너십 1-4. 액터의 역할과 커넥션 핸드셰이킹 📌 1-1. 언리얼 네트웍 멀티플레이어 프레임웍 개요 1. 향후 실습할 예제 프로젝트의 기본 설정 2. 클라이언트-서버 모델의 이해 3. 언리얼 네트웍 멀티플레이어 프레임웍을 구성하는 주요 개념의 이해 4. 앞으로 보강해야 할 기능의 확인 언리얼 네트웍 멀티프레이어 프레임웍의 구성 요소 어플리케이션: 게임 인스턴스, 월드, 네트웍 모드 접속 플로우: 로그인, 커넥션, 오너십, ..
2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제풀이 다이나믹 프로그래밍을 이용해서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다. 오름차순으로 나열한 A의 번호에 각각 연결된 B의 번호들을 순서대로 나열한 것을 하나의 수열로 생각하고 해당 수열에서 가장 긴 증가하는 부분 수열을 만들었을 때, 이 부분 수열에 해당하지 않는 숫자의 개수가 제거해야 하는 전깃줄의 최소 개수와 같습니다. 문제의 예제를 살펴보면, A 1 2 3 4 6 7 9 10 B (8) 2 (9) (1) 4 6 7 10 B의 최장 증가 부..