복습 정리 노트

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 20670번 : '미스테리 싸인', 3878번 : '점 분리' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum III ~ Platinum II에 해당하며, 문제를 풀이하기 위해 볼록 다각형 내부의 점 판정 알고리즘에 대해 알고 있어야 합니다. [C++ 알고리즘] 다각형 내부의 점 판정 알고리즘 (Point in Convex Polygon) 이 포스트에서는 다각형 내부의 점 판정 알고리즘에 대한 예시 코드와, 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 'Point in Convex Polygon' 태그의 문제들에 대한 풀이 코드와 해설을 다 res..

이 포스트에서는 다각형 내부의 점 판정 알고리즘에 대한 예시 코드와, 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 'Point in Convex Polygon' 태그의 문제들에 대한 풀이 코드와 해설을 다룹니다. 최근 기하 문제들을 많이 풀이하고 있는데, Convex Hull 알고리즘과 Roating Calipers 알고리즘만으로는 해결할 수 없는 문제들이 있습니다. 이들 중 가장 자주 보이는 태그 중 하나는 point_in_convex_polygon으로, 다각형 내부의 점 판정을 하는 알고리즘입니다. 따라서 이번 포스트에서는 위의 문제들을 해결할 수 있는 다각형 내의 점 판정 알고리즘을 구현해보고, 나아가 예제 하나를 풀이해보도록 하겠습니다. 문제는 가장 쉬운 문제를 풀..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 1310번 : '달리기 코스', 10254번 : '고속도로' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, 문제를 풀이하기 위해 회전하는 캘리퍼스(Rotating Calipers) 알고리즘에 대해 알고 있어야 합니다. [C++ 알고리즘] 회전하는 캘리퍼스 알고리즘 구현 (BOJ 8927번 : Squares) 이 포스트는 회전하는 캘리퍼스 알고리즘(Rotating Calipers)에 대해 다루고, 이에 대한 예제를 풀어보면서 알고리즘을 직접 코드로 구현하는 내용을 다루고 있습니다. 풀이할 예제는 프로그래밍 문 restudycafe.tistory.com ↑ 회전하는 캘리퍼..

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 9240번 : '로버트 후드' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum IV 이상이며, 문제를 풀이하기 위해 Convex Hull 알고리즘과 Rotating Calipers 알고리즘에 대한 이해가 필요합니다. Convex Hull 알고리즘에 대한 설명 : https://restudycafe.tistory.com/386?category=969972 Rotating Calipers 알고리즘에 대한 설명 : https://restudycafe.tistory.com/401?category=969972 위에 배경 지식을 위한 링크를 첨부하니 공부하실 때 참고하시면 좋습니다. 여기서는 알고리..

이 포스트는 회전하는 캘리퍼스 알고리즘(Rotating Calipers)에 대해 다루고, 이에 대한 예제를 풀어보면서 알고리즘을 직접 코드로 구현하는 내용을 다루고 있습니다. 풀이할 예제는 프로그래밍 문제 사이트 백준 Online Judge의 8927번 : 'Squares'이며, 문제의 난이도는 Solved.ac 기준 Platinum II에 해당합니다. 우리는 Convex Hull 알고리즘을 사용하면 주어진 점들 중에서 가장 외곽의 점들을 선택하여 볼록다각형을 구성할 수 있고, 이는 주어진 점들로 구성할 수 있는 최대 면적이 됩니다. 그렇다면 주어진 점들 중에서 가장 긴 거리를 구하는 방법은 무엇일까요? 가장 간단하게 완전 탐색으로 생각해보면, 점의 개수가 N개라고 할 때 이들 중 2개를 이루는 점의 쌍..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 7420번 : '맹독 방벽' 문제와 6850번 : 'Cows' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum에 해당하며, 문제를 풀이하기 위해 Convex Hull 알고리즘에 대해 알고 있어야 합니다. 7420번 : 맹독 방벽 모든 건물들로부터 L 이상의 거리를 가지는 방벽의 최소 길이를 구하는 문제입니다. Convex Hull 알고리즘을 이용해 구한 최소 크기의 볼록다각형에 둘레를 추가로 계산해주면 되는 문제입니다. ↓ 풀이 코드는 아래의 접은 글에 정리되어 있습니다. 더보기 #include #include #include #include #include #define Pi 3.1..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 13059번 : 'Tourists' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum IV에 해당하며, 문제를 풀이하기 위해 LCA(최소 공통 조상) 알고리즘에 대한 지식이 필요합니다. 13059번 : Tourists 문제가 영문이고 길이가 길지만, 주어진 그림과 예시를 읽어보면 쉽게 이해가 가능한 문제입니다. y > x이고 y = ax인 모든 (x, y)에 대해 x에서 y로 갈 때 거치는 노드(양 끝 x, y 노드 포함)의 총 합을 구하는 문제입니다. 위의 경우에는 저렇게 55개의 노드를 거치므로 답으로 55를 출력해주면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1761번 : '정점들의 거리' 문제에 대한 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 LCA(최소 공통 조상) 알고리즘에 대한 이해가 필요합니다. 1761번 : 정점들의 거리 트리가 주어지고, 두 노드 쌍의 번호가 입력되면 그 거리를 출력하는 문제입니다. 문제 자체는 아주 간단하지만, N이 4만 이하이고 M이 1만 이하이기 때문에 효율적인 알고리즘을 활용하지 않으면 시간 초과에 걸리게 됩니다. [C++ 백준 풀이] LCA, 최소 공통 조상 알고리즘 (11438번 : LCA 2 / 11437번 : LCA) 이 포스트에서는 LCA, 최소 공통 조상 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 15480번 : 'LCA와 쿼리' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Platinum II에 해당하며, LCA(최소 공통 조상) 알고리즘에 대해 알고 있어야 합니다. 15480번 : LCA와 쿼리 N개의 노드로 이루어져 있는 트리의 간선들이 모두 입력되었을 때, r u v(루트 노드를 r이라고 설정했을 때 u와 v의 LCA를 출력) 쿼리에 대한 처리를 수행하는 문제입니다. 우선 노드의 수가 10만개 이하이므로, LCA 알고리즘을 사용하여 최소 공통 조상을 log H 시간 안에 찾아야 함은 예상이 가능합니다. 문제는 루트 노드가 매 쿼리마다 바뀐다는 것인데, 상식적으로 생각해보아도 루트를 ..

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 3584번 : '가장 가까운 공통 조상' 문제의 풀이 코드와 해설을 다루고 있습니다. 문제의 난이도는 Solved.ac 기준 Gold IV에 해당하며, 문제를 풀이하기 위해 트리에 대한 기본 지식이 필요합니다. 지난 포스트에서 LCA에서 Parent 배열에 2^k번째 부모 노드들을 저장하는 방법을 통해 10만 단위의 N에 대해서도 빠른 풀이를 하는 방법을 다루어보았습니다. 그러나 작은 범위의 트리에 대해서 LCA를 더 간단하게 구현하는 방법은 뭐가 있을까요? (순서가 반대로 된 것 같지만 이번 포스트에서는 더 쉬운 LCA 문제는 어떻게 구현하면 간단할지 알아보도록 하겠습니다.) 3584번 : 가장 가까운 공통 조상 문제에서 가장 가까운..