Dev_Diary

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 의 제곱근 이하의 소수를 모두 구한..

DFS(Depth First Search) / 깊이 우선 탐색DFS 는 후에 설명될 BFS 와 함께 대표적이고 가장 기초적인 길찾기 알고리즘입니다.깊이 우선 탐색이라는 이름에 걸맞게 우선 깊게 파고들어가고 보는 알고리즘이라고 볼 수 있는데, 일반적으로 복잡하지 않은 길 찾기 문제나 어떤 그래프가 몇 개의 그룹으로 존재하는지 찾는데 많이 사용하곤 합니다. 또 스택(Stack) 이라는 자료구조를 사용하는 것이 특징이며 후입선출이라는 스택의 특징을 잘 이용한 알고리즘입니다. 혹은 재귀 함수로 스택을 사용하지 않고 구현할 수 있지만 후입선출이라는 특징은 여전히 사용됩니다. DFS 를 사용하는 상황에서의 단계를 크게 나누자면 아래와 같습니다. 1. 데이터를 입력2. 데이터에서 그래프 혹은 트리를 생성 ( 특정 노..

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