과학

자바로 프로그래밍에 입문할래요: 1.4. 배열 (1)

비복원추출에 대한 코드는 경험자도 한 번은 참고해볼만한 코드인 것 같아.

수학의 순열과 조합에 대한 지식이 있다면 이해하는 데에는 얼마 걸리지 않을 거야.

막상 실제로 비복원추출의 상황을 맞닥뜨렸을 때, 효율적인 코드가 바로 생각나지 않거든.

예를 들어, 마피아 게임에서 각 역할들을 어떻게 동일한 확률로 플레이어들에게 분배할 수 있을까?

마지막에 있는 예제 코드는 이러한 문제에서 아주 멋진 해답을 제시해.

 

1.3. 조건문과 반복문 (2)

1.3. 조건문과 반복문 (1)

1.2. 내장 자료형 (2)

1.2. 내장 자료형 (1)

0.0. 여는 글, 1.1. 첫 프로그램 만들기

 

===============================

 

  이번 절에서 우리는 배열(array)이라는 기초적 프로그래밍 요소에 대해 배워볼 것입니다. 배열은 많은 양의 자료를 저장하고 다루기 위해 존재합니다. 많은 자료를 처리하는 작업에 필수적인 역할을 하죠. 또한 벡터나 행렬 등을 표현할 수 있으므로, 수학 및 과학의 프로그래밍에 많이 이용됩니다.

 

  배열은 같은 자료형을 갖는 값들의 집합입니다. 값들을 집합으로서 처리하는 경우는 흔히 볼 수 있습니다. 시험 점수나 주식의 가격, DNA의 염기, 책의 글자들 등, 이런 예시들은 전부 '숫자'라는 같은 자료형으로 이루어진 수많은 값들의 집합입니다.

 

  우리는 이런 값들을 저장하는 방법 뿐만 아니라, 접근하는 방법도 생각해봐야 할 것입니다. 자바에서는 배열의 각 값들에 번호를 매겨 참조하는 방식으로 접근합니다. 만약 N개의 값이 있다면, 이 값들은 0번부터 N-1번까지 번호를 부여받습니다. a배열의 i번째 값을 참조할 때, 우리는 a[i]라고 표기합니다. 이런 식의 구조를 1차원 배열(one-dimensional array)이라고 합니다.

 

  1차원 배열은 이 강의에서 볼 수 있는 첫번째 자료구조(data structure)입니다. 자료구조라 함은, 자료들을 정리하는 방법입니다. 후에, 우리는 더 복잡한 자료구조인 2차원 배열 또한 이번 차시에서 다룰 것입니다. 자료구조는 현대 프로그래밍에서 필수적인 역할을 하고 있으며, 챕터 4에서 이를 다뤄볼 것입니다.

 

 

자바의 배열

  자바 프로그램에서 배열을 만들기 위해서는 다음 3단계를 거쳐야 합니다.

 

  1. 배열의 이름과 자료형을 선언합니다.
  2. 배열을 생성합니다.
  3. 배열의 값을 초기화합니다.

 

  배열을 선언하기 위해서는 이름과 자료형이 포함되어야 합니다. 또한 배열을 생성하기 위해서는 배열의 크기를 명시해야 하죠. 다음은 N개의 double형 배열을 만들고, 전부 0.0으로 초기화하는 코드 조각입니다.

 

 
double[] a;
a = new double[N];
for (int i = 0; i < N; i++)
	a[i] = 0.0;

 

  첫번째 구문은 배열의 선언입니다. 배열을 선언할 때에는, 이것이 배열임을 명시하는 대괄호를 자료형 뒤에 씁니다. 해당하는 자료형의 변수 하나를 선언하는 것과 별반 다르지 않습니다.

 

  두번째 구문은 배열의 생성입니다. 이 구문은 기본 자료형을 선언할 때에는 필요가 없었죠. 따라서 여러분들은 이런 구문을 본 적이 없었을 것입니다. 하지만 기본 자료형이 아닌 자료형들을 다룰 때에는 언제나 이 구문이 필요합니다. 이 강의에서 나오는 코드들은 대부분 정수형 변수 N을 이용해서 배열의 크기를 정할 것이지만, 어떤 정수값이든 상관 없습니다.

 

  세번째 구문인 for문은 배열의 초기화입니다. 배열 이름 뒤의 괄호에 번호를 넣음으로써 참조할 수 있습니다. for문을 이용해 N개의 배열 값을 0.0으로 초기화하고 있습니다.

 

  배열을 사용하기 위해서는 선언, 생성, 초기화를 반드시 해야합니다. 이 중 하나를 빼먹는 실수는 꽤나 흔합니다. 효율적인 코딩을 위해, 세 단계를 전부 합쳐 한 구문으로 만들 수 있습니다. 

 

 
double[] a = new double[N];

 

  사실 초기화를 위한 for문은 필요하지 않습니다. 자바에서는 기본적으로 double형의 변수는 0.0으로 초기화를 해주기 때문입니다. 하지만 0이 아닌 값을 원한다면, 당연히 초기화를 해주어야 합니다. 모든 숫자 자료형에서는 0, boolean 자료형에서는 false가 기본 초기화 값입니다. String은 기본 자료형이 아니므로, 기본값은 null이며 이에 대해서는 챕터 3에서 배워볼 것입니다.

 

  배열이 강력한 이유는, 변수 각각에게 이름을 따로 지어주지 않아도 되기 때문입니다. 만약 8개의 double형 변수를 사용하고 싶다고 생각해보죠. 배열을 사용하지 않는다면, 아마 코드는 다음과 같을 것입니다.

 

 
double a0, a1, a2, a3, a4, a5, a6, a7;

 

  게다가 각각의 값을 참조하기 위해 직접 이름을 코드에 명시해주어야겠죠. 하지만 배열을 사용한다면 a[0], a[1]과 같이 명시할 수 있으며, 이는 반복문을 통해 쉽게 참조가 가능하게 됩니다. 

 

  배열의 활용에 대한 코드들을 참고하세요.

 

 

 

Zero-based indexing

  배열을 참조할 때, 첫 번째 요소는 항상 0번부터 시작합니다. 언뜻 보기에는 첫 번째 요소를 a[1]이라 하고, 두 번째 요소를 a[2]라 하는 방법이 더 자연스러워 보입니다. 하지만 0번으로 시작하게 되면 약간의 장점이 있으며, 현대 프로그래밍 언어에서 관습처럼 사용되고 있기도 합니다. 이러한 관습 때문에 off-by-one 오류가 자주 일어나게 되며, 이런 버그는 피하기도, 찾기도 힘들기로 악명이 높습니다. 조심하세요!

 

 

배열의 길이

  배열을 생성하면, 그 크기는 고정됩니다. 우리는 명시적으로 배열을 사용할 때 그 크기를 정해주며, 이는 런타임 때 이루어집니다. 다시 말하면, 컴파일 시기에는 해당 배열에게 어느정도의 공간을 주어야하는지를 알기 힘듭니다. 예를 들어 N이라는 변수를 명령행 인자로 받고, N을 통해 배열을 생성한다면, 코드를 컴파일 하는 시기에는 그 배열의 크기를 알 수 없을 것입니다. 실행되기 전까지는 N이 결정되지 않으니까요.

  따라서 자바에서는 배열 a[]의 길이를 a.length로 참조할 수 있게 합니다. a[]를 N 크기의 배열로 생성했다면, N은 a.length가 됩니다. 따라서 마지막의 배열 원소는 a[a.length-1]이 됩니다. Zero-based indexing이기 때문입니다.

 

 

배열의 메모리 표현

  배열은 거의 모든 컴퓨터 메모리 시스템과 직접 연결되어 있습니다. 따라서 이는 기본적인 자료구조라고 말할 수 있습니다. 배열의 요소들은 메모리에 연속적으로 저장되며, 이런 특성 때문에 배열의 값에 빠르게 접근하기 쉽습니다. 사실, 우리는 컴퓨터 메모리를 그 자체로 거대한 배열로 볼 수 있죠. 

 

  현대 컴퓨터에서는, 적절한 메모리에 빠르게 접근할 수 있도록 인덱스화 된 메모리 구성을 하드웨어에 구현하고 있습니다. 이는 마치 거대한 memory배열을 memory[0], memory[1]과 같은 형식으로 참조할 수 있다고 생각하면 됩니다. 컴퓨터 메모리에 접근할 때, 우리는 보통 해당 메모리의 주소를 인덱스로 참조합니다. 

 

  배열의 이름 a를, 배열의 첫째 요소의 주소인 a[0]의 메모리 주소로 생각하면 편리합니다. 컴퓨터의 메모리가 1000개의 값을 저장할 수 있고, 그 주소가 000부터 999까지라고 생각해보죠. 다음 그림을 참고해보세요. 물론 이는 언제까지나 간단하게 보여주는 그림이므로, 실제로 메모리가 저렇게 일률적인 칸을 갖는다고 생각하진 마세요.

 

 

 

 

  우리가 배열을 선언해서, 523번부터 530번까지 배열의 여덟 개 값이 저장되었다고 해봅시다. 이 상황에서, 자바는 메모리 어딘가에 배열의 첫번째 값(123번지)과 배열의 길이(124번지)만을 저장합니다. 이 경우 a에는 523이, a.length에는 배열의 길이인 8이 저장됩니다.

 

  이렇게 저장하게 된다면, 우리가 a[i]라고 명시했을 때, 컴파일러는 a[]의 메모리 주소에 인덱스인 i를 더해서 원하는 값을 참조할 수 있는 코드를 만들어냅니다. 예를 들어, 자바 코드 a[4]는 메모리 위치 a + 4 = 523 + 4 = 527의 주소를 찾아낼 것입니다. 배열의 i번째 요소에게 접근하는 것은 상당히 효율적입니다. 두 정수를 더하는 것만으로 메모리에 접근할 수 있기 때문입니다. 이는 배열이 0번부터 시작하는 이유이기도 합니다. 1번부터 시작하게 된다면, 개념적으로는 인덱스 번호를 더하고 1을 다시 빼주어야했을 터이니 말입니다. 

 

 

메모리 할당(Memory allocation)

  new 키워드를 이용해 배열을 생성할 때, 자바는 메모리 공간을 확보합니다. 이 작업을 메모리 할당이라고 합니다. 프로그램 내의 모든 변수에게는 메모리 할당 작업이 이루어집니다. 배열의 어떤 요소를 접근하기 이전에 여러분은 반드시 new 키워드를 이용해 메모리를 할당해야 할 책임이 있습니다. 만약 이 규칙을 어기게 된다면, 컴파일 시기에 uninitialized variable(초기화되지 않은 변수) 오류를 직면할 것입니다. 

 

 

경계 검사(Bound checking)

  계속 말씀드리다시피, 배열을 사용할 때에는 굉장히 조심해야 합니다. 배열 요소에 접근할 때에는 올바른 인덱스 번호를 사용해야 합니다. N 크기의 배열을 만들었다면, 0보다 작거나 N-1보다 큰 번호를 입력했을 때 ArrayIndex-OutOfBounds 라는 런타임 예외와 함께 프로그램이 종료될 것입니다.

 

  대부분의 프로그래밍 언어에서는 이와 같은 buffer overflow 조건을 시스템으로부터 확인하지 않습니다. 이런 점검하기 힘든 오류들은 여러분들을 야근의 늪으로 이끌뿐만 아니라, 프로그램이 종료되어도 메모리가 몰래 남아있는 경우도 있습니다. 심지어 이런 실수들은 해커들이 시스템, 더 나아가서 컴퓨터의 제어권을 뺏는데 이용되고, 바이러스를 감염시키고 개인 정보를 빼앗는 등 악용될 여지가 충분합니다. 에러 메시지를 접하는 것은 처음에는 짜증나겠지만, 프로그램의 안정성을 위해 지불하는 작은 대가라고 생각하세요.

 

 

컴파일 시기에 배열의 값을 설정하기

  적은 수의 리터럴 값을 배열에 넣고 싶다면, 중괄호 안에 쉼표로 구분하여 선언과 함께 초기화 할 수 있습니다. 다음 예제는 카드 게임을 구현한 프로그램의 코드 조각입니다.

 

 
String[] suit = { "Clubs", "Diamonds", "Hearts", "Spades" };
String[] rank =
{
		"2", "3", "4", "5", "6", "7", "8", "9", "10",
		"Jack", "Queen", "King", "Ace"
};

 

  크기가 각각 4와 13인 두 개의 배열을 생성함으로, 우리는 카드 뭉치에서 임의의 카드를 뽑는 효과를 이끌어낼 수 있습니다.

 

 
int i = (int) (Math.random() * rank.length);
int j = (int) (Math.random() * suit.length);
System.out.println(rank[i] + " of " + suit[j]);

 

  이 코드는 1.2절에서 보았던 임의의 경우를 생성하는 방법을 배열로 응용해본 것입니다. 이렇듯 컴파일 시기에도 배열의 모든 요소들의 값을 명시해 배열을 초기화 할 수 있습니다. 다만 배열의 크기는 크지 않아야겠죠. 이렇게 중괄호를 이용해서 선언하는 것은 곧 배열의 생성을 의미하므로, new 키워드는 따로 사용하지 않아도 됩니다.

 

 

런타임 시기에 배열의 값을 설정하기

  사실은 배열에 단순히 직접 타이핑해서 배열에 값을 집어넣기보다는, 일련의 계산 작업들을 거쳐서 값을 저장하는 것이 일반적입니다. 다음 코드 조각은 앞서 선언한 두 배열을 이용해, deck이라는 배열에 각 카드들을 저장합니다.

 

 
String[] deck = new String[suit.length * rank.length];
for (int i = 0; i < suit.length; i++)
	for (int j = 0; j < rank.length; j++)
		deck[rank.length*i + j] = rank[i] + " of " + suit[j];

 

  이 코드가 실행되면, deck[0]부터 deck[51]까지 각 카드들이 저장됩니다. 한 번 생각해보세요.

 

  • 2 of Clubs
  • 2 of Diamonds
  • 2 of Hearts
  • 2 of Spades
  • 3 of Clubs
  • 3 of Diamonds
  • ...
  • Ace of Hearts
  • Ace of Spades

 

 

배열의 두 값을 교환하기

  여러분은 배열의 두 값을 바꿀 일이 잦을 것입니다. 다음 코드 조각을 통해 i번째 배열의 값과 j번째 배열의 값을 서로 바꿀 수 있습니다. 이는 1.2절에서 대입문을 배울 때 본 것과 비슷합니다.

 

 
String t = deck[i];
deck[i] = deck[j];
deck[j] = t;

 

  우리가 이 코드를 사용할 때 확신할 수 있는 것은, 배열 값의 순서가 변할 뿐 배열 값의 조합이 변하지는 않는다는 것입니다. 만약 i와 j가 같다면, 배열은 변하지 않을 것입니다. i와 j가 같을 때 배열이 변하지 않는다는 사실은 중요한데, 다음과 같이 응용할 수 있기 때문입니다.

 

 

배열을 섞기

  다음 코드 조각은 배열을 완전히 섞습니다.

 

 
int N = deck.length;
for (int i = 0; i < N; i++)
{
	int r = i + (int) (Math.random() * (N-i));
	String t = deck[i] ;
	deck[i] = deck[r];
	deck[r] = t;
}

 

  이 코드는 deck[i] 부터 deck[N-1] 사이의 무작위 카드를, deck[i]와 교환하는 코드입니다. 이는 보기보다 수준 높고 세련된 방법입니다. 첫째, 우리는 섞은 후의 카드 덱과 섞기 전의 카드 덱이 같다는 것을 보장할 수 있습니다. 둘째, 아직 선택되지 않은 카드들로부터 균일하게 선택되어 섞입니다.

 

 

비복원추출

  아마 여러분은 비복원추출(집합의 요소가 최대 한 번만 선택되는 추출)을 구현하고 싶은 상황을 많이 맞닥뜨릴 것입니다. 로또에서 바구니에 숫자가 적힌 탁구 공을 뽑는다거나, 덱에서 카드를 뽑는다거나 하는 것이죠. 균일한 확률로 이를 뽑아내는 것은 생각보다 쉽지 않습니다.

 

 

프로그램 1.4.1: Sampling without replacement

 
public class Sample
{
	public static void main(String[] args)
	{ // Print a random sample of M integers
		// from 0 ... N-1 (no duplicates).
		int M = Integer.parseInt(args[0]);
		int N = Integer.parseInt(args[1]);
		int[] perm = new int[N];
		// Initialize perm[].
		for (int j = 0; j < N; j++)
			perm[j] = j;
		// Take sample.
		for (int i = 0; i < M; i++)
		{ // Exchange perm[i] with a random element to its right.
			int r = i + (int) (Math.random() * (N - i));
			int t = perm[r];
			perm[r] = perm[i];
			perm[i] = t;
		}
		// Print sample.
		for (int i = 0; i < M; i++)
			System.out.print(perm[i] + " ");
		System.out.println();
	}
}
% java Sample 6 16
9 5 13 1 11 8
% java Sample 10 1000
656 488 298 534 811 97 813 156 424 109

 

  <프로그램 1.4.1>은 크기가 M인 집합에서 N 길이의 무작위 순열을 출력합니다. 만약 r의 값이 주어진 범위에서 각 값을 무작위로 선택한다는 것이 보장된다면, perm[0]부터 perm[M-1]은 완벽한 임의의 순열이 될 것입니다. 선택된 각 요소들은, 아직 선택되지 않은 집합에서 선택된 것이기 때문입니다. 이 코드를 이해하는 것은, 곧 모든 배열에서 무작위 값들을 추출할 수 있다는 것입니다. 아주 중요한 부분이고 굉장히 많이 쓰이는 방법이니, 꼭 이해하고 넘어가셨으면 좋겠습니다.

 

(계속)

 

13개의 댓글

27 일 전
0

이거 다 직접 쓰는거야?

0
27 일 전
@내가옳고니가그름

프린스턴대 Robert Sedgewick 교수님의 Introduction to Programming in Java라는 책을 내가 번역해서 올리고 있어

2
@스비니

고생한다 추천줬다

0
27 일 전

오 비복원추출.. 좋은 아이디어다

 

0

잘보고있다

잼있네

0
26 일 전

비복원 추출 ㄷㄷ 콜렉션 사용하는 버릇이 들어서 그런지 suffle()로 해결하는 경우가 많았는데

저런식으로 처리할 수도 있겠군요 좋은글 잘보고있습니다.

0
26 일 전

와드 박고 갑니다. 끝까지 완주해주시길...

프로그래밍 하나도 모르는 사람입니다.ㅎㅎ

0
26 일 전

0 ~ 999 까지의 배열을 미리 선언한 뒤에, 그 배열을 무작위로 섞고, 원하는 크기만큼만 앞에서부터 선택하는거구나..

 

근데 int r = i + (int) (Math.random() * (N-i)) 이런식으로 랜덤한 값을 선택하는 이유가 뭐야??

int r = (int) (Math.random() * (N)); 직관적으로 이렇게 해봤는데 결과가 다른 게 없어 보여서 ㅠㅠ

 

올려주는게 재밌고 도움이 많이 돼서 항상 고마움!!

0
26 일 전
@라프로익15년

1. 가장 처음에 이루어지는 교환을 생각해봐. 배열의 0번부터 n번까지 중 무작위로 하나를 선택해서, 그걸 0번에 넣는 것이 되겠지?

여기서 우리가 보장할 수 있는 것은, 현재 0번에 있는 값은 완전히 무작위로 선택되었다는 것이야.

다시 말하면, 0번은 더 이상 건들 필요가 없어.

 

2. 그렇다면 다음에 이루어지는 교환은 어떨까? 배열의 1번부터 n번까지 중 무작위로 하나를 선택해서, 그걸 1번에 넣어주는 것이야.

이 역시 1번에 있는 것은 나머지 것들에서 완전한 무작위로 선택되었음을 보장할 수 있겠지?

 

3. 즉 i번부터 n번까지의 값 중 무작위로 하나를 선택해서 i번 배열에 넣어주는 것을 반복하는 거야. 이를 코드로 표현하면, 물어본 코드처럼 되는 거지.

 

4. 만약 개붕이가 쓴 코드처럼 하게 된다면, 이는 완전한 비복원 추출이 아니야. 왜냐하면, 앞서 선택된 값들 또한 무작위 추출에 포함될 수 있기 때문이야. 0번은 건들 필요 없는데 건들게 되는 셈이지. 알게 모르게 각 숫자의 확률이 다를 거야.

아마 그렇게 되면 내가 간단하게 3개 숫자만 이용해서 경우의수를 따져봤는데, 가운데 쪽에 있는 숫자가 앞쪽이나 뒤쪽으로 분포될 확률이 더 높아져.

0
24 일 전
@스비니

덕분에 이해됐음 ㅎㅎㅎ 감사감사!!

0
26 일 전

머가 좀 익숙하다 했더니 학부생때 쓰던 책이엇구나 유익함 ㅊㅊ

0

나도 자바스크립트 쓰는데 왜 안됨?

해명해! 해명해! 해명해!

0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜
493 [과학] 자바로 프로그래밍에 입문할래요: 1.5. 입출력 (1) 1 스비니 1 3 일 전
492 [과학] 자바로 프로그래밍에 입문할래요: 1.4. 배열 (3) 1 스비니 4 12 일 전
491 [과학] 일론 머스크는 스티브 잡스 같은 사람이다. (feat. 뉴럴링크) 38 빨머 20 13 일 전
490 [과학] 자바로 프로그래밍에 입문할래요: 1.4. 배열 (2) 9 스비니 2 19 일 전
489 [과학] 방사선에 관하여_20210423_Ch.4까지 완료 63 ptrtype01 4 20 일 전
488 [과학] 日 자민당 의원이 공개한 원전오염수 성분 31 SOLEUS 16 22 일 전
487 [과학] ??? : 한국이 오염수 더 많이 방류한다 빼애액 24 SOLEUS 13 22 일 전
486 [과학] 일본의 방사능 기준치가 신용받지 못하는 이유 71 뭘까요 1 23 일 전
485 [과학] 도쿄의 암 발생률. 27 뭘까요 5 23 일 전
484 [과학] 일본은 과연 후쿠시마 인근만 방사능에 오염돼었을까? 13 뭘까요 10 23 일 전
483 [과학] 일본이 주장하는 후쿠시마의 방사능량은 서울과 같다는게 사... 31 뭘까요 14 24 일 전
482 [과학] 일본 후쿠시마 오염수 방류 팩트정리 21 뭘까요 7 24 일 전
481 [과학] 자바로 프로그래밍에 입문할래요: 1.4. 배열 (1) 13 스비니 7 27 일 전
480 [과학] 약사가 쓴 az백신과 혈전에 관한 글 109 pipo 40 2021.04.08
479 [과학] 자바로 프로그래밍에 입문할래요: 1.3. 조건문과 반복문 (2) 21 스비니 4 2021.04.06
478 [과학] 사회과학계에서 밝혀졌던 "보이루"의 실체 13 안티파굳 23 2021.04.05
477 [과학] 피임약은 어떻게 임신을 예방할까? 33 동식 18 2021.04.01
476 [과학] 자바로 프로그래밍에 입문할래요: 1.3. 조건문과 반복문 (1) 11 스비니 2 2021.03.27
475 [과학] 급성 방사선 장해의 치료 역사, 그리고 방법은 무엇일까? 20 바른말고운말하는사람 7 2021.03.24
474 [과학] 자바로 프로그래밍에 입문할래요: 1.2. 내장 자료형 (2) 23 스비니 5 2021.03.23