본문 바로가기

글

 (470)
[C++] 24558번 Downsizing https://www.acmicpc.net/problem/24558 25/10/21 반전 기하학의 내용을 담은 문제로, 나는 그린 정리의 내용을 활용하여 문제를 해결했다. 문제 접근 방식: 문제를 요약하면, 어떤 원과 그 원 내부에 있지 않은 다각형의 좌표들이 주어질 때, 다각형을 원에 대해서 반전시킨 넓이를 구하는 것이 목적이다. 편의 상 원의 중심의 좌표를 $(0, 0)$으로 옮기고, 다각형의 모든 점의 좌표 또한, 해당 이동에 맞게 전부 다 옮겨진 상태라고 가정하자. 원의 반지름을 $R$이라고 하자. 점 $P = (x, y)$의 Inversion $P' = (x', y')$은 닮음에 의하여 $(kx, ky)$가 된다. 이때, $k$의 값을 구하기 위해 $\text{length}(\overline..
[C++] 34041번 회전체와 쿼리 https://www.acmicpc.net/problem/34041 25/10/18 미적분학 + 기하학 내용으로 풀 수 있는 다이아문제다. 내용이 그리 어렵진 않은 것 같다. 문제 접근 방식: 기본적으로 Pappus Centroid Theorem을 이용한다. 해당 정리에 대한 증명은 다음과 같다.# Centroid of a RegionThe centroid $(\bar{x}, \bar{y})$ of a region bounded by the graphs of the continuous functions $f$ and $g$ such that $f(x) \geq g(x)$ on the interval $[a, b]$, $a \leq x \leq b$ is given by $$ \bar{x} = \fra..
[C++] INU 코드페스티벌 2025 업솔빙 https://www.acmicpc.net/category/detail/4580 25/10/16 백준 34552번~ 34562번까지 총 11문제로 이루어져 있다. A번 - 디딤돌 장학금(34552번)문제에서 주어진 그대로 구현하면 된다.// 34552번 디딤돌 장학금// 구현#include #include using namespace std;#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define endl '\n'int main(void){ fastio vector M(11); for (int i = 0; i > M[i]; int N; cin >> N; int ans = 0; int B; float ..
[C++] 11585번 속타는 저녁 메뉴 (추후 보강 예정) https://www.acmicpc.net/problem/11585 25/10/04 문제의 의도는 너무 뻔하다. KMP로 풀라는 문제인데, 일단 나는 라빈-카프로 문제를 해결했고, 사실 KMP든 라빈-카프든 둘 다 필요 없는 허점이 많은 문제이다. 문제 접근 방식: 아이디어는 간단하다. 기존 문자열을 2배한 문자열을, 매칭시키고 싶은 패턴 문자열과 매칭시켜서 몇번 매칭되는 지 확인하면 된다. 기존 문자열을 2배한 문자열의 길이는 최대 200만이고, 매칭시키고 싶은 패턴 문자열의 길이는 100만이기 때문에, 일반적인 나이브한 접근을 한다면 $\mathcal{O}(NM)$의 시간복잡도로 인해 터진다. 따라서 이걸 빠르게 하기 위해 KMP를 쓰는데... 일단 나는 KMP를 명확하게 이해하지 못했기 때문에 ..
[C++] 1238번 파티 https://www.acmicpc.net/problem/1238 25/10/06 간단한 다익스트라 기초 문제. 문제 접근 방식: $X$에서 시작하는 다익스트라를 돌리고, 역방향 간선들을 담은 그래프에서 $X$에서 시작하는 다익스트라를 돌리면 된다. 두 다익스트라를 통해 나온 dist배열의 값들을 더하면 한 지점에서 왕복한 거리가 된다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 1238번 파티// 데이크스트라/*접근 방법:정방향 다익 + 역방향 다익*/#include #include #include using namespace std;#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie..
[C++] 17999번 Maze Connect https://www.acmicpc.net/problem/17999 25/09/30 어떻게 해야할 지는 금방 보이는 문제이지만, 어떻게 구현해야 할지가 큰 고민인 문제다. 문제 접근 방식: 문제가 영어로 되어있긴 하지만, 요약하자면, 대각선 모양으로 갇혀있는 방의 개수를 세어주면 되는 문제다. 이때 방은 외부와 연결되어있지 않은, 닫힌 한 구역을 의미한다. 그러면 자연스럽게 "그냥 BFS 쓰면 되겠네"하는 아이디어가 떠오를 것이다. 근데 문제는 입력 형식이다. 어떻게 BFS를 진행할 것인가가 결국 문제인데... 입력 형식이 일반적인 격자 형태로 주어지는 것이 아니라 격자가 45도 회전된 모양으로 주어지기 때문에 BFS를 어떻게 처리해야할 지가 고민이다. 같은 칸 이어도, 그 칸이 실제로는 하나의 칸..
[C++] 33616번 판드랄추 https://www.acmicpc.net/problem/33616 25/09/30 XOR의 성질을 이용한 재미있는 애드혹 문제다. 문제 접근 방식: 문제를 요약하면, 두 수 $A, B$가 주어지는데, 하나의 수에는 XOR연산을, 하나의 수에는 덧셈 연산을 동시에 진행한다. 이 과정을 반복하여 두 수를 같게 만들 수 있는지의 여부를 묻고, 만약 같게 만들 수 있다면 최소 연산 수가 소요되는 방법을 출력하는 문제이다. 여기서 관찰할 점들을 꼽아보면 다음과 같다. 1. 어떤 수에 덧셈 연산을 하면 항상 늘어난다. 2. 어떤 수에 XOR연산을 하면 덧셈 연산한 것 보다 더 커지게 늘어날 수는 없다. 오히려 줄어들 수도 있다. 일단 이 두 가지를 관찰하면, 다음과 같은 결론을 얻을 수 있다. 어떤 두 수..
[Python] 26076번 곰곰이의 식단 관리 2 https://www.acmicpc.net/problem/26076 25/09/12 0-1 BFS문제다. 이전에 곰곰컵에 나가서 틀린 이후에 한참동안 묵혀놨다가 해결해서 적어본다. 문제 접근 방식: 2025.09.15 - [알고리즘/백준 문제 풀이] - [Python] 3140번 GULIVER [Python] 3140번 GULIVERhttps://www.acmicpc.net/problem/3140 25/09/03 재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다. 문제 접근 방식: 두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값lighter.tistory.com기본적인 접근 방식은 위의 문제와 매우매우매우 유사하다. 단지 해당 문제는 정답이 0, 1, 2로..

티스토리툴바