[Java] 자바로 프로그래밍 입문하기: 1.4. 배열 (2)

 사전 계산(Precomputation)

  어떤 응용프로그램들은 나중에 계산 작업을 쉽게 하기 위해, 미리 계산된 값들을 넣어놓는 용도로 배열을 사용합니다. 하나의 예로, 이전에 저희가 작성해보았던 조화수(<프로그램 1.3.5>, Harmonic numbers)를 계산하는 프로그램을 생각해보죠. 다음은 배열에 값을 저장하기 위한 효율적인 접근 방법입니다.

double[] H = new double[N]; for (int i =1; i < N; i++) H[i] = H[i-1] + 1.0/i;

  이렇게 작성해놓으면, 언제든지 H[i]를 통해 각 조화수를 참조할 수 있습니다. 이렇게 값을 사전 계산해놓는 것은, space-time tradeoff의 예시입니다. space-time tradeoff는 공간에 투자하는 것(값을 저장하는 것)은, 시간을 절약하는 것(이후에 다시 계산할 필요가 없는 것)이며 이것이 서로 절충된다는 것입니다. 즉 공간을 많이 사용하면 시간이 절약되고, 시간을 많이 사용하면 공간이 절약됩니다. 이런 방법은 큰 N값에선 별로 효과적이지 않지만, 작은 N값에서의 값이 자주 필요할 때 아주 효과적입니다.

반복의 간단화

  배열의 다른 응용으로는, 주어진 숫자에 해당하는 달의 이름을 출력하는 프로그램의 코드 조각을 생각해볼 수 있습니다.

if (m == 1) System.out.println("Jan"); else if (m == 2) System.out.println("Feb"); else if (m == 3) System.out.println("Mar"); else if (m == 4) System.out.println("Apr"); else if (m == 5) System.out.println("May"); else if (m == 6) System.out.println("Jun"); else if (m == 7) System.out.println("Jul"); else if (m == 8) System.out.println("Aug"); else if (m == 9) System.out.println("Sep"); else if (m == 10) System.out.println("Oct"); else if (m == 11) System.out.println("Nov"); else if (m == 12) System.out.println("Dec");

  물론 siwtch문을 이용할 수도 있습니다. 하지만 좀 더 간편한 대안으로는, 각 달의 이름을 담고 있는 String 배열을 이용하는 것입니다.

String[] months = { "", "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec" }; System.out.println(months[m]);

  여러분이 각 달의 이름을 코드의 곳곳에서 참조해야 할 때, 이런 식의 방법은 특히 더 유용해집니다. 배열의 한 칸을 의도적으로 버리면서 months[1]이 January와 일치하게끔 만들어 준 부분도 확인해보세요.

대입과 동일성 확인(Assignments and equality tests)

  a[]와 b[] 두 개의 배열을 생성했다고 생각해봅시다. 대입문 a = b; 의 의미는 무엇일까요? 비슷하게, 두 배열의 동등을 확인하기 위한 코드 (a == b) 의 의미는 무엇일까요? 이 질문들에 대한 답은 아마 여러분이 생각한 것과는 다를 것입니다. 다만 배열 메모리의 표현에 대해 생각해본다면, 이런 연산들에 대한 자바의 인식이 타당함을 확인할 수 있을 것입니다.

  대입의 경우(a = b), a라는 이름과 b라는 이름이 같은 배열을 참조하게만 만듭니다. 비슷하게, 동일성 확인(a == b) 시에는 두 변수가 같은 배열을 참조하는지를 확인합니다. 즉, 배열 내부의 값은 전혀 신경 쓰지 않습니다. 만약 이런 방식으로 구동되는 자바가 맘에 들지 않는다면, 여러분들이 직접 반복문을 작성해서 각 값을 대입하게 하고, 각 값이 동일한지를 확인하는 방법 뿐입니다.

  앞서 말한 두 경우, 즉 "대입은 해당하는 배열을 참조하게만 만들고, 동일성 확인은 두 변수가 같은 배열을 참조하는지를 확인하게만 하는 것"은, 자바에서의 구현을 굉장히 간단하게 만듭니다: 배열의 이름은, '배열의 메모리 주소 값을 지닌' 변수인 것처럼 표준 연산을 수행하면 되는 것입니다.

  여러분들이 배열에서 수행되었으면 하는 다양한 연산들이 있을 수 있겠죠. 예를 들어, 배열에서 a = a + b 라고 하는 연산의 의미는, "대응하는 b의 요소들을 각 a의 요소에 더한다"였으면 참 좋았을 것 같지만, 자바에서 이런 구문들은 허용되지 않습니다. 대신 우리는 반복문을 이용해서 배열의 모든 덧셈을 구현해야 합니다. 이 부분을 꼭 기억하세요!

  이제 이런 기초적인 정의와 예제들은 끝내고, 흥미롭고 고전적인 문제들과 배열의 효율적인 계산에 대한 근본적인 중요성을 겨냥한 두 가지 응용에 대해 알아볼 것입니다.

쿠폰 수집(Coupon collector)

  52장 세트의 카드 덱들이 무한하게 진열 되어 있고, 각 덱의 맨 윗장만 뒤집어가며 확인해본다고 생각해봅시다. 한 문양의 모든 카드를 확인하려면 몇 장의 카드를 뒤집어야 할까요? 한 숫자의 각 문양을 전부 확인하려면 몇 장의 카드를 뒤집어야 할까요? 이러한 문제는 쿠폰 수집 문제(coupon collector problem)로도 유명합니다.

  트레이딩 카드 회사는 N개의 서로 다른 카드로 트레이딩 카드를 발급한다고 가정해봅시다. 각 종류의 카드를 뽑을 확률이 같다고 생각해볼 때, 모든 N개의 카드를 전부 모으려면 얼마나 수집을 해야할까요?

  쿠폰 수집 문제는 단순히 문제를 위한 문제가 아닙니다. 예를 들어 과학자들은 자연에서 발생하는 어떤 일련의 사건들이 정말로 무작위한 순서로 나타나는 건지 궁금해합니다. 만약 그렇다면 그런 대로 흥미로운 것이고, 그렇지 않다면 무언가 패턴을 찾기 위해 추가적인 조사를 해볼 것입니다. 예를 들어, DNA에서 게놈 부분을 연구할 때 어떤 게놈이 가치가 있는지를 결정하기 위해 사용됩니다.

프로그램 1.4.2: Coupon collector simulation

public class CouponCollector { public static void main(String[] args) { // Generate random values in (0..N] until finding each one. int N = Integer.parseInt(args[0]); boolean[] found = new boolean[N]; int cardcnt = 0, valcnt = 0; while (valcnt < N) { // Generate another value. int val = (int) (Math.random() * N); cardcnt++; if (!found[val]) { valcnt++; found[val] = true; } } // N different values found. System.out.println(cardcnt); } }

% java CouponCollector 1000
6583
% java CouponCollector 1000
6477
% java CouponCollector 1000000
12782673

  <프로그램 1.4.2>는 N개의 쿠폰을 몇 회만에 전부 모을 수 있는지 시뮬레이션 하는 프로그램입니다. 0부터 N-1 사이의 값을 무작위로 추출하고, 그 값에 해당하는 found 배열의 인덱스를 확인합니다. false라면, true로 만들고 해당하는 인덱스의 쿠폰을 모은 것으로 간주합니다. 이렇게 해서, 모든 쿠폰을 모은 것으로 확인이 되면 반복문을 탈출합니다.

에라토스테네스의 채(Sieve of Eratosthenes)

  소수는 수학 및 암호학에서 중요한 역할을 합니다. 소수란 자신과 1로만 나누어 떨어지는 수입니다. 소수를 찾는 방법은 다양한데, 다음 프로그램은 에라토스테네스의 채를 이용해서 소수를 찾습니다.

프로그램 1.4.3: Sieve of Eratosthenes

public class PrimeSieve { public static void main(String[] args) { // Print the number of primes <= N. int N = Integer.parseInt(args[0]); boolean[] isPrime = new boolean[N + 1]; for (int i = 2; i <= N; i++) isPrime[i] = true; for (int i = 2; i <= N / i; i++) { if (isPrime[i]) { // Mark multiples of i as nonprime. for (int j = i; j <= N / i; j++) isPrime[i * j] = false; } } // Count the primes. int primes = 0; for (int i = 2; i <= N; i++) if (isPrime[i]) primes++; System.out.println(primes); } }

% java PrimeSieve 25
9
% java PrimeSieve 100
25
% java PrimeSieve 1000000000
50847534

  <프로그램 1.4.3>은 N보다 작은 소수들의 개수를 출력합니다. isPrime[i]의 boolean 값은 i가 소수이면 true, 아니면 false로 계산됩니다. 처음에는, 배열의 모든 값들을 true로 만들어 모두를 소수라고 생각합니다. 그 후에 소수가 아닌 숫자들을 false로 만드는데, 방법은 다음과 같습니다. i는 2부터 위로 순회하며, a[i]가 true라면 a[i]는 소수이며 a[i]의 배수는 전부 false로 만듭니다.

(계속)