[Python] 2389번 세상의 중심에서... / 13708번 모든 점을 포함하는 원 / 2626번 헬기착륙장 / 11930번 Smallest Enclosing Sphere / 9158번 Super Star / 21182번 Weird Flecks, But OK

https://www.acmicpc.net/problem/2389

https://www.acmicpc.net/problem/13708

https://www.acmicpc.net/problem/2626

https://www.acmicpc.net/problem/11930

https://www.acmicpc.net/problem/9158

https://www.acmicpc.net/problem/21182

---

 

24/07/27

 

 

경사 하강법(Gradient Descent)으로 백준에 있는 최소 외접원 문제들을 해결할 수 있다.

 

내가 볼 땐 경사 하강법만 알고 있다면 이를 통해 최소 외접원 문제를 해결하는 코드를 짜는 건 굉장히 쉽다고 생각하기 때문에 글을 작성해본다. (경사 하강법만 알고 있다면 다이아 5 4문제를 먹을 수 있다? 뿌슝빠슝)

---

 

문제 접근 방식:

 

 

최소 외접원 문제는 경사 하강법으로 최적해에 충분히 가깝게 근사할 수 있음이 밝혀져 있다.

https://hongjun7.tistory.com/25

Smallest Enclosing Circle/Sphere Problem

이와 관련되어 8년 전쯤에 글을 작성하신 hongjun7님의 블로그 글이 있다.

 

여기에 최소 외접원을 구하는 다양한 방법들을 소개한 논문의 링크가 있는데, 이를 참고하였다.

https://dspace.mit.edu/bitstream/handle/1721.1/4015/HPCES024.pdf?sequence=2

 

논문에 따르면, 최소 외접원 문제는 Convex problem로 모델링할 수 있기 때문에, Convex problem을 해결하는 어떠한 프로그래밍 방법을 사용하든 해결할 수 있다고 한다.

 

나의 경우 논문의 2.2에 해당하는 Subgradient method를 사용하여 구현하였다.

 

점들이 $N$개 분포해있다고 하자.

 

이때, 모든 점의 평균을 낸 점을 초기 외접원의 중심으로 잡고, 다음과 같은 작업을 반복 수행한다.

 

1. 원의 중심과 가장 멀리 떨어진 점과의 거리를 구한다. 이 거리를 $r$이라고 하자.

 

2. 가장 멀리 떨어진 점 쪽으로 원의 중심을 움직인다. $\alpha r$만큼 움직인다고 하자. 여기서 $\alpha$는 일정 비율이다.

 

3. $\alpha$를 감소시킨다. 그 이유는 움직이는 거리가 단조감소 하도록 하기 위함이다.

 

이 과정을 적절히 반복하면 원하는 만큼 수렴할 수 있다. 직관적으로 그렇겠지만, 자세한 수학적 내용이 궁금하다면 논문을 읽어보자.

 

여기서 우리는 반복횟수 $K$, 일정 비율 $\alpha$, $\alpha$를 감소시키는 decay rate $D$등을 경험적으로 조절해가며 구할 수 있다.

 

시간 복잡도는 $\mathcal{O}(NK)$이다.

 

위에 있는 2389, 13708, 2626번은 2차원에서 이 짓거리를 하면 되고, 11930, 9158번은 3차원에서 이 짓을 하면 된다. 21182번은 좌표를 xy평면, yz평면, zx평면 각각에 사영시켜서 최소 외접원을 3번 구하면 된다.

 

6문제를 위의 방식으로 풀면 코드만 살짝 바꿔주면 되기 때문에 코드는 하나만 올리겠다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2389번 세상의 중심에서...
# 휴리스틱
'''
접근 방법:
경사 하강법
'''
import sys
input = sys.stdin.readline

N = int(input())
point_list = []
for _ in range(N):
    x, y = map(float, input().split())
    point_list.append((x, y))

before_x, before_y = sum(x[0] for x in point_list)/N, sum(x[1] for x in point_list)/N
rsquare = 0
weight = 0.05
for x, y in point_list:
    rsquare = max(rsquare, (before_x-x)**2+(before_y-y)**2)
for _ in range(800):
    farthest_d = 0
    farthest_x, farthest_y = 0, 0
    for x, y in point_list:
        d = (before_x - x)**2 + (before_y - y)**2
        if d >= farthest_d:
            farthest_d , farthest_x, farthest_y = d, x, y
    rsquare = farthest_d
    before_x += (farthest_x-before_x)*weight
    before_y += (farthest_y-before_y)*weight
    weight *= 0.994

print(before_x, before_y, rsquare**0.5)