고정 헤더 영역
상세 컨텐츠
본문
- 배열 선언
배열 선언은 다음과 같이 가능하다. ex) int[] a ;
예시를 보면 맨 처음 자료형과 []를 적고 배열 변수를 적어주면 된다. 여기서 int[] a = new int[n] ; 과 같이 new 연산자로 본체를 생성하지 않는 이상 a는 그냥 배열 변수일뿐 배열 그 자체가 아니다.
배열을 생성하면서 선언할 수 있는 두가지 방법이 있다.
1. int[] a = new int[n]; > 배열의 크기가 n인 integer형 배열
2. int[] a = { 1, 2, 3 }; > 배열이 integer형이고 1과 2 그리고 3으로 이루어진 크기가 3인 배열
1번은 new 연산자로 배열의 크기만 정해서 생성하는 방법이고, 2번은 배열 생성과 동시에 초기화까지 하는 방법이다.
- 배열의 요솟수(길이)
배열 변수 이름.length를 통해 배열의 요솟수를 구할 수 있고 배열의 길이라고도 부른다.
- 자료형의 기본값
배열을 생성하면 배열의 구성요소는 자료형의 기본값으로 자동 초기화 된다. 각 자료형의 기본값은 다음과 같다.
- 값을 대입하지 않은 지역 변수
배열의 구성요소와 클래스의 필드(멤버 변수)는 자동으로 기본값으로 초기화가 된다. 그러나 메서드 안에서 선언한 지역변수는 기본값으로 초기화되지 않는다. 따라서 초기화나 대입을 통해 값을 받지 못한 지역변수에서는 값을 꺼낼 수 없다.
예를 들면 int a ; System.out.println( " a값은 " + a + "입니다."); 의 경우 a가 지역변수면 선언만 했을 뿐 초기화를 안했기 때문에 컴파일 오류가 발생한다.
- 의사 난수와 선형 합동법
자바에서는 Random 클래스를 이용해 난수를 생성할 수 있다. 우리는 이 난수를 규칙없이 무작위로 생성한다 생각할 수 있는데 컴퓨터에서 생성된 모든 난수는 미리 컴퓨터가 계산해 둔 '의사 난수' 이다. 의사 난수는 규칙없는 무작위 난수처럼 보이지만 일정한 규칙에 의해 생성된다. 여기서 난수를 의사 난수라고 부르는 건 다음에 생성할 난수를 예측할 수 있기 때문이다. Random에서 생성하는 의사 난수는 '선형 합동법'으로 생성이 가능하다. 간단하게 보면 선형 합동법은 현재 의사 난숫값을 A배 하고 C를 더한 다음, M으로 나눈 나머지를 의사 난수로 선택하는 방법이다.
- 배열을 역순으로 정렬하는 알고리즘
간단하게 말하면 크기가 n인 배열이 있을때 배열의 양 끝의 요소를 서로 바꿔준다. 그 다음 방금 건드린 요소들을 제외한 나머지 값들의 양 끝의 요소를 서로 바꿔준다. 이렇게 하는 것을 중앙값까지 반복하면 된다.
코드를 보면 다음과 같다.
public class Main {
public static void main(String[] args) {
int a[] = {1, 2 ,3 ,4 ,5};
int n = a.length;
for( int i = 0; i < n/2 ; i++){
int t = a[i] ;
a[i] = a[n-i-1] ;
a[n-i-1]=t;
}
for(int i=0; i<a.length;i++)
System.out.println(a[i]);
}
}결과 값을 보면 5 4 3 2 1 이 출력되며 배열이 역순으로 정렬된 것을 알 수 있다.
- 배열의 전체 요소 표시
배열의 전체 요소를 표현하고 싶을때 Arrays.toString(배열 변수 이름)을 이용하면 된다.
만약 int[] a = {1, 2, 3, 4} ; 라면 Arrays.toString(a)를 통해 문자열 "[1, 2, 3, 4]"를 return 할 수 있다.
따라서 System.out.println(Arrays.toString(a)); 를 하면 문자열 "[1, 2, 3, 4]"이 출력된다.
- 배열에 관한 세부 규칙
1. 빈 배열 : 배열의 크기는 0이어도 된다. 이런 배열을 빈 배열이라고 부른다
int[] a = new int[0] ; 가능
2. 배열 복제(클론) : 배열을 복제할때 int[] a = {1, 2, 3, 4, 5}; int[] b = a ; 이렇게 하면 배열 b는 배열 a의 주소를 복사해 가는 것이지 배열 요소들을 복사해 가는 것이 아니므로 a와 b 둘 중 어느 하나라도 수정하면 a, b 둘 다 수정이된다. 이러한 일을 막기 위해서 int[] b = a.clone(); 을 사용하면 배열 b는 배열 a의 요소들을 복사해가기 때문에 독립적인 배열이 될 수 있다.
- 기수 변환 알고리즘
기수란 집합 구성요소의 개수를 나타내는 수이다. n진수는 n을 기수로하는 수이다. 그 이유는 n진수를 표현할 때 사용하는 숫자가 0~n-1까지 n개이기 때문이다. 따라서 기수를 변환하는 것은 진법을 변환하여 수를 표현하는 것이다. 기수를 변환하는 법은 10진수에서 r진수로 바꾸는 법과 r진수에서 10진수로 바꾸는 법을 알아볼 것이다.
1. 10진수에서 r진수로 변환하기
10진수를 r진수로 변환하려면 10진수 정수를 r로 나눈 몫과 나머지를 구하고 나머지를 배열에 저장한다. 그리고 몫을 다시 x에 대입해 x가 0이 될때까지 위의 과정을 반복해야 한다. 반복이 끝나면 배열을 역순으로 나열하고 순서대로 출력하면 r진수 변환이 완료된다. 이를 코드를 보면서 이해해보자.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int r = sc.nextInt();
char[] d = new char[32];
String dchar = "0123456789ABCDEF";
int digits = 0;
// x를 r로 나누면서 나온 나머지값 d배열에 대입 나눈 몫은 x에 다시 대입하고 x가 0이 될때 까지 반복
do{
d[digits++]= dchar.charAt(x%r);
x = x / r;
} while(x!=0);
//배열을 역순으로 만든후 출력
for( int i=0; i<digits/2;i++){
char t = d[i];
d[i] = d[digits-i-1];
d[digits-i-1] = t;
}
for(int i=0; i<digits;i++){
System.out.print(d[i]);
}
System.out.println();
}
}
2. r진수를 10진수로 변환하기
이는 앞의 예제보다 쉽다. 예시로 보면 더 쉬운데 16진수 정수 0xA25D가 있으면 다음과 같이 10진수 정수로 변환할 수 있다.
0xA25D = (16^3)*10 + (16^2)*2 + (16^1)*5 + (16^0)*13 = 41565가 된다. (A=10, D=13)
10진수값 = r진수 정수의 첫째자리값*r^(0) + 둘째자리값*r^(1) + 셋째자리값*r^(2) ... n번째자리값*r^(n-1) 이 된다.
- 소수 나열하는 알고리즘
소수란 자신과 1 이외의 어떤 정수로도 나누어떨어지지 않는 정수이다. 그러므로 어떤 정수 n이 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않으면 소수라고 하고, 나누어떨어지면 합성수라 한다.
이를 이용해 소수를 구하는 알고리즘을 만들 수 있는데 3가지 단계별 방법이 있다. 2~1000사이의 소수를 구하는 예시를 통해 알아보자.
1. 정의 그대로 구하는 방법
정의 그대로 i를 2~i-1로 나눈 후 나누어떨어지지 않으면 소수로 판단하고 이를 i = 2부터 1000까지 해보는 방법이다.
public class Main {
public static void main(String[] args) {
int count=0;
for(int i=2; i<=1000; i++){
boolean ok = true;
for(int j=2;j<i;j++){
count++;
if(i%j==0){ ok = false; break;}
}
if(ok) System.out.println(i);
}
System.out.println(count);
}
}다음과 같이 이중for문을 이용해 구할 수 있다. 내부 for문은 i%j==0이면(i가 j로 나누어떨어지면) ok = false로 바꾸고 for문을 탈출한다(소수가 아니라고 판단). 반면 반복을 끝까지 진행하고 for문이 끝나면 if 조건인 ok = true이므로 (소수가 맞다고 판단) i값을 출력한다. 코드 중간에 count라는 int값이 있고 이는 나눗셈을 할때마다 1씩 증가하여 알고리즘이 진행되는 동안의 나눗셈을 한 횟수를 구할 수 있는데 1번 방법은 총 78022번의 나눗셈을 통해 소수를 전부 찾아냈다.
2. j의 범위를 줄여 구하는 방법
1번의 방법을 이용하되 j의 범위를 크게 줄이는 방법이다. j의 범위를 줄이는 이유는 뭘까? 예를들어 12의 약수를 확인해 보자. 12 = 1*12, 2*6, 3*4, 4*3, 6*2, 12*1 인데 약수를 늘여놓으면 1,2 ,3 ,4 ,6,12 이다. 잘보면 특이한 것이 보이는데
12의 제곱근인 √12 (= 3.46..) 보다 큰 약수들은 전부 √12 보다 작은 약수들과 곱해져있다. 따라서 n이 소수인지 확인할 때 2~ n-1까지가 아닌 2~√n 까지만 확인해도 된다.( √n 보다 큰 약수가 있는 정수의 경우 이미 √n이하의 약수에서 나누어 떨어져 소수가 아님이 확인되기 때문이다.) 그래서 이를 이용해서 코드를 수정하면 다음과 같다.
public class Main {
public static void main(String[] args) {
int count=0;
for(int i=2; i<=1000; i++){
boolean ok = true;
for(int j=2;j*j<=i;j++){
count++;
if(i%j==0){ ok = false; break;}
}
if(ok) System.out.println(i);
}
System.out.println(count);
}
}1번과 같은방법으로 큰 차이 없어 보이지만 count의 값이 5288로 크게 줄었다. 단지 j값의 범위를 조정했을 뿐인데 효율이 크게 늘었다.
3. 에라토스테네스의 체
마지막 방법은 에라토스테네스의 체라고 불리는 방법이다.
1) 2부터 1000까지 모든 수를 써놓는다.
2) 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3) 그 수는 소수이다.
4) 이제 그 수의 배수를 모두 지운다. 다시 2)부터 반복한다.
이는 소수의 배수는 소수를 약수로하는 합성수임을 이용해 효율을 극대화 한 방법이다. 2~1000까지의 수 중 지워지지 않은 가장 작은 수는 2니까 2는 소수이고 2의 배수는 전부 지운다. 따라서 짝수가 사라진다. 다음 지워지지 않은 수는 3이므로 3은 소수이다. 그리고 3의 배수를 전부 지운다. 4는 지워졌고 5가 지워지지 않았으므로 5의 배수를 지운다. 이런 방법을 계속 반복하면 되는데 이때 배수를 지우는 경우 n*2부터 n*3, n*4, n*5 ... 전부 지우는 것이 아니라 n*n부터 n*n+1, n*n+2, n*n+3 ... 이렇게 n*n부터 시작하여 지우면 된다. 그 이유는 n보다 작은 수의 배수는 다 지워졌기 때문에 굳이 했던 일을 반복할 필요가 없기 때문이다.(ex: n*2 : 2의 배수로 지워짐, n*3 : 3의 배수로 지워짐, n*4 : 4가 2의 배수이므로 2의배수로 지워짐 ....) 이제 배수를 지우는 법도 알아봤고 배수를 지우는 일을 언제까지 해야될지 생각해보자. 2부터 시작해서 지워지지 않은 가장 작은 수 n을 찾아 반복하다보면 n*n>1000이되는 경우가 생긴다. 이때 알고리즘이 끝난다. 따라서 n= 31일때 까지만 판단하면 알고리즘이 끝난다. ( 32부터는 32*32가 1000보다 크므로 지워도 의미가 없다. 따라서 지금까지 안지워진 1000보다 작은 값들은 더이상 지워질 일이 없고 소수로 확정이 된다.) 코드를 통해 구현한 것을 보자.
public class Main {
public static void main(String[] args) {
int count = 0;
boolean[] check = new boolean[1001]; // 소수 = false, 합성수 = true
int n = 1000;
for( int i=2; i*i<n;i++){
if(check[i]) continue; // 합성수인 경우 패스
for(int j=i*i;j<=1000;j=j+i) {
check[j] = true; // 소수의 배수인 경우 true
count++; // 배수인지 판단하는 경우 count++
}
}
for(int i=2;i<=1000;i++) {
if(!check[i])
System.out.println(i);
}
System.out.println(count);
}
}다음과 같이 boolean배열을 이용해 false면 소수, 합성수면 true라는 기준을 만들었다. for문 i의 범위를 2 ~ √n으로 만들었고 i가 소수인지, 소수의 배수(합성수)인지 if 절을 통해 판단한다. 소수인경우 그 수의 배수들을 true로 바꾸면서 판단시마다 count 를 증가시킨다. 이렇게 에라토스테네스의 체를 이용하면 count가 1411로 가장 효율적인 방법임을 알 수 있다.
- 나머지 연산
나머지 연산은 다음과 같은 식이 성립한다.
(A+B) % M = ((A%M)+(B%M))%M
(A*B) % M = ((A%M)*(B%M))%M
그러나 뺄셈의 경우에는 %연산 결과가 음수가 될 수 있기 때문에 덧셈, 곱셈과 달리 M을 한번 더 더해준다..
(A-B) % M = ((A%M)-(B%M)+M)%M
- 최대공약수, 최소공배수
두 수 A와 B가 있을 때
최대공약수(GCD) : A와 B의 공통된 약수 중에서 가장 큰 정수
최소공배수(LCM) : A와 B 두 수의 공통된 배수 중에서 가장 작은 정수
1. 최대공약수를 구하는법 : 유클리드 호제법
A와 B의 최대공약수를 구할 때 유클리드 호제법을 쓰면 간단하다. A를 B로 나눈 나머지를 R이라 했을 때 A와 B의 최대공약수를 나타내는 GCD(A,B)와 B와 R의 최대공약수를 나타내는 GCD(B,R)가 같다. 즉 GCD(A,B) = GCD(B,R) 이다.
이 과정을 반복해서 GCD(A,B) = GCD(B,R) = GCD(B',R')......= GCD(b,0) 두 수중 0이 나오면 이때 b가 최대공약수이다.
ex) GCD(24,16) = GCD(16,8) = GCD(8,0) >> 따라서 24와 16의 최대공약수는 8이다.
만약 세 수의 최대공약수를 구해야하면 GCD(A,B,C) = GCD(GCD(A,B),C)와 같다.
2. 최소공배수를 구하는 방법 : GCD 이용하기
GCD를 구하면 LCM은 구하기가 쉽다. GCD*LCM = A*B 이므로 LCM = A*B/GCD가 된다.
'자료구조와 알고리즘 > 자료구조, 알고리즘' 카테고리의 다른 글
| 제너릭스와 Comparable, Comparator (0) | 2023.01.09 |
|---|---|
| Java import선언과 Java.lang 패키지 + 클래스 메서드와 인스턴스 메서드 (0) | 2023.01.09 |
| 배열 검색 알고리즘 (선형 검색, 이진 검색) (0) | 2023.01.09 |
| 기본 자료구조 (클래스) (0) | 2023.01.06 |
| 드모르간 법칙 (0) | 2023.01.05 |
