Dev_Diary

https://www.acmicpc.net/problem/2254 2254번: 감옥 건설첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.www.acmicpc.net볼록 껍질 ( convex hull ) 알고리즘과 임의의 점이 다각형 안에 존재하는지 찾는 알고리즘을 함께 사용하면 풀 수 있습니다. 볼록 껍질 알고리즘은 아래 링크를 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 ..

https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있다 www.acmicpc.net 일반적인 볼록 다각형이라면 단순히 모든 직선과 사람의 좌표를 CCW 알고리즘을 통해 일관된 방향이 나오는지 체크하면 되지만 오목 다각형을 포함하는 문제라면 그렇게 쉽게 풀리지 않습니다. (0, 0) 에서 출발해서 시계 방향으로 체크한다고 가정하겠습니다. 0~3 직선까지는 직선-점의 방향이 시계방향이지만 4 직선에서는 반시계방향인 것을 알 수 있습니다. 즉 오목 다각형을 포함하는 문제에서..

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 선분이 교차하는지 판단하는 알고리즘과 그룹을 판단하기 위한 유니온 파인드 알고리즘을 함께 사용하면 풀 수 있습니다. 우선 선분이 교차하는지 판단하기 위해 두 개의 선분이 주어졌을 때 가질 수 있는 상태를 생각해보겠습니다. 위와 같이 열 가지의 상태가 존재하며 모든 상태를 고려해주겠습니다. 상태의 파악에는 CCW 알고리즘을 사용하겠습니다. (0, 0) 의 경우에는 ..

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 볼록 껍질, 즉 Convex Hull 문제입니다. 이 문제를 푸는 방법 중 보편적으로 알려져 있는 알고리즘은 그라함 스캔, 그라함 알고리즘으로 알려져 있습니다. 해당 알고리즘으로 문제를 풀어보겠습니다. 그라함 스캔을 사용하기 위해서는 CCW 알고리즘을 알아야 하는데, 외적을 이용하는 알고리즘으로 세 개의 점의 상태를 알 수 있습니다. 즉 세 개의 점이 하나의 직선 위에 있는지 ..

https://www.acmicpc.net/problem/1858 1858번: 기울기가 가장 큰 두 점 평면상에 N개의 서로 다른 점들이 주어져 있을 때, 그 중 임의의 두 점을 지나는 직선의 기울기의 절댓값이 가장 큰 두 점을 찾고 싶다. 두 점의 좌표가 (x1, y1), (x2, y2) 라고 할 때, 기울기의 절댓 www.acmicpc.net 완전탐색으로 알고리즘을 짜면 시간초과가 걸리니 적당히 샘플링 할 방법을 찾아야합니다. 여기서 어느 점들을 골라 비교하면 될까를 생각하게 되는데, 결론적으로는 x 축을 기준으로 인접한 점들을 비교해주면 됩니다. 어떤 좌표군을 탐색하겠습니다. 우리는 해당 좌표군을 2진 탐색의 방식으로 가장 기울기의 절댓값이 큰 선분이 어떤 식으로 존재하는지 탐색하겠습니다. x 축을..

https://www.acmicpc.net/problem/22870 22870번: 산책 (large) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 기본적으로 다익스트라를 두 번 사용해주면 풀 수 있는 문제입니다. 다만 최단 거리로 이동할 때 노드 번호가 가장 작은 노드로 이동하는 점이 해결해야 할 가장 큰 포인트라고 할 수 있습니다. A -> B 최단거리를 기록하고 B 노드에서 다시 거슬러 올라가며 최단거리를 탐색할 때 1. 노드 번호가 작은 노드로 거슬러 올라가며 탐색한다. 의 경우에는 최단거리가 1 2 3 4 5 6 ..

https://www.acmicpc.net/problem/4563 4563번: 리벤지 오브 피타고라스 피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다. A2 + B2 = C2 세 변의 길이가 모두 자 www.acmicpc.net 피타고라스의 직각삼각형 식을 분해해 수를 구해주면 풀 수 있습니다. #include #include #include #include #include using namespace std; int main(void) { while (true) { // 입력 long long int A; cin >> A; // 입력이 0 이면 끝 if (A == 0) return 0; //..

https://www.acmicpc.net/problem/14285 14285번: 간선 끊어가기 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net 설명은 복잡하지만 결국 어떤 경로를 제외한 모든 간선을 제거하고, 남은 경로에서 한 간선을 제거한 뒤, 남은 간선들의 가중치의 합을 총 가중치 합에서 빼주면 되는 문제입니다. 물론 그 값이 최댓값이 되어야 한다는 것이 문제지만 생각을 조금 달리 해보면 쉽게 풀 수 있습니다. 총 가중치 합 - 특정 간선의 가중치 합 을 최대로 만들어야 하는 문제인데, 총 가중치 합은 정해져 있으므로 특정 간선의 ..

https://www.acmicpc.net/problem/5551 5551번: 쇼핑몰 첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N) 다음 M개 줄에는 도로의 정보 a, b, www.acmicpc.net 최단거리 목록을 초기화하지 않고 다른 노드에서 시작하는 다익스트라를 돌리면 어떻게 되는지 생각해보자. 다익스트라 알고리즘은 기본적으로 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘이므로 여러 시작노드에서 알고리즘을 돌리면 어느 노드에서 시작했는지는 모르겠지만 하여튼 해당 노드까지 도달하는 최단 거리를 기록하게 된다. 또, a->b / b->..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라로 최단 경로를 구한 뒤 최단 경로를 모두 제외시키고 다시 다익스트라로 최단경로를 구하면 풀 수 있습니다. 다만 최단경로 중복을 염두에 두고 현재 가중치가 최단 가중치보다 같거나 작을 때 우선순위큐에 넣는 방식으로 풀면 시간이 초과되므로 같을 때와 작을 때로 나누어 알고리즘을 실행해야합니다. #include #include #include #include #..