본문 바로가기

알고리즘

 (368)
[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를 구현할 것이냐가 문제인데, 벽을 최대 한 칸까지 뚫을 수 있다는 점이 핵심이다. 따라서 벽을 뚫는 행위를 어떻게 구현할 것인가가..
[Python] 30961번 최솟값, 최댓값 https://www.acmicpc.net/problem/30961 30961번: 최솟값, 최댓값 수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가 $N$인 수열 $A$가 주어질 때, 이 수열에서 길이가 $1$ 이상인 모든 부분수열 각각의 힘을 구하여 모두 XOR한 값을 구하여라. www.acmicpc.net 24/03/18 XOR의 성질을 이용한 간단한 수학 문제다. 문제 접근 방식: 문제의 요구 사항은 수열 $A$가 주어졌을 때, $A$의 부분 수열 $B$의 최댓값과 최솟값을 곱한 값을 $C$라고 하면, $A$의 모든 부분 수열에서 나오는 $C$의 값을 모두 XOR한 값을 구하는 것이다. 즉, 다음과 같은 수식으로 나타낼 수 있다. $$\bigoplus_{B \subset A} ( \max ..
[Python] 28692번 선형 회귀는 너무 쉬워 2 https://www.acmicpc.net/problem/28692 28692번: 선형 회귀는 너무 쉬워 2 주어진 점이 $(7, 32)$, $(18, 67)$, $(40, 137)$이므로, $n = 3$, $S_x = 65$, $S_y = 236$, $S_{xx} = 1\,973$, $S_{xy} = 6\,910$이다. 즉, $a_2 = \frac{3 \times 6\,910 - 65 \times 236}{3\times 1\,973 - {65}^2} = \frac{5\,390}{1\,694}=\frac{35}{11} www.acmicpc.net 23/08/21 선형 회귀는 너무 쉬워 시리즈의 두 번째 문제이다. 얼핏 보면 어려운 문제일 것 같지만, 문제만 잘 읽으면 쉽게 해결할 수 있다. 문제 접근 방..
[Python] 27295번 선형 회귀는 너무 쉬워 1 https://www.acmicpc.net/problem/27295 27295번: 선형 회귀는 너무 쉬워 1 유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중을 하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 더 어려운 문제를 내 www.acmicpc.net 23/01/30 선형 회귀는 너무 쉬워 시리즈의 첫 번째 문제이다. 간단한 선형 방정식을 풀면 되는 문제다. 문제 접근 방식: 문제의 요구 사항은 $b$가 주어지고 각 데이터들이 주어질 때, $\sum_{i=1}^{n} (ax_i + b - y_i)$가 $0$에 가장 가깝도록 하는 $a$의 값을 구하는 것이다. 가능한 $a$의 값이 여러 개라면 EZPZ를 출력하면 된다. 식을 ..

티스토리툴바