본문 바로가기

글

 (385)
[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$개임을 ..
[Python] 1185번 유럽여행 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 24/03/21 MST 응용 문제로, 아이디어를 사용해서 MST를 구하는 문제로 "변형"시켜야 해결할 수 있다. 문제 접근 방식: 먼저 문제를 보면 최소 비용이 되도록 길을 남길 것을 요구하고 있고, 길의 개수는 $N-1$개가 되도록 하라고 했으니, MST관련 문제임을 확인할 수 있다. 그러면 어떻게 접근해야 할까? 예제 입력 1을 예시로 들며 접근해 보자. ..
[Python] 2487번 섞기 수열 https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 24/03/21 순열 사이클 분할의 개념을 알고 있으면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 모든 순열(Permutation)은 일정한 사이클들로 "분할"할 수 있다는 개념이 순열 사이클 분할이다. 순열 사이클 분할에 대해서 더 자세히 알고 싶다면 아래 링크를 참고해보자. https://en.wikipedia.org/wiki/Permutation#Cycle_notation ..

티스토리툴바