[알고리즘] 2장-2) 배열 이어서

⚛ 2장-1 을 이어서 작성한 포스팅

🛠 배열 요소의 최대값 구하기

public class Main{
	public static void main(String[] args) {
		int[] a = {3, 4 ,2};
		int max; 
		max = a[0];
		if(max<a[1]) max = a[1];
		if(max<a[2]) max = a[2];
		
		System.out.println(max);
		
		int[] b = {10,9,8,12};
		max = b[0];
		if(b[1]>max) max = b[1];
		if(b[2]>max) max = b[2];
		if(b[3]>max) max = b[3];
		
		System.out.println(max);
		
	}
}

a 배열에는 3개의 요소이 있고, b배열에는 4개의 요소가 있다. 배열에서 최대값을 구하기 위해서 배열의 모든 요소들과 전부 비교를 해보는 것이다.
만일 배열에 n개의 요소가 있다면 if문은 총 n-1번 등장한다. (첫번째 배열요소는 max에 대입을 하므로)

//배열 a의 요소 개수가 n개일 경우
int max = a[0];
for(int i =1; i<a.length; a++){
	if(a[i]>max) max=a[i];
}

이렇게 배열의 요소를 하나씩 차례로 살펴보는 과정을 알고리즘 용어로 주사(traverse)라 한다.
술먹고 부리는게 아니라 달릴 주, 조사할 사 란다. 한자는 잘 모르므로 pass;

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

사실 온라인저지사이트(e.g. BOJ)를 이용하여 문제를 제출할땐 상관이 없는 내용이다.
하지만 내 컴퓨터의 IDE를 이용하여 작성하고 테스트를 할때 일일히 테스트값들을 지정해주기가 번거롭다면 난수를 이용해보자.

일단 난수는 말 그대로 Random Number, 즉 무작위로 생성된 수이다. 하지만 컴퓨터는 그저 전기먹는 깡통에 불과하므로 진짜 난수를 발생시킬 수 없다. seed(씨앗)이라 불리는 숫자를 입력받아 일련의 연산과정을 거쳐 숫자를 내놓는다. 이는 언뜻보기에 무작위로 숫자를 내놓는것같아도 컴퓨터가 미리 계산해놓은 숫자를 우리에게 보여주는것 뿐이다. 즉 난수를 따라한 의사난수이다.
만약 같은 seed로 계속 난수를 가져오면 아마 같은 결과가 보일것이다.
이 seed를 계속 바꿔주기 위해 보통 현재시간을 가장 많이 사용한다. 현재시간은 매순간 계속 바뀌기 때문이다.

자바에서 난수를 사용하기 위해서는 random 클래스를 사용한다. java.util 패키지에 속해있으므로 import 해주면 된다. random 클래스의 주요 메서드들은
nextBoolean(), nextInt(), nextInt(n), nextLong(), nextDouble(),nextFloat()등이 있다. nextInt()메서드는 오버로딩이 되어있는데 매개변수가 없으면 int형의 범위인
대략 -21억~+21억까지 숫자중 하나를 반환한다. 정수를 매개변수로 받으면 0~n-1까지 숫자 하나를 리턴해준다.

🛠 배열의 요소를 역순으로 정렬하기

예를 들어 요소의 개수가 7인 다음과 같은 배열이 있다고 가정해보자.

1	2	3	4	5	6	7

나는 이것을 아래와 같이 바꾸고 싶다.

7	6	5	4	3	2	1

순서)
1. 맨 첫번째 값인 1과 마지막 값인 7의 위치를 변경한다.
2. 2번째 값인 2와 마지막에서 2번째 값인 6의 위치를 변경한다.
3. 3번째 값인 3과 마지막에서 3번째 값인 5의 위치를 변경한다.

총 3번 위치를 교환해주면 내가 원하는 결과가 나오게 된다.
만약 n개의 요소를 가지는 배열을 역순으로 정렬하기 위해서 필요한 교환횟수는 n/2 가 될것이다.
n이 짝수라면 문젠 없지만 만약 홀수라면? 그래도 상관없다. 정수를 정수로 나눈 값은 내가 특별히 자료형을 지정해주는 cast를 하지 않는다면 결과값은 정수로 나오기 때문. 즉 소수점 이하의 값들은 버려진다.

그리고 각각의 순서에서 두 요소들을 교환할 땐 작업용으로 쓸 임시변수를 하나 만들고 교환한다.

//만약 아래와 같이 코딩을 했다면
int a=1;
int b=2;
a=b; //a값은 2
b=a; // a의 값은 2인데 이것을 그대로 b에 넣으므로 b는 그대로 2.

//다음과 같이 교환한다.
int a = 1;
int b = 2;
int temp;

temp = a;
a = b;
b = temp;

교환횟수가 (배열요소의 개수 / 2) 이라는 것과 두 요소를 교환하는 방법을 같이 사용하여 배열을 역순으로 정렬하는 다음과 같은 코드를 작성했다.

import java.util.Scanner;

public class Main{

	//두 요소를 교환하는 방법, 메서드로 만들어 놓고 사용하는 것이 편리하다.
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	static void reverse(int[] a) {
    	// 교환횟수를 배열의 요소개수인 a.length를 2로 나눈것으로 구함.
		for(int i=0; i<a.length/2; i++) { 
			swap(a, i, a.length-i-1);
		}
		System.out.println("요소를 역순 정렬 완료");
	}
	
	public static void main(String[] args) {
		Scanner ss = new Scanner(System.in);
		
		System.out.println("배열의 요소 개수 입력 : ");
		int num = ss.nextInt();
		
		int[] arr = new int[num];
		
		for(int i=0;i<arr.length;i++) {
			System.out.print("요소 입력 : ");
			arr[i] = ss.nextInt();
		}
		reverse(arr);
		for(int a : arr) {
			System.out.print(a+" ");
		}		
	}
}

🛠 두 배열의 모든 요소의 값이 같은지 판단하는 방법

두 배열이 같은가를 판단하는 것이다. 정확히 말해서 두 배열의 모든 요소가 같은지를 판단!
긴말않고 코드를 보자.

//두 배열의 모든 요소의 값이 같으면 true, 아니라면 false
static boolean equalArray(int[] a, int[] b) {
	if(a.length != b.length) return false; // 길이부터 다르면 볼것도없이 false.
    	
        for( int i=0; i<a.length ; i++) {
        	if(a[i] != b[i]) return false;
        } // 인덱스를 0부터 차례로 1씩 증가시키며 모든 요소들을 비교
        
        return true; //위의 험난한 여정을 뚫고 여기까지 왔다면 같다고 봐야지 ㄹㅇ;
}

🛠 n진수로 변환하기

10진수를 n진수로 변환하는 방법에 대해 나와있다.
10대 학창시절에 우리는 모두 배웠었다.
기본적으로 어떤 십진수 a를 n진수로 변환하는 방법은 a를 n으로 나누고 나누고 나누고 나누는 것이다. 몫이 0이 될때까지 말이다. 그리고 발생하는 나머지를 역순으로 적어주면 끝난다.

자바에서는 내가 어떤 십진수를 2진수, 8진수, 16진수로 바꾸고 싶다면,
Integer 클래스의 toString()메서드를 사용하면 된다.

int a = 17;
Integer.toString(a,16); // a를 16진수로 바꾸고 그 결과를 String형으로 반환.

하지만 배열을 공부하고 있으므로 배열을 이용해 한번 직접 작성을 해보자!

package chap01;
import java.util.Scanner;

public class CardConvRev {
	
	// 십진수 x를 r진법으로 변환하여 배열d에 아랫자리부터 채워넣고 자릿수 반환 
	static int cardCount(int x, int r, char[] d) {
		int digit = 0;
		String dchar = "0123456789ABCDEF";
		
		do {
			d[digit++] = dchar.charAt(x%r);
			x /= r;
		} while(x!=0);
		
		return digit;
	}
	
	public static void main(String[] args) {
		Scanner ss = new Scanner(System.in);
		int no; //변환하는 정수
		int cd; //기수, n진수의 n
		int dno; //변환 후의 자릿수
		int retry; //루프를 다시 돌릴 것인지?
		char[] cno = new char[100]; //n진수로 변환후 각 자리의 숫자를 넣는 배열
		
		System.out.println("10진수를 기수변환 합니다.");
		do {
			do {
				System.out.print("변환할 정수를 입력하세요(음이 아닌 정수) :");
				no = ss.nextInt();
			} while(no<0);
			
			do {
				System.out.print("어떤 진수로 변환할까요?(2진수~16진수) : ");
				cd = ss.nextInt();
			} while(cd<2 || cd>16);
			
			dno = cardCount(no,cd,cno);	
			
			System.out.print(cd + "진수로 변환결과 : ");
			for(int i=dno-1; i>=0; i--) {
				System.out.print(cno[i]);
			}
			System.out.println("입니다.");
			System.out.print("한번더 할까요? 숫자입력(1:예 / 0:아니오) : ");
			retry = ss.nextInt();
		} while(retry==1);
		
		System.out.println("종료합니다.");	
 	}
}