본문 바로가기

알고리즘

 (364)
[Python] 9027번 Stadium https://www.acmicpc.net/problem/9027 24/07/22  지난 주 주간 연습 문제 중 하나로 뽑았던 문제인데, 개인적으로 누적 합 알고리즘을 적용하기에 좋은 문제인 것 같아서 쉽지만 해설을 작성해보고자 한다. 문제 접근 방식:  먼저 문제에서 요구하는 바를 보자. $N$개의 마을 중 한 곳을 선택하여 돔 구장을 짓고자 하고, 각 마을마다 팬이 몇 명 살고있는지, 각 마을의 위치가 어떠한지 또한 주어진다. 각 마을의 위치는 오름차순으로 주어진다.이때 문제에서 요구하는 것은 모든 팬들이 돔 구장으로 모일 때의 이동 거리의 합이 최소가 되도록 돔 구장을 지을 때, 돔 구장의 위치를 출력하는 것이다. 문제 설명의 편의 상 $i$번째 마을의 위치를 $v_i$, 돔 구장의 위치를 $d$,..
[Atcoder] ABC 361 A번 - Insert (1:41, +, AC) 길이 $N$짜리 배열 $A$가 주어지고 인덱스 $K$번째에 원소 $B$를 삽입하여 출력하는 문제.파이썬에서는 insert라는 함수를 사용하면 된다.B번 - Intersection of Cuboids (32:37, +4, AC)이 문제 때문에 그냥 이번 ABC가 다 말림.입력 예제만 보고 4번이나 잘못짜서 그냥 망침.마지막에는 다 갈아엎고 다시 짰음.핵심은 $x, y, z$축은 전부 다 따로 봐도 되고, 하나의 구간이 다른 구간이랑 겹치는지의 여부만 판단하면 됨.하나의 구간이 다른 구간이랑 겹친다면, 구간의 형태는 [max(왼쪽들), min(오른쪽들)]이다.따라서 이를 활용하여 함수를 구현하고, 그걸 각 축마다 해준다.백준에 이 문제의 상위호환 문제가 있는데,..
[Python] 17367번 공교육 도박 https://www.acmicpc.net/problem/17367 24/07/05  살짝 변형된 확률 DP문제이다. 기댓값의 의미를 되살리며 문제를 해결해보자. 문제 접근 방식:  모든 게임의 상태는 마지막 주사위 눈금 3개에 의해 결정되고, 주사위를 몇 번 던질 수 있는 지에 의해 결정이 된다. 따라서 4차원 확률 DP로 문제를 해결할 수 있다. 먼저 마지막 주사위 눈금 3개를 입력받으면 이에 대한 상금을 반환하는 prize(d1, d2, d3)를 구현하자. 수찬이가 받을 수 있는 상금의 기댓값이 최대가 되도록 게임을 한다는 말이 무슨 말일까? 이 말은, 현재 상태에서 수찬이가 주사위를 굴려서 상금의 기댓값이 올라간다면 주사위를 굴리고, 그렇지 않다면 현재 상태에서 얻을 수 있는 상금이 최댓값이 된다..
[Python] 17371번 이사 https://www.acmicpc.net/problem/17371 24/07/05  처음 풀었을 땐 예제보고 신뢰의 제출 했는데, 증명해보려고 한다. 문제 접근 방식:  문제 제한을 보면 $N = 1000$이여서 최대 $\mathcal{O}(N^2\log N)$의 시간 복잡도로 통과할 수 있다.(해설을 읽어보니 이것이 원래 문제의도였다고 한다.) 문제의 요구 조건은 어떤 점 $P$에 대하여, $P$와 가장 가까운 편의 시설 $A$의 거리와 $P$와 가장 먼 편의 시설 $B$의 거리의 평균이 가장 최소가 되도록 점 $P$의 좌표를 구하는 것이다. 문제 예제를 잘 관찰하면 이러한 점 $P$의 좌표가 사실은 그냥 문제에서 주어진 편의 시설로 잡아도 괜찮다는 것을 알 수 있다. UCPC공식 해설에서는 이를 다..
[24/07/04] UCPC 2019 예선 https://www.acmicpc.net/category/detail/2053A번 - import sysinput = sys.stdin.readlineprint([1, 2, 3, 4, 5, 4, 3, 2][int(input()) % 8 - 1])B번 -좀 귀찮은 구현. 빠르게 구현하는 실력을 길러보자.# 17363번 우유가 넘어지면?# 구현import sysinput = sys.stdin.readlineN, M = map(int, input().split())translate = {'.': '.', 'O': 'O', '-':'|', '|':'-', '/':"\\", '\\':'/', '^':'', '>':'^'}mat = [list(input().rstrip()) for _ in ..
[24/07/04] Latin America Regional Contests 2022 https://www.acmicpc.net/category/detail/3579A번 - (업솔빙 예정)B번 - (업솔빙 예정)C번 - (업솔빙 예정)D번 - (업솔빙 예정)E번 - (업솔빙 예정)F번 - (업솔빙 예정)G번 -(업솔빙 예정)H번 -(업솔빙 예정)I번 -(업솔빙 예정)J번 -(업솔빙 예정)K번 -(업솔빙 예정)L번 -(업솔빙 예정)M번 -(업솔빙 예정)
[Python] 17623번 괄호 https://www.acmicpc.net/problem/17623 24/07/01  업다운 랜디를 하다가 만난 문제이다. 복습 겸 의식의 흐름대로 적어보고자 한다. 문제 접근 방식:  요구 사항은 다음과 같다. 괄호 문자열은 소괄호, 중괄호, 대괄호로 만들 수 있음.괄호 문자열은 두 괄호 문자열을 서로 Concatenate하거나 하나의 괄호 문자열을 감싸면 만들 수 있음.val함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.또한 dmap함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.어떤 정수 $N$이 주어질 때, $val(x) = N$이 되도록 하는 괄호 문자열 $x$를 찾는 것이 우리의 목적임.이러한 $x$가 여러 개 있다면 $dmap(x)$가 최소가 되도록 하는 것이 우리의 목적임. dma..
[Python] 3673번 나눌 수 있는 부분 수열 https://www.acmicpc.net/problem/3673 24/07/01  간단한 조합론 + 누적 합 문제이다. 업다운 랜디를 하며 풀었다. 문제 풀이 방식 자체는 간단하지만 이를 떠올리는 과정이 좋은 것 같아서 적어보고자 한다. 문제 접근 방식:  요구 사항은 연속하는 부분 수열의 합이 $d$로 나누어 떨어지는 것의 개수를 구하는 것이다.(물론 원래 수열 $A$도 주어지고, $d$값도 주어진다.) 나의 의식의 흐름은 다음과 같았다. 수열의 크기가 테스트 케이스 하나당 최대 5만 정도임. $\rightarrow$ 테스트 케이스 수는 최대 $200$임. $\rightarrow$ 둘을 곱하면 1000만정도 되므로, 하나의 테스트 케이스 당 $\mathcal{O}(N)$의 시간 복잡도로 문제를 해결해..

티스토리툴바