Dev_Diary

https://www.acmicpc.net/problem/2143부분합 문제입니다. 단순히 부분합 리스트를 만들고 부분합 / 부분합 쌍을 찾으면 간단히 생각해도 최악의 경우 1000개의 데이터에서 4중 반복문을 돌아야 하기 때문에 다른 방법을 찾아야 합니다. 우선 각 부분합 리스트에서 2중 반복문을 통해 모든 부 배열 합을 기록해줍니다. 데이터 기록을 할 때 딕셔너리와 리스트 중 선택할 수 있는데, 딕셔너리는 일반적으로 시간을 위해 공간을 포기한 경우로 해당 문제에서 딕셔너리에 모든 부 배열 합을 기록하면 메모리초과가 발생합니다. 그러므로 리스트에 기록하도록 합니다. 기록 중 이분 탐색을 통한 빠른 검색을 위해 정렬을 해주어야 하는데, 이분탐색을 활용한 정렬인 bisect.insort 함수를 사용할 수 ..

https://www.acmicpc.net/problem/3673우선 리스트를 부분합 리스트로 치환해줍니다. 연산 시 걸리는 시간을 줄이기 위함입니다.그 뒤에 'd 로 나누어 떨어진다' 의 부분을 쉽게 풀어 볼 생각을 해야합니다.조건에서 데이터의 크기는 최대 50000 개인데 해당 데이터를 2중 반복문으로 순회하면 시간 초과가 발생하기 때문입니다. 결론적으로, 어떠한 두 수 A, B의 차가 d 로 나누어 떨어지려면 A 를 d 로 나눈 나머지와 B 를 d 로 나눈 나머지가 같으면 됩니다. A = ad + q, B = bd + p 라고 가정하겠습니다.A - B = d(a-b) + (q - p) 입니다.A - B 가 d 로 나누어 떨어지려면 모든 인수가 d 로 나누어떨어지면 됩니다.d(a-b) 는 이미 d 의..

https://www.acmicpc.net/problem/1027 현재 서있는 건물 꼭대기에서 다른 건물을 볼 수 있는 조건은 내가 서있는 건물과 보고자 하는 건물 사이의 건물들이 시야를 가리지 않는 것입니다. 즉 서있는 건물의 꼭대기와 보고자 하는 건물의 꼭대기를 이은 선분이 다른 건물과 교차하지 않으면 됩니다. 다만 이런 식으로 진행하면 앞선 건물이 다음 건물을 가리는 경우를 고려할 수 없으니 다른 방법을 생각해야 합니다. 왼쪽에 있는 건물의 왼쪽에 있는 건물을 보려면 내가 서있는 건물의 꼭대기에서 가까운 왼쪽에 있는 건물의 꼭대기를 향해 반직선을 그었을 때 반직선의 반시계 방향에 건물의 꼭대기가 있다면 이 건물은 앞선 건물에 가려 보이지 않습니다. 반대로 반직선의 시계 방향에 건물의 꼭대기가 있다면..

https://www.acmicpc.net/problem/1016제곱수의 배수가 아닌 수를 찾는 문제입니다. 다만 제한이 상당히 빡빡해 시간을 최대한 단축해야 통과할 수 있습니다.특정 범위의 수들을 제곱수로 체를 칠텐데, 우리는 어떠한 범위에서 A 의 배수들을 제거하면 NxA 의 배수들도 모두 없어짐을 알고 있습니다. NxA 의 배수들은 A 의 배수이기도 하기 때문입니다.즉 A^2 으로 체를 친다는 말은 (N*A)^2 은 생각하지 않아도 된다는 말과 같습니다. 어차피 A^2 을 고려하며 모두 제거되었기 때문입니다. 즉 고려해야하는 수 A는 어떤 수의 배수가 아닌 수, 즉 소수임을 알 수 있습니다. 그렇기에 문제를 해결하는 프로세스는 다음과 같습니다. 1. 최댓값 MAX 의 제곱근 이하의 소수를 모두 구한..

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 ..