자료구조
◽ 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계
◽ 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
배열
int[] a; // 선언
a = new int[5]; // 생성
◽ 배열을 생성하고 초기화를 하지 않을 경우, 자동으로 0으로 초기화된다.
배열의 복제
int[] a = {1, 2, 3, 4, 5};
int[] b = a.clone(); // 복제
배열의 최댓값
class MainClass {
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;
}
}
난수의 생성
Random rand = new Random();
Random rand = new Random(n);
◽ 코드에서 난수를 사용할 때는 실제 난수가 아닌 의사 난수를 사용하여 처음 실행했을 때의 난수와 동일한 난수를 가져오게 된다. 따라서, 현재 시간 값을 srand 메서드에 매개변수로 전달해서 매번 다른 의사 난수를 생성하는 것이 일반적이다.
역순으로 배열 정렬하기
class MainClass {
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1];
a[idx1] = a[idx2];
a[idx2] = t;
}
static void reverse(int[] a) {
for (int i = 0; i < a.length / 2; i++) {
swap(a, i, a.length - i - 1);
}
}
}
두 배열의 요소 비교
class MainClass {
static boolean equals(int[] a, int[] b) {
if (a.length != b.length)
return false;
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i])
return false;
return true;
}
}
기수 변환
class MainClass {
int no; // 변환하는 정수
int cd; // 기수
int dno; // 변환 후의 자릿수
char[] cno = new char[32]; // 변환 후 자리의 숫자를 넣어두는 문자의 배열
public static int cardConvR(int x, int r, char[] d) {
int digits = 0;
String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
do {
d[digits++] = dchar.charAt(x % r); // r로 나눈 나머지를 저장
x /= r;
} while (x != 0);
return digits;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
no = stdIn.nextInt(); // 변환할 음이 아닌 정수 입력
cd = stdIn.nextInt(); // 변환할 기수 입력
dno = cardConvR(no, cd, cno); // no를 cd진수로 변환한 자릿수 반환
for (int i = dno - 1; i >= 0; i--) {
System.out.print(cno[i]); // 역으로 되어있는 문자 배열을 거꾸로 출력
}
}
String 클래스
String s = "ABC";
char charAt(int i) // 인덱스가 i인 곳의 문자를 가져온다.
int length() // 문자열의 문자 수를 가져온다.
boolean equals(String s) // 문자열 s와 같은지 조사한다.
소수의 나열
✔️ 2부터 1000까지의 정수 중에서 소수를 나열하고, 이를 구하는데 필요한 연산 횟수를 출력하는 프로그램을 작성하시오.
하급 알고리즘
◽ 아이디어 : 어떤 정수 n에 대하여 2부터 n - 1까지의 어떤 정수로도 나누어 떨어지지 않는다.
class MainClass {
public static void main(String[] args) {
int counter = 0; // 나눗셈의 횟수
for (int n = 2; n <= 1000; n++) {
int i;
for (i = 2; i < n; i++) {
counter++;
if (n % i == 0) // 나누어 떨어지면 소수가 아님
break; // 더 이상의 반복은 불필요
}
if (n == i) // 마지막까지 나누어 떨어지지 않음
System.out.println(n);
}
System.out.println("나눗셈을 수행한 횟수 : " + counter);
}
}
중급 알고리즘
◽ 아이디어 : 어떤 정수 n에 대하여 2부터 n - 1까지의 어떤 소수로도 나누어 떨어지지 않는다.
class MainClass {
public static void main(String[] args) {
int counter = 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++) { // 이미 찾은 소수로 나누어 봄
counter++;
if (n % prime[i] == 0) // 나누어 떨어지면 소수가 아님
break; // 더 이상의 반복은 불필요
}
if (ptr == i)
prime[ptr++] = n;
}
for (int i = 0; i < ptr; i++) // 찾은 ptr개의 소수를 나타냄
System.out.println(prime[i]);
System.out.println("나눗셈을 수행한 횟수 : " + counter);
}
}
고급 알고리즘
◽ 아이디어 : n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.
class MainClass {
public static void main(String[] args) {
int counter = 0; // 곱셈과 나눗셈의 횟수
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2; // 2는 소수
prime[ptr++] = 3; // 3은 소수
for (int n = 5; n <= 1000; n += 2) { // 대상은 홀수만
boolean falg = 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);
}
}
다차원 배열
📋 한 해의 경과 일 수를 계산하는 프로그램
class MainClass {
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) {
return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
}
static int dayOfYear(int y, int m, int d) {
int days = d; // 일 수
for (int i = 1; i < m; i++) // 1월 ~ (m - 1)월의 일 수를 더함
days += mdays[isLeap(y)][i - 1];
return days;
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("년 : "); int year = stdIn.nextInt(); // 년
System.out.print("월 : "); int month = stdIn.nextInt(); // 월
System.out.print("일 : "); int day = stdIn.nextInt(); // 일
System.out.printf("그 해 %d일째입니다\n", dayOfYear(year, month, day));
}
}
확장 for 문
class MainClass {
public static void main(String[] args) {
double[] a = { 1.0, 2.0, 3.0, 4.0, 5.0 };
double sum = 0;
for (double i : a)
sum += i;
System.out.println("모든 요소의 합은 " + sum + "입니다.");
}
}
◽ 배열의 모든 요소를 스캔하는 과정에서 인덱스 자체의 값이 필요하지 않으면 확장 for문으로 구현하는 것이 좋다.
'Data Structure' 카테고리의 다른 글
배열로 집합 만들기 (0) | 2021.12.13 |
---|---|
재귀 알고리즘 (0) | 2021.11.30 |
큐 (0) | 2021.11.29 |
스택 (0) | 2021.11.28 |
검색 (0) | 2021.11.24 |