[최적화 및 문제풀이] 자연수 a³ + b³ = c³ + d³ 문제

이번 글에서는 자연수 a³ + b³ = c³ + d³ 를 만족하는 모든 조합을 구하는 문제를 해결하는 다양한 방법을 소개하고, 무식한 방법(brute force)으로 문제를 풀고, 개선해나가는 방법에 대해 알아보겠습니다.

 

 

목차

 

 

 

자연수 a³ + b³ = c³ + d³ 문제

먼저, 무식한 방법(brute force)으로 문제를 풀어보고, 중복되는 작업, 불필요한 작업 등을 제거해나가면서 개선해나가는 방법에 대해 알아보겠습니다.

 

무식한 접근(brute force) 방법

가장 먼저 떠오르는 방법은 가능한 모든 a, b, c, d 값을 대입해 보는 것입니다. 이 방식은 직관적이지만, 매우 비효율적입니다.

int n = 1000;
for (int a = 1; a <= n; a++) {
  for (int b = 1; b <= n; b++) {
    for (int c = 1; c <= n; c++) {
      for (int d = 1; d <= n; d++) {
        if (Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3)) {
          System.out.println(a + ", " + b + ", " + c + ", " + d);
        }
      }
    }
  }
}

이 알고리즘의 시간 복잡도는 O(N^4)입니다. 즉, N이 커질수록 실행 시간이 매우 오래 걸리게 됩니다. 이처럼 비효율적인 접근을 피하고 더 나은 방법을 찾아야 합니다.

 

최적화 1: 불필요한 계산 제거

d 값을 반복적으로 계산하는 대신, 주어진 a, b, c 값에 대해 d를 직접 계산할 수 있습니다. 이 방식은 시간 복잡도를 O(N^3)으로 줄여줍니다.

int n = 1000;
for (int a = 1; a <= n; a++) {
  double aCubed = Math.pow(a, 3);
  for (int b = 1; b <= n; b++) {
    double bCubed = Math.pow(b, 3);
    for (int c = 1; c <= n; c++) {
      double cCubed = Math.pow(c, 3);
      int d = (int) Math.cbrt(aCubed + bCubed - cCubed);
      if (d > 0 && aCubed + bCubed == cCubed + Math.pow(d, 3)) {
        System.out.println(a + ", " + b + ", " + c + ", " + d);
      }
    }
  }
}

이 방법은 O(N^4)에서 O(N^3)으로 성능을 개선하지만, 최적화를 더 진행할 수 있습니다.

 

최적화 2: 해시맵(HashMap) 사용으로 중복 계산 제거

문제를 더 최적화할 수 있는 방법은 해시맵(HashMap)을 활용하는 것입니다. (c, d) 쌍을 미리 계산해 저장한 뒤, 이를 통해 (a, b) 쌍을 빠르게 찾는 방식입니다. 이는 시간 복잡도를 O(N^2)로 크게 줄일 수 있습니다.

int n = 1000;
// 결과 (c^3 + d^3)를 키로 하고 (c, d) 쌍의 리스트를 값으로 저장하는 해시맵
HashMap<Double, List<Pair>> hashMap = new HashMap<>();

// c^3 + d^3 계산 후 (c, d) 쌍을 해시맵에 저장
for (int c = 1; c <= n; c++) {
  double cCubed = Math.pow(c, 3);
  for (int d = 1; d <= n; d++) {
    double dCubed = Math.pow(d, 3);
    double result = cCubed + dCubed;

    // 이 결과에 해당하는 (c, d) 쌍을 리스트에 추가
    hashMap.computeIfAbsent(result, k -> new ArrayList<>()).add(new Pair(c, d));
  }
}

// (a^3 + b^3)을 계산하고, 해시맵에서 해당하는 (c, d) 쌍을 찾아 출력
for (int a = 1; a <= n; a++) {
  double aCubed = Math.pow(a, 3);
  for (int b = 1; b <= n; b++) {
    double bCubed = Math.pow(b, 3);
    double result = aCubed + bCubed;

    // 해당 결과에 해당하는 (c, d) 쌍 리스트를 가져옴
    List<Pair> list = hashMap.get(result);

    // 리스트가 null이 아닌 경우 (a, b, c, d) 조합 출력
    if (list != null) {
      for (Pair pair : list) {
        System.out.println(a + ", " + b + ", " + pair);
      }
    }
  }
}

이 방법은 중복 계산을 제거하고, 해시맵을 이용해 결과를 저장함으로써 O(N^2)의 시간 복잡도를 달성합니다.