Doby's Lab

https://www.acmicpc.net/problem/1064 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net Solved By: Geometry, CCW CCW를 통해 세 점들이 한 직선 위에 있는지 판별하여 평행사변형을 만들 수 있는지 없는지에 대해 1차적으로 구분합니다. 나머지는 세 점들로부터 두 점씩 짝지어 거리를 구하여 구할 수 있는 모든 평행사변형의 둘레를 구한 다음 최댓값과 최솟값의 차이를 구해줍니다. #include #include #include #defin..

군생활 도중에 이런 목표를 이뤄낼 수 있을 거라 생각하지 못했습니다. 목표 중 꽤나 큰 목표였던 백준 다이아몬드를 달성했습니다. 이때까지의 PS에 관해서 생각이 많았던 만큼 할 말도 많아서 두 파트로 나누어 첫 번째 파트는 어떻게 달성했는지에 대한 표면적인 이야기를 다루고, 두 번째 파트에서는 어떤 생각들을 가지고 있었는지에 대해 이야기해보려 합니다. Part 1: Outside 이론을 넘은 응용 누군가 어떻게 풀었든 간에 겸손할 것 이론을 넘은 응용 티어를 달성할 때마다 깨닫는 것들이 있습니다. 이번에 깨달은 것은 이때까지 모호하던 말이 명확해졌기 때문에 적어봅니다. 한 알고리즘의 이론에 대해 공부를 하고, 구현을 하는 데까지 성공하면 바로 알고리즘을 적용해서 문제를 풀고 싶어 집니다. 하지만, 1~2..

https://www.acmicpc.net/problem/10531 10531번: Golf Bot Do you like golf? I hate it. I hate golf so much that I decided to build the ultimate golf robot, a robot that will never miss a shot. I simply place it over the ball, choose the right direction and distance and, flawlessly, it will strike the ball across www.acmicpc.net Solved By: FFT 문제가 영어로 되어있어서 간단히 요약하자면 N개의 정수가 주어지는데 뒤이어 주어지는 M개의 정수를 N..

https://www.acmicpc.net/problem/18134 18134번: 치삼이의 대모험 첫 번째 줄에 골목길의 교차점 개수 N(3 ≤ N ≤ 1,000)과 골목길의 개수 M(3 ≤ M ≤ 10,000)이 주어진다. 두 번째 줄부터 M개의 줄에 골목길의 정보가 주어진다. 각 줄에는 3개의 정수로 골목길의 www.acmicpc.net Solved By: Network Flow, MCMF 이 문제는 2311번(https://www.acmicpc.net/problem/2311)과 29900번(https://www.acmicpc.net/problem/22990)에서 유사한 테크닉으로 풀 수 있었습니다. 왕복을 해야 한다는 점에서 SOURCE로부터 시작 노드로 Capacity가 2가 되도록 Edge를 잡..

https://www.acmicpc.net/problem/22990 22990번: 사이클 모든 정점을 포함하고 정점과 간선이 서로 겹치지 않는 단순 사이클의 집합이 존재하는 경우 첫 번째 줄에 1을 출력한다. 그렇지 않으면 0을 출력한다. 모든 정점을 포함하고 정점과 간선이 서로 www.acmicpc.net Solved By: Network Flow, Bipartite Matching, MCMF 단순 사이클이란 시작점과 끝점을 제외한 중복 점이 없는 사이클입니다. 이러한 부분에서 노드를 정점 분할로 두고 생각해야겠다 했지만, '모든 정점을 사용했는가'는 알아낼 수 있는 방법이 떠오르지 않았습니다. 또한, 모든 정점을 사용해야 하지만 모든 정점이 한 사이클에 포함되었는지, 몇 개의 정점이 나뉘어서 단순 사..

https://www.acmicpc.net/problem/9413 9413번: 제주도 관광 제주도는 관광객들이 많이 찾는 도시이다. 제주도에는 교차로가 N개, 일방통행 도로 M개가 있다. 각각의 도로는 한 교차로와 다른 교차로를 연결한다. 한 교차로 쌍을 연결하는 도로의 개수가 여 www.acmicpc.net Solved By: Network Flow, MCMF 네트워크 문제는 항상 어떻게 모델링을 할 지에 대한 아이디어가 중요합니다. 문제를 읽어보며 어떻게 처리할지 하나씩 다루어봅시다. 1. 교차로, 일방통행 도로 - 교차로는 Node, 일방통행 도로는 Directed Edge로 처리하였습니다. 2. 교차로를 공유하면 안 된다. - 노드를 한 번만 지나쳐야 합니다. 정점 분할을 통해 정점 간의 Capa..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net Solved By: DP 4부터 다음과 같은 특징을 발견할 수 있었습니다. 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 2 + 1 + 1 2 + 2 3 + 1 로 4를 표현할 수 있는데 이 중에 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 는 앞에 1을 때고 보면 3을 만드는 방법과 같습니다. 2 + 1 + 1 2 + 2 또한 2를 만드는 방법과 같고, 3 + 1 마지막 또한 1을 만드는 방법과..

https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net Solved By: DP 간단한 점화식으로 구성됩니다. 현재 좌표값이 1일 경우 cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]) + 1 현재 좌표값이 0일 경우 cache[i][j] = max(cache[i - 1][j], cache[i][j - 1]) #include #define MAX 301 using namespace std..