2024. 7. 11. 17:21ㆍ카테고리 없음
7월은 시험의 달
모두 화이팅
Ⅰ. 문제 상황 설명
“동현이의 몬테카를로 방법”
동현이(가명)는 요즘 고급수학을 공부하면서 ‘몬테카를로 방법' 이라는 것에 대해 배우고 있다. 그러나 안타깝게도, 동현이는 요즘 새벽 1시까지 잠을 자지 않아 머리가 다소 피로해져있는 탓에, 공부를 하려고 하면 머리가 잘 돌아가지 않아 이해를 잘 하지 못하고 있다… 따라서 우리는 동현이가 고급수학을 잘봐서 조진 시험에 붙을 수 있도록 도와야 한다!
우리는 동현이가 몬테카를로 방법을 이해할 수 있도록, 동현이가 시뮬레이션을 돌릴 샘플의 수(N)와 원의 반지름(R)을 입력하면 이를 바탕으로 matplotlib 라이브러리를 이용해 점을 찍은 것을 그래프로 나타내 시각화를 하고, 원의 넓이도 구해서 출력해야 한다.
- 입력 조건:
샘플의 수(N)와 반지름(R)이 한 줄에 입력된다. (N, R은 1이상 2147483647 이하의 자연수)
- 출력 조건:
점을 찍어서 원 내부에 있는 점은 빨간색(red), 외부의 점은 파란색(blue)로 점을 찍어 표현한다. 이때, 점의 크기는 1(s=1)이다.
원의 넓이를 출력할 때는 소수점 6번째 자리에서 반올림해서 소수점 5번째 자리까지 나타내어야 한다.
- 도움말:
그래프를 출력할 때 scatter 그래프를 사용하고 조건 외에 다른 값은 건드리지 않고 기본값으로 사용한다.
반올림할 때에는 round() 함수를 이용해야 한다.
random 함수의 seed는 42로 사용한다.
- 입력 예시:
10000 1
- 출력 예시:
3.126
Ⅱ. 문제 풀이 전략
1. 기본 설정
from random import *
import matplotlib.pyplot as plt
seed(42)
x_arr_r = []
y_arr_r = []
x_arr_b = []
y_arr_b = []random 라이브러리와 matplotlib 라이브러리를 호출하고 random seed를 42로 설정한다. 이는 일정한 문제 상황에서 항상 ‘같은 무작위성을 가진' 답이 나오기 위함이다.
그 다음 네 가지 배열을 선언해준다. x_arr_r, y_arr_r은 원 내부 점들의 x, y좌표 배열이다. x_arr_b, y_arr_b는 원 외부 점들의 x, y좌표 배열이다. 자세한 사용은 다음 circle 메서드에서 설명되어 있다.
2. 몬테카를로 방법
def circle(samples, radius):
dot = 0
for i in range(samples):
x = uniform(0, radius)
y = uniform(0, radius)
if x**2 + y**2 <= radius**2:
dot += 1
x_arr_r.append(x)
y_arr_r.append(y)
else:
x_arr_b.append(x)
y_arr_b.append(y)
plt.scatter(x_arr_r, y_arr_r, color='red', s=1)
plt.scatter(x_arr_b, y_arr_b, color='blue', s=1)
plt.show()
return round(4*(dot/samples), 5)dot은 원 내부에 찍힌 점의 개수이고, samples는 총 샘플의 수이다.
uniform 함수를 통해 0~반지름 까지의 임의의 x, y 좌표를 설정하고 만약 해당 좌표가 원 안에 있으면 빨간색 점, 외부에 있다면 파란색 점으로 처리한다. 이를 주어진 샘플의 수(N)만큼 반복한다.
반복문이 끝났으면 그래프를 출력한 뒤, 최종적으로 round() 함수를 통해 소수점 5번째 자리까지의 원의 넓이를 반환한다.
이때 원의 넓이는 원 내부의 점(dot)을 전체 샘플의 수(samples)로 나눈 뒤, 앞의 반복문에서 사분원의 크기만 고려했으므로 이 값에 4를 곱한다.
3. 입력 받기
N, R = map(str, input().split())
N = int(N)
R = int(R)
print( circle(N, R) )N, R과 입력받고 이를 앞서 정의한 circle 메서드에 매개변수로 전달해준다.
Ⅲ. 문제에 적용한 개념 설명
몬테카를로 방법(Monte-Carlo Method)는 반복된 무작위 추출을 이용하여 함수의 값을 수리적으로 근사하는 알고리즘을 부르는 용어이다. 수학이나 물리학 등에 자주 사용되며, 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 근사적으로 계산할 때 사용된다.
몬테카를로 방법은 알고리즘의 반복과 큰 수의 계산과 관련되기 때문에 컴퓨터로 계산하는 것이 가장 적합하다. 따라서 몬테카를로 방법은 컴퓨터의 성능이 발달하기 시작하면서 같이 많이 사용되기 시작했다.
기존의 예측 방법은 주로 결정적이다. 예측에 대해 확고한 답을 제공하며 불확실성을 고려할 수 없다. 그러나 몬테카를로 방법은 확률적 모델이기에, 시뮬레이션을 할 때마다 매번 다른 결과가 나온다. (정답 소스 코드에서 random seed를 42로 고정한 것도 이와 같은 이유이다.)
이처럼 몬테카를로 방법은 항상 정확한 답을 줄 수는 없으나, 어느 정도의 자원 투입이 보장되면 상당한 수준으로 원하는 답을 근사해낼 수 있다.
몬테카를로 방법을 이용한 문제 중 대표적인 것은 바로 원주율 값을 근사해내는 것이다. 이는 위에 있는 그림에서도 볼 수 있듯이, 총 점을 찍는 개수(n)이 커질수록 원주율 값도 더 정밀하게 나온다. 즉, 더 많은 자원을 투자할수록 더 나은 결과값을 보인다는 것이다. 원주율을 구하는 과정에서 두 가지 눈여겨볼 점으로 첫째는 점이 균일하게 분포되지 않을수록 근사치가 떨어진다는 것이고, 둘째로 평균적으로 더 많은 점을 배치할수록 근사치가 개선된다는 것이다.
이를 직접 확인해보기 위해 이번 문제의 정답 소스코드를 이용해 여러 n 값을 입력해보면서 실험해본 결과, n 값이 커지면 커질수록 원주율도 더 나은 근사치를 가지고 구해내는 것을 확인해 볼 수 있었다.
Ⅳ. 시행착오
임의로 점을 찍었을 때 내부에 빨간색 점을, 외부에 파란색 점을 찍는 알고리즘을 설계하는 것이 어려웠다. 처음에는 많은 샘플의 수를 다뤄야 하기에 numpy를 이용하려 했으나, list 형태로도 그렇게 많은 시간이 걸리지 않아서 최종적으로 배열 형태로 알고리즘을 설계하게 되었다.
Ⅴ. 소스 코드
전체 소스 코드는 다음과 같다.
from random import *
import matplotlib.pyplot as plt
seed(42)
x_arr_r = []
y_arr_r = []
x_arr_b = []
y_arr_b = []
def circle(samples, radius):
dot = 0
for i in range(samples):
x = uniform(0, radius)
y = uniform(0, radius)
if x**2 + y**2 <= radius**2:
dot += 1
x_arr_r.append(x)
y_arr_r.append(y)
else:
x_arr_b.append(x)
y_arr_b.append(y)
plt.scatter(x_arr_r, y_arr_r, color='red', s=1)
plt.scatter(x_arr_b, y_arr_b, color='blue', s=1)
plt.show()
return round(4*(dot/samples), 5)
N, R = map(str, input().split())
N = int(N)
R = int(R)
print( circle(N, R) )
Ⅵ. 느낀점
몬테카를로 방법을 이론적으로만 알고 있었는데, 이번에 이러한 알고리즘을 실제로 적용해보니 재밌는 경험이었다. 또 한가지 재밌는 알고리즘을 배워가는 기분이다. 그리고 이번에는 원의 넓이를 구하는 것으로 문제를 냈었지만, 이를 잘 응용하면 원의 넓이 말고도 sin, cos 함수 등 여러 초월함수의 넓이도 근사적으로 구해낼 수 있지 않을까 생각했다. 그래서 만약 다음에 다시 기회가 찾아오게 된다면 여러 초월함수들에 대해서도 몬테카를로 방법을 적용해 문제를 만들어봐야 겠다고 생각했다.