본문 바로가기

알고리즘

 (368)
[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)!$의 가짓수..
[Python] 31530번 새로운 AVL 트리 만들기 https://www.acmicpc.net/problem/31530 31530번: 새로운 AVL 트리 만들기 첫 번째, 두 번째, 세 번째, 네 번째 테스트 케이스의 경우 아래와 같이 $1$가지, $1$가지, $4$가지, $15$가지이다. www.acmicpc.net 24/03/21 간단한 DP문제로, 토글링의 방법으로 해결할 수 있는 문제다. 문제 접근 방식: DP테이블을 다음과 같이 정의하자. $$DP[i][j] = \textrm{높이가 }i\textrm{이고 가능한 균형값의 상태가 }j\textrm{일 때의 경우의 수}$$ 이때, 가능한 균형값의 상태는 다음과 같이 정의한다. $$j = 0, 1, 2 \rightarrow \{-1\} , \{0\} , \{1\}$$ $$j = 3, 4, 5 \rig..
[Python] 24553번 팰린드롬 게임 / 31648번 Palindrome Game https://www.acmicpc.net/problem/24553 24553번: 팰린드롬 게임 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1\,000$) 둘째 줄부터 $T$개의 줄에 걸쳐, 돌 무더기에 쌓여 있는 돌의 개수 $N$이 주어진다. ($1 \le N \le 10^{18}$) www.acmicpc.net https://www.acmicpc.net/problem/31648 31648번: Palindrome Game Bessie and Elsie are playing a game with a pile of stones that initially contains $S$ stones ($1\le S= 0 and DP[i-p] == 1: break else: DP[i]..
[Python] 4803번 트리 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 24/03/24 여러 방법으로 풀 수 있는 좋은 문제다. 나의 경우는 BFS로 먼저 접근했고, 이후 유니온 파인드로 다시 풀었다. 첫 번째 문제 접근 방식: BFS로 접근했다. 그러면 사이클을 어떻게 판단해야 할 지가 문제인데, 사이클 판단을 굳이 할 이유가 없었다. 왜냐하면 결국 우리는 트리의 개수를 세야 하고, 트리는 간선의 개수가 $N-1$개이면 노드의 개수가 $N$개임을 ..

티스토리툴바