안녕하세요.
풀어야 되는 문제에 대한 알고리즘 도움을 얻고 싶어서 글 올립니다.
풀어야 되는 문제는 2차원 평면상의 여러 개의 점들과 가장 근접한 점이 어디냐를 찾는 문제인데요.
점의 개수는 최대 20 개.
좌표의 범위는 X, Y 모두 +- 10e7 이하. 좌표는 정수입니다.
각 점들은 1~10 점 사이중 점수를 가지고 있습니다.
얻고자 하는 점은 점수가 높은 점들과 가까운 점입니다.
예제를 두 가지 들면,
찾고자 하는 대답은 한 점이구요.
왼쪽 그림은 왼쪽 위, 9 7 8 점을 가지고 있는 점들 근처가 될테고..
오른쪽 그림은 오른쪽 중간 4 5 6 7 이 모여 있는 쪽 근처에 찍히는게 이상적인 답입니다.
점수는 두 점을 직선으로 이었을 때 거리에 비례하여 떨어진다고 하구요.
같은 좌표를 가질 수는 없습니다.
점 간의 거리에 따른 점수계산 수식이 확실히 없기 때문에 직접 풀기는 애매하구요.
제가 얻고자 하는 것은 정확한 점이 아니라 대충 어느 범위 내에 점이면 되거든요.
처음에는 각 점마다 원을 그려서 좌표가 정수기 때문에 칸으로 만들어서 점에서 멀어질수록 낮은 점수를 주고,
모든 점을 돌고 나면 제일 점수가 높은 점을 선택했었는데,
이게 X Y 범위가 워낙 크다 보니까 (+-10e7)
메모리 사용량도 너무 많고 점의 숫자는 적은데 멀리 떨어져 있을 경우 쓸데없이 오래 걸립니다 ;;
제게 도움이 될만한 알고리즘이나 힌트가 있을까요~?
룡이
안녕하세요.
풀어야 되는 문제에 대한 알고리즘 도움을 얻고 싶어서 글 올립니다.
풀어야 되는 문제는 2차원 평면상의 여러 개의 점들과 가장 근접한 점이 어디냐를 찾는 문제인데요.
점의 개수는 최대 20 개.
좌표의 범위는 X, Y 모두 +- 10e7 이하. 좌표는 정수입니다.
각 점들은 1~10 점 사이중 점수를 가지고 있습니다.
얻고자 하는 점은 점수가 높은 점들과 가까운 점입니다.
예제를 두 가지 들면,
찾고자 하는 대답은 한 점이구요.
왼쪽 그림은 왼쪽 위, 9 7 8 점을 가지고 있는 점들 근처가 될테고..
오른쪽 그림은 오른쪽 중간 4 5 6 7 이 모여 있는 쪽 근처에 찍히는게 이상적인 답입니다.
점수는 두 점을 직선으로 이었을 때 거리에 비례하여 떨어진다고 하구요.
같은 좌표를 가질 수는 없습니다.
점 간의 거리에 따른 점수계산 수식이 확실히 없기 때문에 직접 풀기는 애매하구요.
제가 얻고자 하는 것은 정확한 점이 아니라 대충 어느 범위 내에 점이면 되거든요.
처음에는 각 점마다 원을 그려서 좌표가 정수기 때문에 칸으로 만들어서 점에서 멀어질수록 낮은 점수를 주고,
모든 점을 돌고 나면 제일 점수가 높은 점을 선택했었는데,
이게 X Y 범위가 워낙 크다 보니까 (+-10e7)
메모리 사용량도 너무 많고 점의 숫자는 적은데 멀리 떨어져 있을 경우 쓸데없이 오래 걸립니다 ;;
제게 도움이 될만한 알고리즘이나 힌트가 있을까요~?
14년 전