2-1 배열

자료구조 

- 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계 

 

1. 배열 다루기 

 

1) 배열(Array)

 

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

 

ex)

구성 요소의 자료형이 int형이고 구성 요소가 5개인 배열 

int[] a; //구성 요소의 자료형이 int형인 배열 
a = new int[5]; //new를 사용하여 배열 본체를 생성한 뒤 배열 변수 a와 연결

 

- 배열 본체를 생성하고, 본체에 대한 참조를 생성

- 배열 본체를 생성하는 new 식을 배열 변수의 초기자(initializer)로 사용 

int[] a = new int[5];

 

 

2) 인덱스 식과 구성 요소 

 

- 배열 본체 안의 구성요소에 접근(access)하려면 정수형 인덱스를 연산자 [ ]안에 넣은 인덱스 식을 사용 

배열 변수 이름[인덱스] //배열 안의 특정 구성 요소에 접근

 

- 배열 a의 모든 구성 요소는 int형이고, 각각의 요소는 배열이 아니라 단일로 선언한 int형 변수와 성질이 같음 

- 각 요소에 자유롭게 int형의 값을 대입하거나 꺼낼 수 있음 

 

 

3) 배열 길이 

 

배열 변수 이름.length; //배열의 구성 요솟수

 

 

4) 기본 값 

 

- 배열의 구성 요소는 자동으로 0으로 초기화됨 

 

 

5) 배열의 요솟값을 초기화하며 배열 선언

 

- 배열 본체는 new 연산자뿐만 아니라 배열 초기화(array initializer)에서도 생성 가능 

- 배열 초기화를 사용하면 배열 본체의 생성과 동시에 각 구성 요소를 특정값으로 초기화 가능 

public class IntArrayInit {
	public static void main(String[] args) {
		int[] a = {1,2,3,4,5};
	
		for(int i=0; i<a.length; i++)
		{
			System.out.println("a["+i+"]="+a[i]);
		}
	}

}

 

 

2. 배열 요소의 최댓값 구하기 

 

- 첫 번째 요소 a[0]의 값을 max에 대입 

- if문을 실행하는 과정에서 필요에 따라 max값을 새로 대입

- 요솟수가 n이면 if문 실행은 n-1번 필요 

- max와 비교하거나 max에 대입하는 요소의 인덱스는 1씩 증가 

 

- 주사(traverse) 

  -> 배열 요소를 하나씩 차례로 조사하는 과정

 

max=a[0];
for(int i=1; i<n; i++)
	if(a[i]>max) max=a[i];

 

 

 

1) 프로그램 실행 중 배열의 요솟수 결정 

 

- 배열의 요소를 구하는 절차를 별도의 메서드 maxOf()로 구현 

- maxOf()는 인수로 받은 배열 a의 최댓값을 구하고 그 값을 반환 

- 배열의 요솟수 num을 입력받고 요솟수가 num인 배열을 생성

- 배열 요솟수가 프로그램을 컴파일할 때가 아닌 실행할때(runtime) 결정 

 

import java.util.Scanner;

public class MaxOfArray {

	//배열 a의 최댓값을 구하여 반환
	static int maxOf(int[] a) {
		int max = a[0];
		for(int i=1; i<a.length; i++)
			if(a[i]>max)
				max=a[i];
		return max;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println("키의 최댓값을 구합니다.");
		System.out.print("사람 수: ");
		int num = sc.nextInt();
		
		int[] height = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("height["+i+"]");
			height[i] = sc.nextInt();
		}
		
		System.out.println("최댓값은"+maxOf(height)+"입니다.");
	}
}

 

 

 

2) 난수를 사용하여 배열의 요솟값 설정

 

Random 클래스 

 

- import 선언 (import java.util.Random)

- Random 클래스형의 변수를 만들기 위한 선언

- 변수 rand에 대하여 난수를 생성하는 메서드 nextInt를 호출 

- nextInt(n)가 반환하는 것은 0부터 n-1까지의 난수 

import java.util.Random;
import java.util.Scanner;

public class MaxOfArrayRand {
	
	//배열 a의 최댓값을 구하여 반환
	static int maxOf(int[] a) {
		int max = a[0];
		for(int i=1; i<a.length; i++)
			if(a[i]>max)
				max=a[i];
	    return max;
	}
	

	public static void main(String[] args) {
		Random rand = new Random();
		Scanner sc = new Scanner(System.in);
		
		System.out.println("키의 최댓값을 구합니다.");
		System.out.print("사람 수: ");
		int num = sc.nextInt();
		
		int[] height = new int[num]; //요솟수가 num인 배열을 생성 
		
		System.out.println("킷값은 아래와 같습니다.");
		for(int i=0; i<num; i++) {
			height[i] = 100+rand.nextInt(90); //요솟값을 난수로 설정 
			System.out.println("height["+i+"]:"+height[i]);
		}
		
		System.out.println("최댓값은 "+maxOf(height)+"입니다.");
		

	}

}

 

 

3. 배열 요소를 역순으로 정렬

 

- {2,5,1,3,9,6,7}을 {7,6,9,3,1,5,2}로 변경

 

- 교환 횟수는 '요솟수 /2 '이고 나머지는 버림 

- 요솟수가 홀수일 때는 가운데 요소는 교환할 필요가 없음 

 

- 변수 i값을 0,1,...로 증가시키는(increment) 방법을 통해 요솟수가 n인 배열의 처리 과정 

1. 왼쪽 요소의 인덱스 i
2. 오른쪽 요소의 인덱스 n-i-1

 

for(int i=0; i<n; i++)
	//a[i]와 a[n-i-1]의 값을 교환

 

 

1) 두 값의 교환 

 

- 배열을 역순으로 정렬하려면 배열 안의 두 요소를 교환해야 함 

-  작업용 변수를 t를 이용한 교환 과정 

 

1. t=x; x값을 t에 보관 
2. x=y; y값을 x에 대입
3. y=t; t에 보관한 처음 x값을 y 에 대입

 

swap 메서드 

- 배열 a의 요소 a[idx1]값과 a[idx2]값을 교환하는 것 

static void swap(int[] a, int idx1, int idx2) {
    int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

 

 

2) 배열의 전체 요소 표시 

 

- Arrays.toString 메서드를 사용하여 배열의 전체 요솟값 한 번에 표시 

- import java.util.Arrays; 필요 

- Arrays.toString(배열 변수 이름)으로 메서드를 호출하면 모든 요소를 쉼표(,)로 구분하여 [ ]로 둘러싼 문자열을 얻는 구조 

 

import java.util.Arrays;
import java.util.Scanner;

public class ReverseArray {

	//배열 요소 a[idx1]와 a[idx2]의 값을 교환 
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	//배열 a의 요소를 역순으로 정렬 
	static void reverse(int[] a)
	{
		for(int i=0; i<a.length/2; i++)
			swap(a,i,a.length-i-1);
	}
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요솟수: ");
		int num = sc.nextInt();
		
		int[]x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"]:");
			x[i] = sc.nextInt();
		}
		
		reverse(x);
		
		System.out.println("요소를 역순으로 정렬했습니다.");
		System.out.println("x="+Arrays.toString(x));
	}
}

 

 

 

 

4. 기수 변환

 

- 10진수 정수를 n진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 구하고, 그 몫을 n으로 나누는 과정을 반복해야 함 

- 이 과정을 몫이 0이 될 때까지 반복하고, 이런 과정을 통해 구한 나머지를 거꾸로 나열한 숫자가 기수로 변환한 숫자 

 

 

ex) 

- 59를 2진수로 변환 

 

//정숫값 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어두고 자릴수를 반환 
	static int cardConv(int x, int r, char[] d) {
		int digits = 0; //변환후의 자릿 수 
		String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		
		do {
			d[digits++] = dchar.charAt(x%r); //1) r로 나눈 나머지를 저장 
			x/=r; //2
		}while(x!=0); //x가 0이 될때까지 반복 
		
		//배열 d의 숫자 문자열을 역순으로 정렬 
		for(int i=0; i<digits/2; i++) {
			char t = d[i];
			d[i] = d[digits-i-1];
			d[digits-i-1] = t;
		}
		
		return digits;
	}

 

- 메서드 cardConv는 정수 x를 r진수로 변환한 숫자 문자를 char형 배열 d에 넣어 두고 그 자릿수(배열에 넣어 둔 문자수)를 반환 

 

- digits는 변환한 수의 자릿수를 나타내기 위한 변수 

- 아래 작업을 x가 0이 될때까지 반복

1) 먼저 x를 r로 나눈 나머지를 인덱스로 하는 문자를 배열 d의 요소 d[digits]에 대입하고 digits값을 1증가 시킴
2) x를 r로 나눔

 

 

변수명.charAt(인덱스 값)

 

- 문자열에서 문자를 추출

- charAt으로 추출하여 char(문자)로 추출한 문자는 고유의 아스키 코드값을 갖기 때문에 숫자 형태로도 표현이 가능하고, 연산도 가능 

 

전체 프로그램 

import java.util.Scanner;

public class CardConv {

	//정숫값 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어두고 자릴수를 반환 
	static int cardConv(int x, int r, char[] d) {
		int digits = 0; //변환후의 자릿 수 
		String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		
		do {
			d[digits++] = dchar.charAt(x%r); //1) r로 나눈 나머지를 저장 
			x/=r; //2
		}while(x!=0); //x가 0이 될때까지 반복 
		
		//배열 d의 숫자 문자열을 역순으로 정렬 
		for(int i=0; i<digits/2; i++) {
			char t = d[i];
			d[i] = d[digits-i-1];
			d[digits-i-1] = t;
		}
		
		return digits;
	}
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int no; //변환하는 정수 
		int cd; //기수 
		int dno; //변환후의 자릿 수 
		int retry; //다시 한번?
		char[] cno = new char[32]; //변환 후 각 자리의 숫자를 넣어 두는 문자 배열 
		
		System.out.println("10진수를 기수 변환합니다.");
		do {
			do {
				System.out.print("변환하는 음이 아닌 정수: ");
				no = sc.nextInt();
			}while(no<0);
			
			do {
				System.out.print("어떤 진수로 변환할까요?(2~36): ");
				cd=sc.nextInt();
			}while(cd<2 || cd>36);
			
			dno = cardConv(no,cd,cno); //no를 cd 진수로 변환 
			
			System.out.print(cd + "진수로");
			for(int i=0; i<dno; i++) //순서대로 출력
				System.out.print(cno[i]); 
			System.out.println("입니다.");
			
			System.out.print("한번 더 할까요? (1..예/ 0..아니요): ");
			retry=sc.nextInt();
		}while(retry == 1);
	}
}

 

 

5. 소수 나열하기 

 

소수 

 

- 자신과 1 이외의 어떤 정수로도 나누어떨어지지 않는 정수 

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

 

public class PrimeNumber1 {
	public static void main(String[] args)
	{
		int count=0; //나눗셈의 횟수 
		
		for(int n=2; n<=1000; n++)
		{
			int i;
			for(i=2; i<n; i++)
			{
				count++;
				if(n%i==0) //나누어 떨어지면 소수가 아님
					break; //반복은 더 이상 불필요 
				
			}
			if(n==i) //마지막까지 나누어떨어지지 않음 
				System.out.println(n);
		}
		
		System.out.println("나눗셈을 수행한 횟수: "+count);
	}
}

 

 

 

- 바깥쪽 for문에서는 n값을 2부터 시작하여 1,000이 될 때까지 1씩 증가시키면서 그 값이 소수인지를 판단 

- 안쪽 for문의 반복이 종료된 시점에서 변수 i값

n이 소수인 경우: n과 같은 값 (for문이 끝까지 실행됨)
n이 합성수인 경우: n보다 작은 값 (for 문이 중단됨)

 

- n이 2 또는 3으로 나누어 떨어지지 않으면 2*2인 4 또는 2*3인 6으로도 나누어 떨어지지 않음 

- 불필요한 나눗셈을 하고 있음 

 

- 정수 n이 소수인지의 여부는 다음 조건을 만족하는지 조사하면 됨 

 

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

 

 

1) 알고리즘 개선하기 1

 

- 소수를 구하는 과정에서 이때까지 구한 소수를 배열 prime의 요소로 저장 

- n이 소수인지 아닌지 판단하려면 그때까지 저장해 둔 소수로 나눗셈을 진행 

- 3 이상의 소수는 이중 for문으로 구함

- 바깥쪽 for문은 n값을 2씩 증가시켜 3,5,7,9,...로 홀숫값만을 생성

- 안쪽 for문은 i값을 1부터 시작하여 ptr-1회 반복 

 

 

 

public class PrimeNumber2 {
	public static void main(String[] args) {
		int count=0; //나눗셈의 횟수 
		int ptr = 0; //찾은 소수의 개수 
		int[] prime = new int[500];
		
		prime[ptr++] =2; //2는 소수 
		

		for(int n=3; n<=1000; n+=2) {
			int i;
			for(i=1; i<ptr;i++) {
				count++;
				if(n%prime[i] ==0) //나누어 떨어지면 소수 아님
					break;
			}
			if(ptr==i) //마지막 까지 나누어 떨어지지 않음
				prime[ptr++]=n;
		}
		
		for(int i=0; i<ptr; i++)
			System.out.println(prime[i]); //찾은 ptr개의 소수를 출력
		
		System.out.println("나눗셈을 수행한 횟수:"+count);
	}
}

 

 

 

2) 알고리즘 개선하기 2

 

- 100의 약수 (2,4,5,10,20,25,50,100)

 (2x50), (4x25), (5x10). (10x10), (20x5), (25x4), (50x2)

- 정사각형 (10x10)을 중심으로 대칭 

- 10까지만 소수로 나눗셈을 시도하고 그 과정에서 나누어 떨어지지 않으면 소수라고 판단해도 됨

 

- 어떤 정수 n은 다음 조건을 만족하면 소수라고 판단 

 

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

 

Prime[i]의 제곱이 n 이하인가?

 

public class PrimeNumber3 {
	public static void main(String[] args) {
		int count=0; //곱셈과 나눗셈 횟수 
		int ptr = 0; //찾은 소수의 개수 
		int[] prime = new int[500]; //소수를 저장하는 배열
		
		prime[ptr++]=2;
		prime[ptr++]=3;
		
		for(int n=5; n<=1000; n+=2) {
			//조사 대상은 홀수만
			boolean flag = false;
			
			for(int i=1; prime[i]*prime[i] <=n; i++) {
				count+=2;
				if(n%prime[i] == 0) { //나누어 떨어지면 소수가 아님
					flag =true;
					break;
				}
			}
			if(!flag) { //마지막까지 나누어 떨어지지 않음 
				prime[ptr++] =n; //소수로 배열에 저장
				count++;
			}
		}
		
		for(int i=0; i<ptr; i++) //찾은 ptr개의 소수를 출력
			System.out.println(prime[i]);
		
		System.out.println("곱셈과 나눗셈을 수행한 횟수: "+count);
	}
}