본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 1199번 오일러 회로 https://www.acmicpc.net/problem/1199 24/09/01  오일러 경로 기본 문제이다. 알고리즘은 간단했으나 시간이 좀 빡빡해서 몇 번의 최적화를 거친 후에야 맞았습니다를 받을 수 있었다. 문제 접근 방식:  무방향 연결 그래프에서 오일러 경로는 정점의 차수가 홀수인 정점이 $0$개이거나 $2$개일 때 만들어 질 수 있다. 차수가 홀수인 정점이 $0$개인 경우, 어느 점에서 시작을 하던 간에 다시 그 점으로 돌아오는 오일러 "회로"를 만들 수 있다. 차수가 홀수인 정점이 $2$개인 경우, 차수가 홀수인 $A$ 정점에서 시작하여 차수가 홀수인 $B$ 정점으로 도착하는 오일러 경로를 만들 수 있다. 이 문제는 오일러 "회로"가 만들어지는 조건을 물어보고 있으며, 그것이 가능한 경우 ..
[Python] 19171번 Euclid https://www.acmicpc.net/problem/19171 24/07/29  어제부터 잡았던 문제인데, 사실 개뻘짓을 하고 있음을 깨달아서 그냥 어이 없어서 적어본다. 문제 접근 방식:  문제에서 요구하는 것은, 세 점 $p_1, p_2, p_3$가 주어지고 어떤 점 $p$에 대하여, $p$와 세 점 사이의 거리의 합이 최소가 될 때, 그 거리의 합을 구하는 것이다. $p_1, p_2, p_3 = (x_1, y_1, z_1), (x_2, y_2, z_2), (x_3, y_3, z_3)$라고 둔다면 다음과 같은 함수를 최소화하는 문제로 바뀐다. $$\begin{align} f(x, y, z) &= \sqrt{(x-x_1)^2 + (y-y_1)^2 + (z-z_1)^2} \\ &+ \sqrt{(x-..
[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$,..
[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공식 해설에서는 이를 다..
[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)$의 시간 복잡도로 문제를 해결해..

티스토리툴바