PS
-
알고스팟 소풍PS 2020. 1. 9. 21:26
https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요 algospot.com n이 매우 작기 때문에 완전탐색으로 풀 수 있겠다고 생각했다. 단, 중복을 없애고 고르는 것이 관건이라고..
-
알고스팟 쿼드 트리 뒤집기PS 2020. 1. 7. 20:21
https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 algospot.com 압축을 풀어서 뒤집고 다시 압축하는 방법은 불가능하다. 그림의 최대 크기가 2^20 * 2^20 ..
-
알고스팟 Traveling Salesman Problem 1PS 2020. 1. 7. 17:49
https://algospot.com/judge/problem/read/TSP1 algospot.com :: TSP1 Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 algospot.com n의 크기에 따라 풀이법을 달리해야 하는 유명한 문제라고 한다. 이 문제는 n이 8로 매우 작으므로 완전탐색으로..
-
알고스팟 게임판 덮기PS 2020. 1. 3. 22:56
https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 입력 력의 첫 algospot.com 전형적인 완전탐색 문제였다. 접근방법 1. 2차원 배열에서 한 칸씩 이동한다. 2. 이때 ..
-
백준 1922번 네트워크 연결PS 2019. 12. 20. 21:25
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소신장트리 기본 문제입니다. 본인은 크루스칼 알고리즘과 프림 알고리즘으로 풀어보았습니다. 1. 그래프의 상태는 따로 저장해놓고(v에 저장하였습니다) 아무것도 연결되어있지 않은 상태에서 시작합니다. 2. 그래프의 간선을 가중치를 기준으로 오름차순 정렬합니다. 3. 가중치가 가장 작은 간선부터 연결합니다. 이때, 사이클이 생기지 않아야 합니다. 이를 위해서 유니온-파인드 기법을 이용합니다. #include #include #include using namespace std; struct ..