글 읽기 - 2261번 base case 처리 및 runtime error에 대한 질문입니다

jth 6년 전 0

안녕하세요 ~

기하 문제를 풀다가 혼자 힘으로 해결하기 버거운 부분이 몇 있어 의견을 구하고자 합니다.

code는 closest pair 문제의 전형적인 접근 방식 중 하나인 divide and conquer을 구현한 것입니다.

질문 1.

기존에는 line 26 부분에서 divide and conquer의 base case 크기를 3으로 하였습니다.

그런데 시간 초과가 심각하게 일어나서 base case의 크기를 점점더 늘려보았더니 100~1000 사이에서 가장 빠른 결과를 얻을 수 있었습니다.

다른 divide and conquer 문제에서 base case의 크기를 잘 쳐줘봐야 50~100으로 잡았던 것 같은데 왜 100이 넘는 크기에서 최적의 결과가 나오는지 궁금합니다.

질문 2.

base case를 200으로 잡고 채점을 하면 80% 까지는 통과가 되는데 매번 81% 쯤에서 런타임 에러가 뜹니다...

static 변수 및 함수를 모조리 private class에다가 넣고 돌려도 같은 지점에서 런타임 에러가 뜨고 있는데, 제 추측으로는 실제로 recursive call이 일어나기 전 데이터 입력 혹은 맨처음 arrays.sort()에서 에러가 발생하지 않을까 하는데, test case의 재연을 하기가 힘이 듭니다. 이 부분에 대해서 도움을 구합니다.

친절한 답변 미리 감사드립니다 :)

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static final int MAX = 1000*1000;
    private static Point[] points;

    private static int brute_force(int start, int end) {

        int min = MAX;
        for(int i=start; i<end; i++)
            for(int j=i+1; j<end+1; j++) {
                min = Math.min(min, euclidian_distance(points[i], points[j]));
            }

        return min;
    }

    private static int closest(int start, int end) {

        if(end-start <= 200)
            return brute_force(start, end);

        int mid = (start+end)/2;

        int min = Math.min(closest(start, mid), closest(mid+1, end));


        // find adjacent points of points[mid] closer than above distance.
        // takes O(n).
        // TODO. transform into array.
        List<Point> adjs = new ArrayList<>();
        adjs.add(points[mid]);
        int index;
        index = mid;
        while(++index < points.length && points[index].x <= points[mid].x+Math.sqrt(min))
            adjs.add(points[index]);
        index = mid;
        while(--index > 0 && points[index].x >= points[mid].x-Math.sqrt(min))
            adjs.add(points[index]);

        // O(nlogn)
        Collections.sort(adjs, new Y_comparator());

        // O(n)
        int temp;
        for(int i=0; i<adjs.size(); i++)
            for(int j=i+1; j<adjs.size() && adjs.get(j).y-adjs.get(i).y<min; j++) {
                temp = euclidian_distance(adjs.get(i), adjs.get(j));
                if(temp < min)
                    min = temp;
            }

        return min;
    }

    private static int euclidian_distance(Point p1, Point p2) {

        return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
    }

    public static void main(String[] args) throws FileNotFoundException {

        FastReader in = new FastReader(args);

        int n = in.nextInt();
        points = new Point[n];
        for(int i=0; i<n; i++)
            points[i] = new Point(in.nextInt(), in.nextInt());

        Arrays.sort(points, new X_comparator());

        System.out.print(closest(0, n-1));
   }

    private static class Point {

        public int x;
        public int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static class X_comparator implements Comparator<Point> {
        @Override
        public int compare(Point a, Point b) {
            if(a.x >= b.x)  return 1;
            else            return -1;
        }
    }

    private static class Y_comparator implements Comparator<Point> {
        @Override
        public int compare(Point a, Point b) {
            if(a.y >= b.y)  return 1;
            else            return -1;
        }
    }


    private static class FastReader {

        private BufferedReader br;
        private StringTokenizer st;

        public FastReader(String[] args) throws FileNotFoundException {
            br = new BufferedReader(new InputStreamReader(System.in));
//            br = new BufferedReader(new FileReader(args[0]));
        }
        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try                 { st = new StringTokenizer(br.readLine()); }
                catch(IOException e){ e.printStackTrace(); }
            }
            return st.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public double nextDouble() {
            return Double.parseDouble((next()));
        }
        public String nextLine() {
            String str = "";
            try                 { str = br.readLine(); }
            catch(IOException e){ e.printStackTrace(); }
            return str;
        }

    }

}

jh05013 6년 전 0

Base case를 어디까지 잡아야 최적인지는 알고리즘과 구현에 달려 있습니다.

브루트 포스가 O(N^2)이고 분할정복이 O(NlogN)이라는 점에서 분할정복이 더 효율적이지만, O-notation에 숨어 있는 상수가 다릅니다. 즉 O(N^2)이라고 하면 최대 a*N^2, O(NlogN)이라고 하면 최대 b*NlogN 이라고 할 수 있습니다. 그러므로 분할정복이 브루트 포스보다 빠르려면 N이 적당히 커야 하고, b가 커질 수록 그 기준점도 커지겠죠.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2261번 base case 처리 및 runtime error에 대한 질문입니다

jth 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말