본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 20302번 민트 초코 https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 24/02/13 자잘한 실수를 많이 해 애를 많이 먹었던 문제입니다. 제가 잘못 접근했던 순으로 문제를 설명하고자 합니다. 문제 접근 방식: 문제에서 주어지는 정보는 간단합니다. 주어진 수식을 순서대로 계산하고, 그 결과가 정수인지 유리수인지 판별하는 것입니다. 파이썬을 사용하고 있다면 가장 흔하게 저지를 수 있는 실수는, 너무 간단한 풀이를 떠올려 구현하는 것입니다. 1. 파이썬에는 eval()이라는 함수가 존재해서, 주어진 수식의 값을 계산해줍니다. 이를 사용하..
[Python] 5069번 미로에 갇힌 상근 https://www.acmicpc.net/problem/5069 5069번: 미로에 갇힌 상근 상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다 www.acmicpc.net 24/02/01 DP문제로, 골드 4보다는 훨씬 어렵다고 느껴졌던 문제입니다. 문제 접근 방식: 처음에 접근했던 방식은, 초기 몇 개의 항을 문제에서 주어진 그대로 브루트포스+백트래킹을 사용하여 구한 뒤, OEIS를 이용해 답을 구한 방식이었습니다. 이 문제에 대한 OEIS링크는 아래에 있습니다. https://oeis.org/A002898 A002898 - OEIS A002898 Number..
[Python] 31532번 선형 회귀는 너무 쉬워 3 https://www.acmicpc.net/problem/31532 31532번: 선형 회귀는 너무 쉬워 3 첫 번째 줄에 $f_3(a)$의 값이 $0$에 가장 가깝게 하는 $a$, 즉, $a_3$을 출력한다. 답이 여러 가지라면 그중 아무거나 하나 출력한다. 가능한 정답 중 최소 하나 이상과의 절대오차 또는 상대오차가 $10 www.acmicpc.net 24/03/12 지난 겨울 MatKor Cup에 나왔던 문제로, 단순한 수치해석 문제입니다. 선형 회귀는 너무 쉬워 시리즈의 3번째 문제에 해당됩니다. 서브태스크 별로 문제 해설을 해보겠습니다. 문제 접근 방식: 서브태스크 1 ($b = 0;y_i = 0$) 모든 데이터(점)들의 $y$값 들이 $0$이고, 직선의 $y$절편이 $0$으로 주어져 있습니다...
[Python] 31478번 포니 양은 놀고 싶어! https://www.acmicpc.net/problem/31478 31478번: 포니 양은 놀고 싶어! 첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$) www.acmicpc.net 24/04/15 간단한 정수론 문제입니다. 분할 정복을 이용한 거듭제곱에 관한 지식과, 페르마의 소정리에 관한 지식이 있어야 해결할 수 있습니다. 문제 접근 방식: 결국 $A^{B^C}$와 $B^C / A$를 빨리 구하는 문제로 귀결됩니다. 후자는 빠르게 구할 수 있습니다. 결국 $7$일이라는 범위 안에서만 따지는 것이기 때문에 $7$..
[Python] 13987번 Six Sides https://www.acmicpc.net/problem/13987 13987번: Six Sides Print, on a single line, a floating-point value representing the probability that the first player wins, rounded and displayed to exactly five decimal places. The value should be printed with one digit before the decimal point and five digits after the dec www.acmicpc.net 24/04/06 간단한 확률론 + 사칙 연산 문제입니다. 저의 경우는 무한 등비 급수를 활용하여 해결했습니다. 문제 접근 방..
[Python] 2357번 최솟값과 최댓값 (추후 보강 예정) https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 24/03/15 대다수의 사람들이 해결한 방식인 세그먼트 트리로 해결하지 않고, 제곱근 분할법으로 해결한 문제이다. 세그먼트 트리로 해결한다면 이후 세그먼트 트리 풀이를 작성할 예정이다. 첫 번째 문제 접근 방식: 제곱근 분할법으로 해결했다. 제곱근 분할법은, 길이 $N$짜리 배열이 있다면 그 배열을 $\sqrt{N}$크기로 적당히 분할하여 시간 복잡도를 줄여..
[Python] 19240번 장난감 동맹군 https://www.acmicpc.net/problem/19240 19240번: 장난감 동맹군 당신은 N개의 동물 장난감을 이용하여 모의 전쟁 놀이를 하려고 한다. 장난감은 편의상 1부터 N까지 번호가 붙어있고, 당신은 이를 두 개의 동맹군으로 나누고 싶다. 다만 특정 장난감끼리 사 www.acmicpc.net 24/03/16 이분 그래프임을 알아낸다면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 장난감을 그래프의 노드, 동맹이 될 수 없는 장난감의 쌍을 두 노드를 이은 간선이라고 간주한다면, 동맹이 될 수 없는 장난감 쌍 끼리는 서로 다른 동맹군이어야 한다는 조건은 이분 그래프의 조건을 만족한다. 따라서 주어진 그래프가 이분 그래프의 조건을 만족함을 알아내기만 하면 충분하다. 이는 DFS로 구현..
[Python] 2682번 최대 사이클 1 https://www.acmicpc.net/problem/2682 2682번: 최대 사이클 1 P는 1부터 n까지 수로 이루어진 순열이다. 최대 사이클 1은 P(1), P(P(1)), P(P(P(1))), ... 중 최댓값이다. 예를 들어 수열 P가 (3, 2, 5, 4, 1, 7, 8, 6) 이라면 P(1) = 3 P(P(1)) = P(3) = 5 P(P(P(1))) = P(5) = 1 따라서 3, 5, www.acmicpc.net 24/03/21 순열 사이클 분할과 조합론적 지식을 활용한 문제이다. 문제 접근 방식: 어떤 순열 $P$의 최대 사이클 1의 값이 $1$이라면, $1$ 혼자서만 사이클을 생성하고, 나머지 $2$부터 $n$까지의 수들은 아무렇게 배치해도 상관없으므로, $(n-1)!$의 가짓수..

티스토리툴바