본문 바로가기

(385)
[Python] 2389번 세상의 중심에서... / 13708번 모든 점을 포함하는 원 / 2626번 헬기착륙장 / 11930번 Smallest Enclosing Sphere / 9158번 Super Star / 21182번 Weird Flecks, But OK https://www.acmicpc.net/problem/2389https://www.acmicpc.net/problem/13708https://www.acmicpc.net/problem/2626https://www.acmicpc.net/problem/11930https://www.acmicpc.net/problem/9158https://www.acmicpc.net/problem/21182 24/07/27  경사 하강법(Gradient Descent)으로 백준에 있는 최소 외접원 문제들을 해결할 수 있다. 내가 볼 땐 경사 하강법만 알고 있다면 이를 통해 최소 외접원 문제를 해결하는 코드를 짜는 건 굉장히 쉽다고 생각하기 때문에 글을 작성해본다. (경사 하강법만 알고 있다면 다이아 5 4문제를 먹을 수 ..
[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..