2. 기본 자료구조
int[] a; // 선언하기
a = new int[5]; // 참조하기
값을 대입하지 않은 지역변수
배열의 구성요소와 클래스의 필드는 값을 대입하지 않으면 초기값으로 초기화 된다. 하지만 method 안의 지역변수는 초기화가 되지 않는다. 따라서 초기화를 해줘야 한다.
배열의 복제 clone
배열 이름.clone()
배열 요소의 최댓값 구하기
max = a[0];
for(i = 1; i < n; i ++ ){
if(a[i] > max) max = a[i];
}
이처럼 배열의 요소를 하나식 차례로 살펴보는 과정을 알고리즘 용어로 스캔이라고 한다.
접근제한자
- public : 모든 접근 허용
- protected: 같은 패키지의 객체, 상속 관계의 객체 허용
- default : 같은 패키지의 객체 허용
- private : 현재의 객체 안에서만 허용
-
난수 생성
- import 선언
- random 클래스형의 변수를 만들기 위한 선언
- rand에 대한 난수를 생성하는 nextInt호출
-
배열 안의 두 요소를 교환하는 함수
static void swap(int[] a, int idx1, int idx2){
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
형 import 선언
클래스나 인터페이스 등의 형은 반드시 어떤 패키지에 소속되어있다.
ex) import java.util.Scanner;
기수변환 프로그램
static int cardConvR(int x, int r, char [ ]d)
{
int digit = 0;
String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
do{
d[digits++] = dchar.charAt(x%r); // r로 나눈 나머지를 저장
x /= r;
} while ( x != 0);
return digits;
}
->변환후의 d 값은 역순으로 저장이 되므로 꺼낼 때 역순으로 꺼내줘야 한다.
for (int i = r-1; i>=0; i--)
System.out.print(r[i]);
String 클래스
String s = "ABC";
문자열 리터럴은 단순히 문자가 늘어서 있는 것이 아니라 String 형 인스턴스에 대한 참조이다.
String 클래스는 문자열을 넣어두기 위한 문자 배열, 문자 수를 나타내는 필드 등을 갖고 있는 클래스이다.
아래 세가지 메서드는 꼭 기억하자.
- char charAt(int i) // 인덱스가 i인 곳의 문자를 가져온다
- int length() // 문자열의 문자 수를 가져온다
- boolean equals(String s) // 문자열 s와 같은가를 조사한다.
소수의 나열
2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다
for (int n = 2; n <= 1000; n++){
int i ;
for(i=2; i<n; i++){
if(n%i == 0)
break;
}
if( n == i )
System.out.println(n);
}
알고리즘 개선방안(1)
정수 n이 소수인지의 여부는 아래 조건을 만족하면 된다.
2부터 n-1까지의 어떤 소수로도 나누어 떨어지지 않는다.
public static void main(String[] args){
int counter = 0; // 나눗셈의 횟수
int ptr = 0 ; // 찾은 소수
int [ ] prime = new int[500];
prinme[ptr++] = 2; //2는 소수
for (int n =3; n<= 1000; n += 2){ // 대상은 홀수만
int i ;
for(i = 1; i < ptr; i++){ // 이미 찾은 소수로 나누어봄
counter++;
if( n % prime[i] == 0 ) / 나누어떨어지면 소수가 아님
break;
}
if ( ptr == i) // 마지막까지 나누어떨어지지 않음
prime[ptr++] = n; //소수라고 배열에 저장
}
for(int i = 0; i < ptr; i++)
System.out.println(prime[i]);
}
알고리즘 개선 (2)
100의 약수를 가지고 그래프를 그려보면, 정사각형이 되는 10x10을 기준으로 대칭을 이룬다는 걸 알 수 있다. 즉 정사각형 한 변의 길이까지만 소수로 나눗셈을 시도하고, 그 과정에서 한번도 나누어 떨어지지만 않으면 소수라고 판단해도 좋다.
넓이가 100이라는 것은 직사각형의 어느 한 변으로 나눌 수 있다는 의미이다. 이러한 성질을 이용하여 제곱근을 한 변으로 하는 이후의 직사각형에 대한 계산량을 줄이는 것이 이 알고리즘 개선(2)의 핵심이다.
즉 prime[i]의 제곱이 n 이하인가? 이 떄 n이 제곱근을 구하는 것이 제곱을 구하는 것보다 훨씬 간단하고 바르다. 이제까지의 프로그램에서는 나눗셈의 횟수를 세었다. 그러나 곱셈의 처리 비용은 나눗셈과 같으므로 이 프로그램에서는 counter에 곱셈과 나눗셈 횟수의 합계를 저장한다.
package chap02;
// 1,000 이하의 소수를 열거(버전 3)
class PrimeNumber3 {
public static void main(String[] args) {
int counter = 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++) {
counter += 2;
if (n % prime[i] == 0) { // 나누어떨어지면 소수가 아님
flag = true;
break; // 더 이상의 반복은 불필요
}
}
if (!flag) { // 마지막까지 나누어떨어지지 않음
prime[ptr++] = n; // 소수라고 배열에 저장
counter++;
}
}
for (int i = 0; i < ptr; i++) // 찾은 ptr개의 소수를 출력
System.out.println(prime[i]);
System.out.println("곱셈과 나눗셈을 수행한 횟수：" + counter);
}
}
counter +=2;를 해주는 이유는 곱셈(prime[i]*prime[i])과 나눗셈(n%prime[i]), 두 연산의 수행 횟수를 계산하기 위해서다.
flag가 true가 될 때, prime[i]*prime[i]의 횟수는 이미 포함되므로, flag가 false일 때에 (n이 소수인 경우) 만 counter를 증가시킨다.
다차원 배열
엄밀하게 말하면 java는 다차원 배열이 없다.
int [][] x = new int[2][4];
“int형을 구성 자료형으로 하는 배열”을 구성 자료형으로 하는 배열
위와 같이 선언하면 실제로 들어오는ㄱ너
본체를 참조하는 배열 변수 x
x[0][0] | x[0][1] | x[0][2] | x[0][3]
x[1][0] | x[1][1] | x[1][2] | x[1][3]
-> 추후 계속
참고자료
Do it! 자료구조와 함께 배우는 알고리즘 입문