enopid 님의 블로그

https://www.acmicpc.net/problem/13372문제 분석 강을 기준으로 양쪽 각각 N개의 지점이 존재하고 양쪽 지점을 잇는 N개의 다리를 놓을 때 교차하는 지점의 최대 개수를 구하는 문제이다. 이때, 문제상에서 3개 이상의 다리가 동일한 지점을 교차하는 경우를 배제하였으므로 교차 지점의 위치를 고려할 필요는 없고 두 다리의 교차여부만 판별하면 된다. 교차 여부 자체는 간단하게 판별가능하다. 그림과 같이 +지점과 -지점이 있을 때, +지점에서 b다리의 값이 더 크면 -지점에서는 a다리의 값이 두 다리는 교차한다.$($그 반대의 경우도 가능하다.$)$ 하지만 모든 다리쌍에서 교차여부를 판별하려 하면, N이 $[2,100000]$으로 모든 다리쌍을 확인하는 경우는 $N^2$으로 $10^{..

https://www.acmicpc.net/problem/25960문제 분석 시작 지점인 폰의 위치에서 다른 기물(비숍, 룩, 퀀, 나이트)등을 경유하여 킹의 위치로 최소 비용으로 이동하는 문제이다. 이때, 기물과 기물 간만 이동가능하며(기물이 없는 빈칸으로 이동불가), 이동 방식은 시작 지점의 기물의 이동방식을 따르고 한 번 방문한 기물로는 재방문이 불가능하다. 더 생각할 것도 없이 폰을 시작, 킹을 도착 지점, 각 기물을 노드로 가지는 다익스트라 문제이다. 다익스트라는 최소 거리를 찾는 과정에서 이미 방문한 노드를 다시 방문하지 않으므로 각 기물 별 이동가능한 이웃 기물 들만 잘 설정하여 풀면된다.문제 해결 전략 각 기물 별로 이동방식이 다른 만큼 기물의 종류(_type), 위치(_x, _y), 이웃..

https://www.acmicpc.net/problem/5855문제 분석 두 사각형이 겹친다는 것은 두 사각형의 중심의 x거리의 차와 y거리의 차가 모두 K보다 작음을 의미한다. 겹침을 판정하는 방식은 간단하나, 모든 사각형의 조합을 고려하는 것은 시간복잡도상 불가능하므로 특정 사각형을 기준으로 가능한 후보군을 줄이는 효과적인 전략이 필요하다. 본 문제에서는 x거리의 차가 겹침을 만족하는 사각형의 후보군에 한해서 y거리의 차도 겹침을 만족하는지 판단하는 전략을 취한다.  방식을 정확히 설명하기에 앞서 특정 사각형과 겹치는 사각형은 모두 특정 사각형보다 x가 크거나 같은 경우만 확인한다.$($어차피 겹치는 사각형은 순서에 상관없어 가능하다. $)$ 1번째로 모든 중심 포인트들을 $(x, y)$ 값을 기준..

https://www.acmicpc.net/problem/10901문제 분석 슈퍼펠린드롬은 짝수일 경우 앞뒤 2 부분, 홀수일 경우 가운데를 포함해 3 부분으로 분할이 가능하다. 그리고 이때, 앞뒤 부분은 서로 동일한 슈퍼펠린드롬이다. 결국 앞뒤가 동일하므로 사전순 비교 시 앞부분만, 필요시 가운데 부분까지만 보고 판단이 가능하다.  즉, 특정 문자열의 가장 빠른슈퍼펠린드롬 문자열의 앞부분의 가장 빠른 슈퍼펠린드롬으로 펠린드롬을 구성하면 된다. 기본적인 아이디어는 위와 같은 방식으로 재귀적으로 구성하면 된다. 자세한 조건분기는 하단에 서술하겠다. 기본적으로 1번째로 문자열 길이가 홀수인지 짝수인지 판단하고, 2번째로 앞부분이 슈퍼펠린드롬인지 확인하며, 3번째로 앞부분과 뒷부분의 사전순 크기비교를 수행한다..

https://www.acmicpc.net/problem/23250문제 분석일단 하노이 탑의 방식부터 다시 정리하자. 알다시피 하노이 탑은 재귀적으로 표현가능하다. N 크기의 탑을 옮기는 과정은 N-1 크기의 탑을 옮기는 과정으로 표현가능하다. N-1의 탑을 잠시 다른데 옮기고 N의 블록을 옮기고 다시 N-1의 탑을 옮기면된다. 이 방법만이 최소면서 유일한 하노이탑 이동 방식이다.   N 크기의 탑을 i위치에서 k위치로 옮기는 경우1. N-1크기의 탑을 i에서 j로 옮긴다.2. N을 i에서 k로 옮긴다.3. N-1 크기의 탑을 j에서 k로 옮긴다.N=1 일시는 바로 i에서 k로 옮긴다. N의 크기의 탑을 이동하는 최소 비용은 $2^N-1$만큼의 이동을 필요로 한다.$($하단에 유도과정이 있다.$)$ 이때..

https://www.acmicpc.net/problem/29761문제 분석 해당 문제를 단순히 접근하면 이미 방문한 노드를 다시 방문해야 되는 문제가  생긴다. 예를 들어 아래와 같은 경우를 생각해 보자 높이가 5인 노드를 나중에 방문하면 우상단의 노드가 4의 값을 가지고 나중에 5인 노드를 거쳐서 우상단의 노드롤 재방문해야될 필요가 생긴다. 노드의 재방문을 허락하게 되면 못 풀 거야 없지만 문제를 굉장히 어렵게 풀도록 된다. 그래서 우리는 노드를 한 번만 방문해도 되도록 몇 가지 규칙을 세우고 노드를 방문하도록 하겠다. 노드를 한번만 방문하기 위해서는 해당 노드를 방문하기 전 인접 노드 중 가장 큰 확산값을 줄 수 있는 노드를 먼저 방문해야 된다.그럼 가장 큰 확산 값을 주는 인접노드는 어떤 노드인가..

1번부터 n번까지 번호가 매겨진 n마리의 드래곤이 있습니다. 드래곤 i의 나이는 $a_i$​입니다. 모든 $a_i$​는 서로 다릅니다. 1번 드래곤은 에비리르$($Evirir$)$입니다.에비리르는 t번 드래곤에게 편지를 보내려고 합니다. 나이 차이로 인한 어색함을 피하기 위해, 에비리르는 편지를 다른 드래곤에게 먼저 보낼 수 있습니다(반드시 t번 드래곤일 필요는 없습니다). 편지를 받은 드래곤은 다시 다른 드래곤에게 편지를 보낼 수 있으며, 이런 식으로 편지를 최종적으로 t번 드래곤에게 전달하는 것이 목표입니다.모든 i$(1≤i≤n)$에 대해, 드래곤 i가 편지를 가지고 있을 때, 드래곤 j에게 편지를 보내는 데 걸리는 시간은 $∣a_i−a_j|$입니다. 드래곤이 자기 자신에게 편지를 전달하는 경우에는 ..

https://www.acmicpc.net/problem/14380문제 분석 각 학생별로 친한 친구(BFF)가 있을 때, 모든 학생이 BFF와 인접하게끔 가장 큰 원을 이루는 방식을 묻는 문제이다. 이때, 조건을 만족하면서 원을 구성하는 방식은 2가지이다. 1번째는 전체 노드가 하나의 사이클을 이루는 방식이고 2번째는 2개의 체인이 끝부분에서 서로를 참조해 이어진 형태이다.(화살표는 해당 노드의 BFF를 가르킨다.)1. 전체 노드가 사이클을 이룬다.ex) $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow (1)$2. 두 가지 선형으로 이루어진 체인의 끝부분이 서로를 참조해 결합해 있다.ex) $1 \rightarrow 2 \rightarrow 3 \le..

https://www.acmicpc.net/problem/2645문제 분석 정리하자면 격자 공간에서 각 격자마다 이동비용이 존재할 때 특정 두 지점을 잇는  최소 비용을 구하는 문제이다. 격자의 한변의 크기인 N이 50보다 작은 수이기 때문에 단순한 다익스트라로도 해결가능하다.문제 해결 전략 우선 각 격자마다 비용을 입력으로 들어오는 회로를 통해 구해내고 다익스트라를 수행한 뒤 간단한 경로 추적까지만 구현하면 된다.코드#include #include #include #include #include using namespace std;//문제분석//격자에서 격자마다 비용이 존재할 때 특정 두 지점사이의 최소 비용 거리 구하기//단순한 다익스트라문제// (V : N^2 = 2500, E=2*N*(N-1)=..

https://www.acmicpc.net/problem/15328문제 분석 3차원에서 원점부터 4개의 지점을 순차적으로 방문할 때 총 이동거리가 X보다 큰지 작은 지를 묻는 문제이다.단순히 각 지점간 거리를 더해서 X와 대소 비교를 하면 되어 보이지만 문제가 long double보다 더 높은 정밀도를 써야 하여 16바이트 자료형인 __float128을 사용해야 하고 그에 따라 거리를 구하기위해 필요한 sqrt함수도 직접 구현해야 한다.  $($파이썬의 경우 decimal 자료형을 사용하면 자료형 자체에서 sqrt를 지원하여 쉽게 구현가능$)$문제 해결 전략 __float128을 사용하고  sqrt 함수를 구현하는 것이 문제의 전부이다. 제곱근은 바빌로니아 방식을 사용하거나 뉴턴 랩슨방식을 통해 구하면 ..