[자료구조-02] 배열의 활용

1. 배열(Array)

- 가장 기본적이고 간단한 자료구조

- 같은 자료형의 변수로 이루어진 구성 요소(component)가 모인 것

 

 

배열 

ju-zero.tistory.com/22?category=900872

[Java-05] 배열(Array) - 1차원 배열

 

- Java를 공부하면서 배열의 개념에 대해서 익혔기 때문에, 배열을 다루는 여러 방법을 공부해보려고 한다.

 

2. 배열의 복제(클론)

 

배열이름.clone()

 

int[] a = {1, 2, 3, 4, 5};		// 1,2,3,4,5
int[] b = a.clone();			// 1,2,3,4,5

 

 

3. 배열 요소의 최댓값, 최솟값 구하기

 

최댓값 구하기

(1) 첫 번째 요소의 값을 max 변수에 대입하기
(2) 반복문과 if를 사용하여 배열의 모든 요소를 비교
(3) max와 비교하였을 때 해당 요소의 값이 max보다 크면 max에 해당 요소의 값 대입하기

 

int[] a = {1, 2, 3, 4, 5};
max = a[0];
for(int i = 1; i < a.length; i++)
	if(a[i] > max)
    	max = a[i];

 

 

최솟값 구하기

(1) 첫 번째 요소의 값을 min 변수에 대입하기
(2) 반복문과 if를 사용하여 배열의 모든 요소를 비교
(3) min와 비교하였을 때 해당 요소의 값이 min보다 작으면 min에 해당 요소의 값 대입하기

 

int[] a = {1, 2, 3, 4, 5};
min = a[0];
for(int i = 1; i < a.length; i++)
	if(a[i] < max)
    	min = a[i];

 

 

4. 난수를 사용해 배열의 요솟값 설정하기

 

java.util 패키지의 Random 클래스를 사용

(1) Random 클래스를 import함
(2) Random 클래스 변수를 선언
(3) 난수를 생성하는 메서드 nextInt() 호출

nextInt() : 정수 범위의 난수를 반환
nextInt(n) : 0 부터 n-1까지의 난수를 반환
nextBoolean(), nextLong(), nextDouble(), nextFloat()도 존

 

import java.util.Random;

...


Random rand = new Random();

int[] a = new int[5];
for(int i = 0; i < 5; i++)
	a[i] = rand.nextInt(90);	// 0 ~ 89 범위의 난수 저장
    

 

 

5. 배열 요소를 역순으로 정렬하기

 

(1) 맨 앞의 요소와 맨 뒤의 요소의 값을 교환
(2) 각각 하나씩 안쪽의 요솟값을 교환
(3) 총 교환 횟수는 '요소 개수 / 2' -> 요소 개수가 홀수여도 가운데 요소는 교환할 필요가 없기 때문

 

int[] a = {12, 4, 29, 99, -4, 127};

int t = 0;
for(int i = 0; i < a.length / 2; i++) {
    t = a[i];					// 임시변수 t에 앞의 값 저장
    a[i] = a[a.length-i-1];		// 앞의 값에 뒤의 값 저장
    a[a.length-i-1] = t;		// 뒤의 값에 임시변수 t의 값 저장
}

 

6. 두 배열의 비교

 

(1) 두 배열의 요솟수(길이)를 비교, 같지 않으면 false 반환
(2) for문으로 두 배열을 처음부터 스캔하면서 a[i]와 b[i]의 값을 비교, 다른 요소가 있으면 false 반환
(3) for문이 중단되지 않고 끝까지 실행되면 true를 반환

 

int[] a = {1, 2, 3, 4, 5};
int[] b = {1, 2, 3, 4, 5};

if(a.length != b.length)
    return false;
    
for(int i = 0; i < a.length; i++)
    if(a[i] != b[i])
        return false;
        
return true;

 

7. 기수 변환

 

진법

ju-zero.tistory.com/16?category=900872

[Java-02] 변수(Variable) - 진법

 

정수값 x를 r진수로 변환하기

(1) x%r 을 인덱스로 하는 문자(dchar.charAt() 사용)를 배열 d의 요소 d[digits]에 대입하고 digits 값을 증가시킴
(2) x를 r로 나눔
(3) x가 0이 될 때까지 반복
(4) x가 0이 됐을 때 digits는 자릿수, d는 변환한 후의 값이 역순으로 저장된 배열이 됨

 

static int cardConvR(int x, int r, char[] d) {
    int digits = 0;		// 변환 후의 자릿수
    String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    
    do {
    	d[digits++] = dchar.charAt(x % r);
        x /= r;
    } while(x != 0);
    
    return digits;
}

public static void main(String[] args) {
    int x = 59;
    int r = 16;
    int digits = 0;
    char[] d = new char[32];
    
    digits = cardConvR(x, r, d);
    
    for(int i = digits - 1; i >= 0; i--)
    	System.out.print(d[i]);
}

 

8. 소수의 나열

 

1) 기본 알고리즘

 

소수 : 2부터 n - 1까지의 어떤 정수로도 나누어떨어지지 않는 수

예를 들어, 2부터 1000까지 숫자 중 소수를 나열하려면
(1) for문을 사용하여 2부터 1000까지 다음을 반복
(2) 이중 for문을 삽입하여 바깥 for문의 숫자(i)가 안쪽 for문의 숫자(j)로 나누어 떨어지면 break하여 탈출
(3) 마지막까지 나누어떨어지지 않으면 소수이므로 출력

 

for(int i = 2; i <= 1000; i++) {
    int j;
    for(j = 2; j < i; j++) {
    	if(i % j == 0)
        	break;
    }
    if (i == j)
    	System.out.println(i);
}

 

 

2) 알고리즘 개선(1)

 

소수 : n보다 작은 소수들로 나누어떨어지지 않는 수
예를 들어, 7이 소수인지는 7보다 작은 소수 2, 3, 5로 나눗셈하면 충분함

(1) 앞서 구한 소수를 저장하는 배열 prime 선언
(2) 2는 소수이므로 prime[0]에 저장
(3) 4 이상의 짝수는 2로 나누어떨어지므로 배제하고, 3 이상의 홀수로만 검사
(4) 3 이상의 홀수 중 이미 찾은 소수로 나누어 떨어지면 소수가 아니므로 break하여 탈출
(5) 마지막까지 나누어떨어지지 않으면 소수이므로 prime에 저장

 

int ptr = 0;				// 찾은 소수의 개수
int[] prime = new int[500];		// 찾은 소수를 저장할 배열

prime[ptr++] = 2;		// 2는 소수

for(int i = 3; i <= 1000; i += 2) {	// 대상은 홀수만
    int j;
    for(j = 1; j < ptr; j++)
    	if(i % prime[j] == 0)
        	break;
    if(ptr == j)
    	prime[ptr++] = i;
}

for(int i = 0; i < ptr; i++)
	System.out.println(prime[i]);
	

 

 

3) 알고리즘 개선(2)

 

소수 : n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는 수

(1) 알고리즘 개선(1)과 동일하게 진행함
(2) prime의 배열 요소 중 prime[i]의 제곱이 n 이하인 요소만 나누어봄
(3) 마지막까지 나누어떨어지지 않으면 소수이므로 prime에 저장

 

int ptr = 0;				// 찾은 소수의 개수
int[] prime = new int[500];		// 찾은 소수를 저장할 배열

prime[ptr++] = 2;		// 2는 소수
prime[ptr++] = 3;		// 3은 소수

for(int i = 5; i <= 1000; i += 2) {	// 대상은 홀수만
    boolean f = false;
    for(int j = 1; prime[j] * prime[j] <= i; j++) {
    	if(i % prime[j] == 0) {
        	f = true;
        	break;
        }
    }
    if(!f)
    	prime[ptr++] = i;
}

for(int i = 0; i < ptr; i++)
	System.out.println(prime[i]);
	

 

9. 다차원 배열

- 2차원 배열(배열을 구성 요소로 함), 3차원 배열(2차원 배열을 구성 요소로 함) 등을 나타내는 말

 

String, 2차원 배열

ju-zero.tistory.com/24?category=900872

[Java-05] 배열(Array) - String 배열, 2차원 배열

 

10. 한 해의 경과 일 수를 계산하기

 

m월 d일의 그 해 경과 일수
1월, 2월, ... , m - 1월의 일 수의 합 + d

평년과 윤년의 차이
평년 : {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
윤년 : {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}

(1) 평년인지 윤년인지 확인
(2) 2차원 배열을 생성하여 평년일수 배열과 윤년일수 배열을 생성
(3) 1월~(m-1)월의 일 수를 더함
(4) d를 더함

 

static int[][] mdays = {
    {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},	// 평년
    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}	// 윤년
}

static int isLeap(int year) {
    // 0이면 평년, 1이면 윤년
    return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
}

static void main(String[] args) {
    int y = 2021;
    int m = 4;
    int d = 15;
    
    int total = d;
    for(int i = 1; i < m; i++) {
    	// 0이면 평년, 1이면 윤년
    	total += mdays[isLeap(y)][i-1];
    }
}

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)