본문 바로가기

알고리즘

 (371)
[Python] 1344번 축구 https://www.acmicpc.net/problem/1344 1344번: 축구 홍준이는 축구 경기를 보고 있다. 그러다가 홍준이는 역시 두 팀 중 적어도 한 팀이 골을 소수로 득점할 확률이 궁금해 졌다. 축구 경기는 90분동안 이루어지고, 분석을 쉽게하기 위해서 경기를 5 www.acmicpc.net 23/08/21 또 다른 확률 DP문제이다. 복습해 보고자 글을 작성한다. 첫 번째 접근 방식: 첫 번째 접근 방식은 확률 DP이다. 나는 다음과 같이 DP테이블을 정의하였다. $$DP[i][j][k] = i번째 \ 구간에서 \ j번째 \ 팀이 \ k점이 \ 될 \ 확률$$ 팀은 $2$팀 밖에 없고, 각 팀이 점수를 얻는 데에는 서로가 서로에게 간섭하지 않으므로, 우리는 한 팀에 대해서만 생각해도 충분..
[구름톤 챌린지] 2주차 6일차 문자열 나누기 문제 길이가 $N$인 문자열 $S$가 주어진다. 플레이어는 문자열 $S$를 서로 겹치지 않는 $3$개의 부분문자열로 나누려고 한다. 부분문자열은 모두 길이가 $1$ 이상이어야 하며, 원래 문자열에서 연속해야 한다. 문자열을 나누는 방법에 따라 플레이어는 점수를 얻을 수 있다. 점수는 다음 과정에 따라 계산된다. 문자열 $S$를 위 조건에 따라 나눴을 때, 등장하는 모든 부분문자열을 중복 제거하고 사전순으로 정렬한 결과를 $P$라고 한다. 나누어진 $3$개의 문자열이 각각 $P$에서 $i, j, k$번째로 등장하는 문자열이라면, 얻을 수 있는 점수는 $i+j+k$이다. 예를 들어, abcd 라는 문자열을 $3$개의 부분문자열로 나누는 방법은 {a, b, cd}, {a, bc, d}, {ab, c, d} 의..
[Python] 15488번 나이트가 체스판을 벗어나지 않을 확률 https://www.acmicpc.net/problem/15488 15488번: 나이트가 체스판을 벗어나지 않을 확률 첫째 줄에 N, 나이트의 좌표 x, y, 이동 횟수 K가 주어진다. (1 ≤ N ≤ 50, 1 ≤ x, y ≤ N, 0 ≤ K ≤ 50) www.acmicpc.net 23/08/18 확률DP 문제로, 이 유형을 처음 접해봤기 때문에 복습을 해보고자 글을 작성한다. 첫 번째 접근 방식: 처음 접근 방식은 BFS를 구현하여 직접 나이트를 옮기면서 나올 수 있는 확률들을 모두 곱하는 방식이었다. 이 방식은 다음과 같다. 우리는 나이트가 $K$번 이동한다는 사실을 알고 있고, 나이트가 체스판을 벗어나는 이동을 하는 순간, 그 즉시 더 이상 움직일 수 없다는 것 또한 알고 있다. 기본적인 방법은..
[구름톤 챌린지] 1주차 5일차 이진수 정렬 문제 $N$개의 10진수 정수가 주어진다. 플레이어에게 정수를 그냥 정렬하는 것은 너무 쉽기 때문에, 아래 기준에 따라 정수를 정렬하기로 한다. 10진수 정수를 2진수로 나타냈을 때, 2진수에 포함된 $1$의 개수를 기준으로 내림차순 정렬한다. $1$의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다. 플레이어가 정수를 잘 정렬했을 때, 앞에서 $K$번째에 위치한 수는 어떤 수가 될 지 구해보자. 입력 첫째 줄에 주어지는 정수의 수 $N$과 플레이어가 찾으려는 정수의 위치 $K$가 공백을 두고 주어진다. 둘째 줄에 정수 $a_1, a_2, \cdots, a_N$이 공백을 두고 주어진다. $1 \leq N \leq 500\ 000$ $1 \leq K \leq N$ $1 \leq a_i \leq ..
[구름톤 챌린지] 1주차 4일차 완벽한 햄버거 만들기 문제 구름 햄버거는 다양한 재료를 사용하여 만들어서 맛있기로 유명하다. 구름 햄버거는 $N$개의 재료를 순서대로 쌓아서 만들고, 구름 햄버거의 맛은 사용된 모든 재료의 맛의 정도를 더한 값이다. 완벽한 구름 햄버거를 만들기 위해서는 맛의 정도가 가장 높은 재료를 기준으로 위랑 아래로 갈수록 재료의 맛의 정도가 감소하거나 같아야 한다. 플레이어는 $N$개의 재료를 순서대로 쌓아서 구름 햄버거를 하나 만들었다. $i$번째로 쌓은 재료의 맛의 정도가 $k_i$라고 할 때, 플레이어가 만든 구름 햄버거의 맛을 구해보자. 만약 플레이어가 완벽하지 않은 구름 햄버거를 만들었다면 0을 출력한다. 입력 첫째 줄에 구름 햄버거에 들어가는 재료의 개수 $N$개가 주어진다. 그다음 줄에 플레이어가 햄버거를 만들 때 쓴 재료..
[구름톤 챌린지] 1주차 3일차 합 계산기 문제 보통의 계산기는 한 번에 하나의 계산 결과만 나타낼 수 있다. 그래서 여러 개의 계산 결과가 필요한 경우에는 이전 계산 결과를 따로 기록해 둬야 하는 번거로움이 있었다. 플레이어는 이러한 점을 해결하기 위해서 합 계산기를 만들었다. 합 계산기는 여러 개의 계산식을 입력받은 뒤, 각각의 계산 결과를 모두 합해서 출력하는 기능을 가지고 있다. 합 계산기에 입력할 수 있는 계산식은 아래 조건을 만족해야 한다. 계산식은 형태이다. 에는 더하기, 빼기, 곱하기, 나누기의 네 가지 사칙 연산 기호가 들어갈 수 있다. 이때, 나눗셈 결과의 나머지는 버린다. 합 계산기에 입력할 $T$개의 계산식이 주어질 때, 합 계산기의 출력 결과를 구해보자. 입력 첫째 줄에 식의 개수 $T$가 주어진다. 다음 $T$개의 줄에는..
[구름톤 챌린지] 1주차 2일차 프로젝트 매니징 문제 플레이어는 구름 프로젝트의 일정을 관리하는 PM(프로젝트 매니저)이자 유일한 개발자다. 현재 구름 프로젝트를 완수하기 위해서는 $N$개의 기능 개발이 추가로 필요하다. 각 기능에는 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번째 기능을 개발하는 데는 $c_i$분의 시간이 걸린다. 플레이어는 프로젝트를 기한 안에 끝내기 위해 철야 작업에 들어갔다. 플레이어가 철야 작업을 시작한 시각은 $T$시 $M$분이다. 플레이어는 $1$번 기능부터 순서대로 개발을 진행하고, 한 기능 개발을 끝마치면 바로 다음 기능의 개발을 시작한다. 플레이어가 모든 기능 개발을 끝마친 시각을 구해보자. 입력 첫째 줄에 필요한 기능의 개수 $N$이 주어진다. 둘째 줄에 두 정수 $T, M$이 공백을 두고 주어진다. 이는 현..
[구름톤 챌린지] 1주차 1일차 운동 중독 플레이어 문제 근력 운동을 할 때, 1회에 최대한으로 들 수 있는 무게를 $1RM$이라고 한다. 본인의 $1RM$이 얼마나 되는지를 알아야 효율적인 운동 방식을 고를 수 있어 $1RM$을 측정하는 것은 무척 중요하다. 그러나 무작정 무거운 무게를 들어서 측정하는 방식은 다칠 위험이 크므로, 보통은 다양한 공식을 사용해서 $1RM$을 추정한다. 최대 무게가 아닌 적당한 무게를 몇 번 반복해 들었나를 가지고 내가 한 번에 들 수 있는 최대 무게를 추정하는 식이다. 이번 문제에서는 아래와 같은 공식을 사용한다. $W$는 무게, $R$은 반복 횟수를 의미한다. $$1RM = W \times (1 + \frac {R} {30})$$ 최근에 운동을 시작한 플레이어는 본인의 운동 기록을 바탕으로 $1RM$을 계산하려고 한다...

티스토리툴바