과학

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

이번 글은 좀 짧긴 한데, 2절과 3절을 하나로 합치자니 또 너무 길어져서.. 적당히 타협했어.

이번 절의 내용은 대부분 배열을 활용하는 방법에 대한 이야기들이야.

 

1.4 배열 (1)

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

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

1.2. 내장 자료형 (2)

1.2. 내장 자료형 (1)

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

 

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

 

 사전 계산(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로 만듭니다. 다음 그림을 참고해보세요.

 

 

 

 

 

(계속)

9개의 댓글

2021.04.23

프로그래밍 / 자바를 진짜 1도 모르는 진짜..요즘 초등학생들보다 모르는 상황인데 시작할려면 어찌 해야하나요?....프로그래밍에 대해서 진짜 1도 모릅니다;; 컴퓨터 언어?라는 것만 알고있어요 ㅠㅠ

0
2021.04.24
@그리즐리

이 글에 내용이 처음 프로그래밍 언어를 접하는 사람이 보기에는 너무 장황하고, 눈에 안 들어 올 수 있어요

시작하지 않으면 시간이 흐르고 그때 해볼걸 미련이라도 남겠지만,

입문서 하나 사서 조금씩 해보면 잘 할 수 있을것같아요, 아직 대학교 진학?을 안하셨으면 관련학과 가시는게 젤 좋구요!

-현직 자바 개발자-

0
2021.04.24
@눈내리는마을

입문서 추천좀 해주실 수 잇나요 ㅎㅎ

0
2021.04.24
@그리즐리

쉽게 배우는 자바 프로그래밍 - 한빛미디어 /우종정 지음

 

입문자가 보기에 거부감 없이 그림으로 아기자기하게 설명잘해줘서 추천드리구

 

위의 책 두 세번 정독하셨으면

 

자바의정석 이라는 책으로 기초를 더 튼튼하게 다져보세요

 

그리고 책만 보면 이론에만, 책에만 집중하게되서 실제로 뭐 해보려고하면 잘 안되니까

 

이론 + 실습 꼭 병행하세용

0
2021.04.24
@그리즐리

지금 학원 다니면서 배우는중인데 독학 보다는 학원 댕기면서 선생한테 배우는게 좀 쉽게 배워짐

0
2021.04.24
@재뇨

제가 시골에샇아서 ㅠㅠ 그런 학원이없네요 ㅠㅠ

0
2021.04.24
@그리즐리

그럼 진짜진짜 윤성우의 열혈 C부터 시작하면서 하세요

여러 논란이 있긴 한데, 입문서로서 그것만한 것도 드뭄

0
2021.04.24

자바말고 파이썬해도되지..?

0
2021.04.25
@Quant

언어는 표현해내는 수단일뿐이라서 어떤 언어라도 상관 없어요.

파이썬이나 자바스크립트 추천

0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜
11208 [기타 지식] 홍콩의 정해진 미래와 홍콩을 바라보는 중국에 관하여 50 골방철학가 35 20 시간 전
11207 [과학] SF스압) 최후의질문 / 원래는..(How It Happened) 8 기타치는고라니 11 23 시간 전
11206 [호러 괴담] [reddit 괴담] 다음 희생자를 몇 달이나 보던 연쇄살인마가 ... 2 다시살기 6 23 시간 전
11205 [호러 괴담] [살인자 이야기] 약혼녀를 버리고 첫눈에 반한 여성과 결혼한... 4 그그그그 4 1 일 전
11204 [과학] [양자역학 3부] 슈뢰딩거의 고양이에 대해서. 24 기타치는고라니 2 1 일 전
11203 [기타 지식] 조선족의 민족의식 39 김여름방학식충 19 2 일 전
11202 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (2) 2 스비니 3 2 일 전
11201 [기묘한 이야기] 공동 생활 규칙 10 트루워치프 8 3 일 전
11200 [호러 괴담] [살인자 이야기] 1964년 미국 미시시피주에서 일어난 믿지 못... 7 그그그그 5 3 일 전
11199 [기타 지식] 게임중독 질병 등재 논란 1편 : 등재 반대측의 잘못된 주장과... 9 년째야스못함 6 4 일 전
11198 [기타 지식] X도 아닌 국제기구 - OECD에 대한 오해에 관하여 12 골방철학가 15 4 일 전
11197 [기타 지식] [약스압/사진有] 취미 카린이가 주절대는 사진 이야기 - 인물... 45 인문학적변태 13 5 일 전
11196 [호러 괴담] [살인자 이야기] 사람들은 그를 "다이너마이트의 악마&q... 10 그그그그 7 5 일 전
11195 [기타 지식] 표준 도시 경제 모델: 도시계획에 대한 새로운 생각 - 07 3 미분가능하지않은... 2 6 일 전
11194 [과학] (기상)우리나라 더위의 발생 형태 4가지. 51 마리괭이 20 6 일 전
11193 [호러 괴담] [살인자 이야기] (스압) 후쿠오카 일가족 살인사건의 전말 4 그그그그 9 7 일 전
11192 [기타 지식] [앨범] 최엘비 - CC 4 NYLON 1 7 일 전
11191 [기타 지식] 취미 카린이가 주절대는 카메라 이야기 - 센서이야기 2편 34 인문학적변태 5 8 일 전
11190 [호러 괴담] [살인자 이야기] 월곡동 황금장 여관 모녀 살인사건 10 그그그그 9 9 일 전
11189 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (1) 4 스비니 1 9 일 전