본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[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 ..
[Python] 12887번 경로 게임 https://www.acmicpc.net/problem/12887 12887번: 경로 게임 첫째 줄에 바꿀 수 있는 하얀색 칸의 개수의 최댓값을 출력한다. www.acmicpc.net 24/03/20 BFS응용 혹은 그리디로 풀 수 있는 간단한 문제이다. 문제 접근 방식: 접근 방식은 굉장히 간단하다. 왼쪽-오른쪽 경로 중 최단 거리의 경로를 찾고, 그 경로를 제외하고 다 색칠하면 최대한 많은 하얀색 칸을 칠할 수 있을 것이라는 아이디어이다. 따라서, 현재 흰색 칸이 몇 개 있는지 구하고, BFS를 통해 최단 거리를 구한 뒤, 흰색 칸에서 최단 거리만큼을 빼주었다. 최단 거리 상의 경로는 항상 흰색 칸 일 것이며, 이를 제외한 흰색 칸을 모두 칠해야 하기 때문이다. 이를 그대로 구현하면 된다. 혹은, ..
[Python] 31235번 올라올라 https://www.acmicpc.net/problem/31235 31235번: 올라올라 길이가 $N$인 수열 $A$가 주어질 때, $N$ 이하의 양의 정수 $k$에 대하여 길이가 $N-k+1$인 수열 $B$를 다음과 같이 정의하자. $$B_{i}=\max_{i \le j \le i+k-1}A_j$$ 수열 $B$가 감소하지 않도록 하는 $k$의 최솟값 www.acmicpc.net 24/03/19 두 가지 방법으로 풀 수 있는 좋은 문제다. 그리디 + 스택으로도 풀 수 있고, 슬라이딩 윈도우+이분 탐색으로도 풀 수 있다. 개인적으로 전자가 더 쉽게 떠올릴 수 있다고 생각하지만 구현하는 데에 조금 실수가 생길 수 있고, 후자는 조금 더 어렵지만 구현하는 것이 그다지 어렵지 않아서, 어느 쪽으로 푸나 난이도..
[Python] 2206번 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 24/03/19 BFS 응용 문제로, 클래스에 있는 아주 교육적인 문제다. 한번 더 생각해야 되는 좋은 문제다. 문제 접근 방식: 기본적으로 최단 거리를 구해야 되는 문제이기 때문에 BFS를 사용해야겠다는 감은 올 것이다. 그러면 어떻게 BFS를 구현할 것이냐가 문제인데, 벽을 최대 한 칸까지 뚫을 수 있다는 점이 핵심이다. 따라서 벽을 뚫는 행위를 어떻게 구현할 것인가가..

티스토리툴바