알고리즘 문제를 풀다 보면
정확한 공식을 바로 쓰기보다,
실험을 여러 번 반복해서 대략적인 값을 추정하는 문제를 만날 수 있습니다.
이번 글에서는 무작위 좌표를 이용해
지도 안에서 특정 안전구역이 차지하는 비율을 추정하는 문제를 정리해보겠습니다.
이런 방식은 Monte Carlo 시뮬레이션이라고 부릅니다.
문제
한 게임 맵은 정사각형 형태입니다.
맵의 좌표 범위는 다음과 같습니다.
x: 0 이상 100 이하
y: 0 이상 100 이하
이 맵 안에는 안전구역이 하나 있습니다.
안전구역은 중심이 (50, 50)이고,
반지름이 30인 원형 구역입니다.
플레이어가 맵 안의 임의 위치에 나타난다고 할 때,
플레이어가 안전구역 안에 등장할 확률을 시뮬레이션으로 추정하는 함수를 작성하세요.
결과는 0 이상 1 이하의 비율로 반환합니다.
함수 형식
estimate_safe_zone_rate(trials)
trials: 무작위 위치를 생성할 횟수- 반환값: 안전구역 안에 들어간 비율
예시
입력: 100000
출력 예시: 0.283
출력값은 실행할 때마다 조금 달라질 수 있습니다.
무작위 좌표를 사용하기 때문입니다.
처음 떠오르는 생각
이 문제는 정확한 면적 공식을 직접 계산하는 문제가 아닙니다.
핵심은 아래처럼 생각하는 것입니다.
- 무작위 좌표를 많이 생성합니다
- 각 좌표가 안전구역 안에 들어가는지 확인합니다
- 전체 실험 중 안전구역 안에 들어간 비율을 구합니다
즉, 값을 바로 계산하는 대신
실험을 반복해서 비율을 추정하는 과정을 코드로 만드는 것이 중요합니다.
핵심 아이디어
플레이어가 맵 안의 아무 위치에나 등장한다고 가정하면,
무작위로 좌표를 많이 찍어볼 수 있습니다.
그리고 그 좌표가 안전구역 안에 들어가는지 확인합니다.
예를 들어 100,000번 좌표를 생성했는데
그중 28,300번이 안전구역 안이었다면,
안전구역 안에 등장할 확률은 대략 이렇게 볼 수 있습니다.
28300 / 100000 = 0.283
즉, 전체 실험 중 성공한 비율을 구하는 문제입니다.
안전구역 안에 있는지 확인하기
안전구역의 중심은 (50, 50)이고 반지름은 30입니다.
어떤 좌표 (x, y)가 안전구역 안에 있는지 확인하려면
중심으로부터의 거리를 확인하면 됩니다.
원 안에 있으려면 아래 조건을 만족해야 합니다.
(x - 50)² + (y - 50)² <= 30²
여기서 30²은 반지름의 제곱입니다.
거리 자체를 구하려고 sqrt를 사용할 수도 있지만,
굳이 제곱근을 계산하지 않아도 됩니다.
양쪽을 제곱한 상태로 비교하면 되기 때문입니다.
코드
import random
def estimate_safe_zone_rate(trials):
inside = 0
center_x = 50
center_y = 50
radius = 30
for _ in range(trials):
x = random.uniform(0, 100)
y = random.uniform(0, 100)
dx = x - center_x
dy = y - center_y
if dx * dx + dy * dy <= radius * radius:
inside += 1
return round(inside / trials, 3)
코드 해설
1. 무작위 좌표 생성하기
x = random.uniform(0, 100)
y = random.uniform(0, 100)
random.uniform(0, 100)은
0부터 100 사이의 실수를 무작위로 뽑습니다.
즉, 맵 안의 임의 위치 하나를 고르는 것입니다.
2. 중심으로부터 얼마나 떨어졌는지 계산하기
dx = x - center_x
dy = y - center_y
현재 좌표가 안전구역 중심에서
가로로 얼마나 떨어졌는지,
세로로 얼마나 떨어졌는지 계산합니다.
3. 안전구역 안에 있는지 확인하기
if dx * dx + dy * dy <= radius * radius:
inside += 1
이 조건을 만족하면 해당 좌표는 안전구역 안에 있습니다.
즉, 무작위로 생성된 위치가 안전구역 안에 들어간 경우입니다.
4. 비율 반환하기
return round(inside / trials, 3)
전체 실험 횟수 중
안전구역 안에 들어간 횟수의 비율을 반환합니다.
문제에서 소수점 셋째 자리까지 보려면
round(..., 3)을 사용하면 됩니다.
실행 예시
print(estimate_safe_zone_rate(1000))
print(estimate_safe_zone_rate(10000))
print(estimate_safe_zone_rate(100000))
출력 예시는 다음처럼 나올 수 있습니다.
0.295
0.281
0.284
실행할 때마다 값이 조금 달라질 수 있습니다.
하지만 실험 횟수가 많아질수록
결과는 점점 안정됩니다.
왜 실험 횟수가 많을수록 안정될까?
무작위 실험은 횟수가 적으면 운의 영향을 많이 받습니다.
예를 들어 10번만 실험하면
우연히 안전구역 안에 많이 들어갈 수도 있고,
적게 들어갈 수도 있습니다.
하지만 10만 번처럼 많이 실험하면
우연의 영향이 줄어들고 전체 비율이 안정됩니다.
쉽게 말하면:
실험 횟수가 적다 → 결과가 흔들림
실험 횟수가 많다 → 결과가 안정됨
복잡도
실험 횟수를 N이라고 하면:
- 시간 복잡도:
O(N) - 공간 복잡도:
O(1)
무작위 좌표를 N번 만들고,
각 좌표가 안전구역 안에 있는지만 확인하기 때문입니다.
이 문제에서 중요한 포인트
이 문제는 정확한 면적 공식을 직접 구하는 문제가 아닙니다.
핵심은 아래 흐름입니다.
- 무작위 좌표를 생성합니다
- 좌표가 조건을 만족하는지 확인합니다
- 조건을 만족한 횟수를 셉니다
- 전체 횟수로 나누어 비율을 구합니다
즉,
반복 실험을 통해 확률을 추정하는 문제입니다.
헷갈리기 쉬운 부분
1. 좌표 범위를 잘못 잡으면 안 됩니다
맵의 범위는 0 <= x <= 100, 0 <= y <= 100입니다.
좌표를 이 범위 밖에서 뽑으면
문제 조건과 다른 실험이 됩니다.
2. 반지름 비교는 제곱으로 해도 됩니다
거리를 구할 때 꼭 제곱근을 사용할 필요는 없습니다.
아래처럼 비교하면 충분합니다.
dx² + dy² <= radius²
이 방식이 더 간단하고 계산도 덜 합니다.
3. 매번 결과가 조금 달라도 정상입니다
이 문제는 무작위 실험을 사용합니다.
그래서 실행할 때마다 결과가 조금 달라질 수 있습니다.
이건 코드가 틀린 것이 아니라,
Monte Carlo 방식의 특징입니다.
정리
이 문제의 핵심은 한 줄입니다.
안전구역 비율 = 안전구역 안에 들어간 횟수 / 전체 실험 횟수
무작위 좌표를 많이 생성하고,
그중 안전구역 안에 들어간 좌표의 비율을 계산하면
대략적인 안전구역 커버율을 추정할 수 있습니다.
이 문제는
확률, 좌표 계산, 시뮬레이션을 함께 연습하기 좋은 문제입니다.
※ 이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.