[자료구조&알고리즘] 기본 자료구조(배열, 클래스)

기본 자료구조

• data structure
• 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계
• 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
• 데이터 단위: 데이터를 구성하는 한 덩어리

---

배열

• 배열의 자료형 구분
  각 요소의 자료형 = int, a[0]은 int형
  자료형 = int[5], a는 int[5]형
• int a = new int[5]; 선언하면 배열 a는 a[0], a[1], a[2], a[3], a[4]로 총 5개의 int형 저장 공간을 차지함
• 배열의 구성 요소는 자동으로 0으로 초기화됨

그림 추가

배열의 복제

배열의 이름.clone();

package chap02_1;

import java.util.Arrays;

public class CloneArray {

	public static void main(String[] args) {
		int[] a = {1, 2, 3, 4, 5};
		int[] b = a.clone(); //b는 a의 복제를 참조
		
		b[3] = 0;
		
		System.out.println("a = " + Arrays.toString(a)); //a = [1, 2, 3, 4, 5]
		System.out.println("b = " + Arrays.toString(b)); //b = [1, 2, 3, 0, 5]
	}
}

그림 추가

배열 요소의 최댓값

package chap02_1;

import java.util.Scanner;

public class MaxOfArray {

	static int maxOf(int[] a) { //배열 a의 최댓값을 구하여 반환
		int max = a[0]; //맨 처음 max값을 배열의 첫번째 값
		
		for(int i = 1; i < a.length; i++) {	//배열의 길이만큼 반복	
			if(a[i] > max) { //현재 max값보가 a[i] 인덱스의 값이 더 클 때
				max = a[i]; //max값에 a[i] 값 넣기
			}
		}
		return max;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.println("키의 최댓값을 구함");
		System.out.print("사람 수: ");
		int num = scan.nextInt(); //배열의 요솟수를 입력 받음 = 배열의 길이
		
		int[] heigth = new int[num]; //길이가 num인 int형 배열 height 생성
		
		for(int i = 0; i < num; i++) { //배열의 값 넣어줘야 하므로 배열만큼 반복
			System.out.print("height[" + i + "] = ");
			heigth[i] = scan.nextInt(); //배열[인덱스값]에 scan.nextInt();로 값 넣어주기
		}
		
		//반복이 끝나면
		System.out.println("최댓값은 " + maxOf(heigth) + "입니다."); //maxOf() 메서드 안에 height 배열 넣어서 최댓값 반환		
	}
}

머쓱이보다 키 큰 사람

https://school.programmers.co.kr/learn/courses/30/lessons/120585

프로그래머스

3항 연산자 사용하자!!!!!!!!

        for(int i: array){
            answer += (i>height) ? 1 : 0;
        }

배열 요소를 역순으로 정렬

그림 추가---

요소 개수가 n인 배열 요소를 역순으로 정렬하는 알고리즘

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

• 교환 횟수는 n/2로 중앙 전까지만 교환하면 됨
  요소 개수가 홀수 - 가운데 요소 교환할 필요 x

배열 안의 두 값 교환

그림 추가---

배열 안의 두 요소를 교환하는 알고리즘

//배열 요소 a[idx1]과 a[idx2]의 값을 교환
static void swap(int []a, int idx1, int idx2) {
	int t = a[idx1];
    a[idx1] = a[idx2];
    a[idx2] = t;
}

• 설명 설명

두 배열의 비교

package chap02_1;

import java.util.Scanner;

public class ArrayEqual {

	static boolean equal(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; //두 조건이 다 true이면 결과적으로 같은 배열임
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.print("a 배열의 요솟수: ");
		int num1 = scan.nextInt();
		int[] a = new int[num1];
		
		for(int i = 0; i < num1; i++) {
			System.out.print("a[" + i + "] = ");
			a[i] = scan.nextInt();
		}
		
		System.out.print("b 배열의 요솟수: ");
		int num2 = scan.nextInt();
		int[] b = new int[num2];
		
		for(int i = 0; i < num2; i++) {
			System.out.print("b[" + i + "] = ");
			b[i] = scan.nextInt();
		}
		
		//3항 연산자 사용
		System.out.println("배열 a와 b는 " + (equal(a, b)? "같습니다." : "같지 않습니다"));
		
	}
}

배열의 모든 요소를 복사

package chap02_1;

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

public class Quiz4 {

	static void copy(int[] a, int[] b) {
		if(a.length != b.length) System.out.println("두 배열의 길이가 같지 않습니다.");
		for(int i = 0; i < a.length; i++) {
			a[i] = b[i];
		}
	}
	
	// 배열 b의 모든 요소를 배열 a에 복사 ▶ 여기서는 길이가 같은지는 중요하지 않음
	//static void copy(int[] a, int[] b) {
	//	int num = a.length <= b.length ? a.length : b.length; //a길이가 작으면 a만큼만, b가 작으면 b만큼만
	//	for (int i = 0; i < num; i++)
	//		a[i] = b[i];
	//}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.print("a의 요솟수는 ：");
		int num1 = scan.nextInt();
		int[] a = new int[num1];
		for (int i = 0; i < num1; i++) {
			System.out.print("a[" + i + "] : ");
			a[i] = scan.nextInt();
		}

		System.out.print("b의 요솟수는 ：");
		int num2 = scan.nextInt();
		int[] b = new int[num2];
		for (int i = 0; i < num2; i++) {
			System.out.print("b[" + i + "] : ");
			b[i] = scan.nextInt();
		}
		
		copy(a, b);
		
		System.out.println("a배열 = " + Arrays.toString(a));
		System.out.println("b배열 = " + Arrays.toString(b));
	}
	
}

역순해서 복사

// 역순 복사
	a[i] = b[b.length - i - 1];

배열 역순 할때는 배열길이 - i -1 사용

static void rcopy(int[] a, int[] b) {	
	int num = a.length <= b.length ? a.length : b.length ;
	for(int i = 0; i < num; i++) {
		a[i] = b[b.length-i-1]; //역순해서 복사
	}
}

---

기수 변환

소수의 나열

 

---

소수

• 자신과 1 이외의 정수로 나누어떨어지지 않는 정수
• 2부터 n-1까지의 어떤 소수로도 나누어떨어지지 않음

n보다 작은 소수로 나눗셈 했을 경우 n-1까지 나누어떨어지는 수가 없으면 소수 (계산 시간을 줄일 수 있음)

↔ 합성수: 나누어떨어지는 정수가 하나 이상 존재하는 수

소수의 나열

package chap02_1;

public class PrimeNumber1 {

	//1000이하의 소수를 열거
	public static void main(String[] args) {
		int counter = 0; //나눗셈의 횟수
		
		for(int i = 2; i <= 1000; i++) {
			int j;
			for(j = 2; j < i; j++) {
				counter++; //나눗셈을 할 때마다 count를 증가해 연산 횟수 계산
				if(i % j == 0) { //나누어 떨어지면 소수x
					break;
				}
			}
			if(i == j) { //마지막까지 나누어 떨어지지 않음
				System.out.println(i);
			}
		}
		System.out.println("시행한 횟수: " + counter);
	}
}

알고리즘 개선(1)

• 배열 prime에는 그 때까지 구한 소수를 넣음
• ptr은 배열에 저장한 소수의 개수를 나타내는 변수
  prime[0] = 2 저장한 후 바로 다음의 ptr 값은 1
• 3 이상의 소수는 이중 for문으로 구함
  안쪽의 for문은 i 값을 1부터 시작하여 ptr-1회 반복

package chap02_1;

//1000이하의 소수를 구하라
public class PrimeNumber2 {
	public static void main(String[] args) {
		int counter = 0; //나눗셈의 횟수
		int ptr = 0; //찾은 소수의 개수, 소수 2가 저장되고 다음은 1이 나옴
		int[] prime = new int[500]; //길이가 500인 소수를 저장하는 배열
		
		prime[ptr++] = 2; //prime[0] = 2 저장, 2는 소수, 여기서 ptr = 1
		
		for(int n = 3; n <= 1000; n += 2) { //2는 소수이고, 3부터 1000까지 홀수(+2씩)만 확인
			int i;
			for(i = 1; i < ptr; i++) { //처음의 i < ptr이 1 < 1이므로 for문을 반복 수행x
				counter++; //나눗셈 횟수를 세고,
				if(n % prime[i] == 0) { //나누어 떨어지면 멈춤(소수x)
					break;
				}
			}
			if(ptr == i) { //처음의 ptr == i는 1==1이므로 prime[1] = 3을 넣음
				prime[ptr++] = n;
			}
		}
		
		for(int i = 0; i < ptr; i++) {
			System.out.println(prime[i]); //찾은 ptr개의 소수를 나타냄
		}
		
		System.out.println("나눗셈을 수행한 횟수: " + counter);
		
	}
	
}

알고리즘 개선(2)

알고리즘 개선(3)

다차원 배열

int[ ][ ] x = new int [2][4];
//2행 4열

한 해의 경과 일 수를 계산하는 프로그램

• 그 해의 경과 일 수는 1월, 2월, 3월, ..., m-1월의 일 수의 합 + d
• 단, 2월의 평년은 28일, 윤년은 29일이므로 다차원 배열로 [0] = 평년, [1] = 윤년으로 잡아줘야 함
        1년을 366일로 잡아도 정확하지 않으므로 평년 = 100으로 나눠지고, 400으로 나눠지지 않는 해 (윤년은 거꾸로)

	//각 달의 일수
	static int[][] mdays = {
			{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, //평년 i=[0]
			{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, //윤년 i=[1]
	};

	//서기 year년은 윤년인가? (윤년 = 1, 평년 = 0)
	static int isLeap(int year) {
		return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1 : 0;
		//4년에 한번은 윤년 &&  !(year%100 == 0 && year%400 != 0) 이 조건이 아닐 때 윤년
	}
	
	//서기 y년 m월 d일의 그 해 경과 일 수 구하는 메서드
	static int dayOfYear(int y, int m, int d) {
		int days = d; //일 수 먼저 넣고
		
		for(int i = 1; i < m; i++) { //1월 ~ (m-1)월의 일 수를 더하기 ********i는 1부터 시작해야 [0]부터 나옴
			days += mdays[isLeap(y)][i-1]; //isLeap로 평년이면 0, 윤년이면 1을 넣어서 행 구해주고, 열은 m-1이니까 i-1해서 일수 days에 넣기
		}
		return days;
	}

• y년 i월의 일 수 = mdays[isLeap[y][i-1]
• 각 달의 일수를 다차원 배열로 나타내고, isLeap 메서드를 사용하여 28일인지 29일인지 선택
• dayOfYear로 일 수 구하기

//while문 사용하여 메서드 구현
	static int dayOfYear(int y, int m, int d) {
		while(--m != 0) { //--m; + m != 0; m에서 하나뺀 값이 0이 아닐때까지 반복, ex) 2월, 1월
			d += mdays[isLeap(y)][m-1];
		}
		return d;
	}

• 변수 days와 for문을 사용하지 않고, while문 이용

	//그 해 남은 일 수 구하기
    static int leftDayOfYear(int y, int m, int d) {
		while(--m != 0) {
			d += mdays[isLeap(y)][m-1];
		} //그 년에서 지난 일 수 구해서
		int result = 365 - d; //365일에서 빼기
		return result;
	}

while문에서 자주 쓰이는 조건식

--m != 0 ▶ --m; + m != 0;
m을 하나씩 줄이고, 그게 0이 아닌 경우

m-- > 0 ▶ m--; + m > 0; 
m을 줄이는데(루프가 돌고 1을 줄임) 0보다 큰 경우

다차원 배열의 복제

• clone은 최상위의 1레벨만 수행 = 그 아래 레벨의 배열은 복제되지 않고 공유

향상된 for문

• 인덱스 자체의 값이 필요하지 않으면 그 스캔은 향상된 for문에 의해 구현

for(int i : arr) {
    관련 수식
}                       ▶ 배열 arr안에 있는 int i, 배열이 int형임

---

Math.random() vs new Random

• 컴퓨터에서 진짜 랜덤 값은 없고, 수식에 의해 생성된 수식의 결과물을 랜덤값으로 사용
• seed * (수식) 으로 seed(컴퓨터의 현재 시간)에 의해 랜덤값이 변함

Math.random()	new Random
import java.lang.Math	import java.util.Random; Random ran = new Random();
0.0 ~ 1.0 사이의 임의의 double형 난수	boolean, int, long, float, double형 난수
seed(현재시간) 가 고정	seed() 임의로 설정 가능
	ran.setSeed(System.currentTimeMillis()); ran.setSeed(10); //동일 seed를 가지면 동일한 랜덤값 생성

• 실무적으로 Random 클래스를 더 많이 사용
• 암호화를 위한 난수 생성에는 rsa, sha256, sha512 등을 사용하여 복호화 어렵게 만듦

난수를 사용한 배열의 요솟값 설정 & 최댓값 --- 수정

package chap02_1;

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

public class MaxOfArrayRand {

	//max값 구하는 메서드
	static int maxOf(int[] a) {
		int max = a[0];
		for(int i = 1; i < a.length; i++) { //a[0]은 이미 max에 들어가있으니까 1부터
			if(max < a[i]) max = a[i];
		}
		return max;
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
//		int ran = ((int)Math.random() * 90 ) + 1;
		Random ran = new Random(); //Random 클래스형의 변수(ran) 선언 
		
		System.out.println("키의 최댓값을 구합니다.");
		System.out.print("사람 수: ");
		int num = scan.nextInt();
		
		int[] heigth = new int[num];
		
		System.out.println("키 값을 아해와 같습니다.");
		for(int i = 0; i < num; i++) {
			heigth[i] = 100 + ran.nextInt(90); //0 <= nextInt(n) < n 이므로 0~89까지의 난수 생성
			System.out.println("heigth[" + i + "] = " + heigth[i]);
		}
		
		System.out.println("최댓값은 " + maxOf(heigth) + "입니다.");
	}
}

1. Random 클래스를 사용하기 위해 import 선언
2. Random 클래스형의 변수(ran)를 만들기 위한 선언
3. 변수 ran에 대한 난수를 생성하는 메서드 nextInt 호출

---

클래스

• 임의의 데이터형을 자유로이 조합하여 만들 수 있는 자료구조
• 여러 형의 요소를 조합하여 만든 자료구조

클래스의 배열

평균 키와 시력의 분포

package chap02_1;

import java.util.Scanner;

//신체검사 데이터용 클래스 배열에서 평균 키와 시력의 분포를 구함
public class PhysicalExamination {

	static final int VMAX = 21; // 시력분포(0.0에서 0.1 단위로 21개)

	static class PhyscData { // 필드 = 멤버변수
		String name; // 이름
		int height; // 키
		double vision; // 시력
		
		//생성자
		//ctrl+shift+s
		public PhyscData(String name, int height, double vision) {
			super();
			this.name = name;
			this.height = height;
			this.vision = vision;
		}
	}
	
	//키의 평균값을 구함
	static double aveHeight(PhyscData[] dat) { //데이터가 들어가 있는 배열
		double sum = 0;
		
		for(int i = 0; i < dat.length; i++) {
			sum += dat[i].height;
		}
		return sum / dat.length;
	}
	
	//시력 분포를 구함
	static void distVision(PhyscData[] dat,
								int[] dist) { //무슨 배열인가..
		int i = 0;
		
		dist[i] = 0;
		for(i = 0; i < dat.length; i++) {
			if(dat[i].vision >= 0.0 && dat[i].vision < VMAX / 10.0)
				dist[(int)(dat[i].vision * 10)]++;
		}
	}
	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		PhyscData[] x = {
				new PhyscData("박현규", 162, 0.3),
				new PhyscData("함진아", 173, 0.7),
				new PhyscData("최윤미", 175, 2.0),
				new PhyscData("홍연의", 171, 1.5),
				new PhyscData("이수진", 168, 0.4),
				new PhyscData("김영준", 174, 1.2),
				new PhyscData("박용규", 169, 0.8),
		};
		
		int[] vdist = new int[VMAX]; //시력분포
		
		System.out.println("■ 신체검사 리스트 ■");
		System.out.println("이름     키   시력");
		System.out.println("---------------");
		
		for(int i = 0; i < x.length; i++) {
			System.out.printf("%-8s%3d%5.1f\n", x[i].name, x[i].height, x[i].vision); //개인 키, 시력
		}
		System.out.printf("\n평균 키: %5.1fcm\n", aveHeight(x)); //메서드 사용
		
		distVision(x, vdist); //시력분포를 구함
		
		System.out.println("\n시력 분포");
		for(int i = 0; i < VMAX; i++) {
			System.out.printf("%3.1f~%2d명\n", i / 10.0, vdist[i]);
		}
	}
	
}

시력 분포
0.0~ 0명
0.1~ 0명
0.2~ 0명
0.3~ 1명
0.4~ 1명

System.out.println("\n시력 분포");
		for(int i = 0; i < VMAX; i++) {
			System.out.printf("%3.1f~:", i / 10.0, vdist[i]); //0.1~2.0까지 써져있는 앞부분

			for (int j = 0; j < vdist[i]; j++) //한 사람씩 반복하면서 *표시
				System.out.print('*');
			System.out.println(); //반복하나 끝나면 아래로 내리기 (이전의 \n과 같음)
		}

시력 분포
0.0~:
0.1~:
0.2~:
0.3~:*
0.4~:*

Quiz 11

클래스 보충

• 본체에는 멤버(필드/메서드/중첩 클래스/중첩 인터페이스), 클래스초기화/인스턴스초기화, 생성자 선언 가능
• 필드/메서드/생성자 선언시 public/protected/private 지정 가능
• 메서드/생성자는 다중으로 정의(오버로드) 가능 = 형식은 다르고, 같은 이름
• final로 선언한 필두는 한 번만 값 대입 가능
• 생성자는 새로 생성한 인스턴스의 초기화를 위해 사용됨

2022.10.05 - [프로그래밍 언어/Java] - [Java] object(객체), class(클래스), 변수(멤버/지역), 생성자(constructor)

[Java] object(객체), class(클래스), 변수(멤버/지역), 생성자(constructor)