Processing math: 11%

본문 바로가기

알고리즘/백준 문제 풀이

(340)

[Python] 31235번 올라올라 https://www.acmicpc.net/problem/31235 31235번: 올라올라 길이가

$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번: 최솟값, 최댓값 수열의 힘은 수열의 최솟값과 최댓값을 곱한 값이다. 길이가

$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를 출력하면 된다. 식을 ..

[Python] 30510번 토마에 함수 https://www.acmicpc.net/problem/30510 30510번: 토마에 함수 첫째 줄에 두 양의 정수

$P$ ,

$Q$ 가 공백으로 구분되어 주어진다.

$(1\le P\le Q\le 100\, 000)$ www.acmicpc.net 24/03/07 이전에 SASA컵을 검수한 적이 있었다. 사실 그때 너무 바빴어서 풀이만 생각하고 정해 코드를 짜지 않았었는데, 이 문제의 해설을 작성해보고자 한다. 문제 접근 방식: 문제를 요약하면 다음과 같다.

$x$ 가 무리수면

$f(x) = 0$

$x$ 가

$f(x) = 1$ 그 외

$x = \frac{p}{q} ; \mathrm{gcd}(p, q) = 1$ 이면

$f(x) = \frac{1}{q}$ 임의의 유리수

$\frac{P}{Q}$ 가 주어질 ..

[Python] 31540번 도박 문제 전문 상담은 국번없이 1336 https://www.acmicpc.net/problem/31540 31540번: 도박 문제 전문 상담은 국번없이 1336 첫 번째 줄에 대회 참가자의 수

$n$ , 배당의 총합을 결정할 정수 상수

$m$ ,

$t$ 가 공백으로 구분되어 주어진다.

$(1\le n, m, t\le 10^6)$ 두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는

$n$ 개 www.acmicpc.net 24/03/10 내가 검수했던 MatKor컵의 한 문제로, 전형적인 수학 문제이다. 두 가지 방법으로 풀 수 있는 좋은 문제이다. 여기서는 의도했던 정해를 중점으로 서브태스크 순으로 따라가며 설명해보고자 한다. 문제 접근 방식: 문제를 요약하면, 준혁이는 도박을 운영하는 도박 운영자고, 사람들에게 받은 돈이 총

$S$ 원이다...

[Python] 10166번 관중석 https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 24/02/13 실버 1치고는 많은 고민을 하게 한 문제이다. 각 코드 별로 어떠한 흐름을 가지고 생각했는지 적어보고자 한다. 문제 접근 방식: 처음으로 생각한 것은, 보이는 관중석이 어떤 일정한 규칙을 가지고 있어서, 그 규칙이 수식으로 표현 될 것이라는 생각이 들었다. 그 이후에 바로 보인 사실은,

$i < j$ 일때, 반지름

$i$ 가 반지름

$j$ 인 원을 가린다면, 그 가리는 관중석의 개수는 ..

목록 더보기

티스토리툴바