[Python] 7869번 두 원
https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 22/11/09 전형적인 수학, 기하학 문제로, 제2코사인 법칙을 사용하여 문제를 해결할 수 있다. 문제 접근 방식: 이 문제를 풀기 위해서는 먼저 제2코사인 법칙을 알아야 한다. 제2코사인 법칙이란, 어떤 삼각형의 세 변과 그 대각 사이에 성립되는 관계로, 위와 같은 식을 따른다. 따라서, 내가 예를 들어, 각 B를 구하고 싶으면 저 식 중 2번째 식을 변형하여 아래와 같이 구할 수 있다. 이 식을 이용할 것이다. 먼저, 원의 위치 관계에 따라 3가지 경우로 나..
[Python] 1737번 Pibonacci
https://www.acmicpc.net/problem/1737 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/11/08 신박한 2차원 DP문제로, 처음에는 재귀를 이용한 탑다운 방식으로 접근했었으나, 재귀 시간이 너무 오래 걸려 바텀업 방식으로 전환하여 풀 수 있었던 문제다. 문제 접근 방식: 이 문제를 보면, 기존 피보나치수열의 점화식과는 다르게 아래와 같은 점화식을 가지고 있다. 맨 처음 생각한 풀이는 위의 점화식을 재귀로 구현하고, DP테이블은 딕셔너리로 구현함으로써 하려고 했다. 딕셔너리의 키는 실수 연산을 통해서 구현하려고 했다. 근데, 이..
[구름 알고리즘 먼데이 챌린지] 3주차 4번 순환하는 수로
22/11/07 DFS/BFS 문제로, 사이클을 출력하는 문제이다. 문제 접근 방식: 사실 이 문제의 해설보다 더 간단한 방법으로 나는 풀었다. 심지어 BFS, DFS도 돌리지 않았다. 나는 문제 조건의 핵심을 꿰뚫어봤다. 먼저, 문제 조건을 보면, 사이클은 단 하나만 존재한다고 했다. 때문에, 노드들과 간선들이 주어져 있으면, 노드들 중에 간선이 하나만 연결되어 있는 노드들은 사이클을 이루고 있지 않다고 생각했다. 왜냐하면, 그 노드가 사이클에 포함되어있다면, 그 노드는 최소 2개 이상의 간선에 연결되어 있기 때문이다. 이러한 이유로, 사이클을 이루고 있지 않은 노드는 그 간선과 노드를 그래프에서 제거해버렸다. 이 과정을 계속 반복하다보면 결국 사이클 하나만 남게 되는데, 이것을 오름차순으로 출력하면 ..
