[Java알고리즘] Ch2-1. 배열

1. 배열

1-1. 자료구조 (data structure)

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

1-2. 배열

변수를 매번 생성하여 자료를 저장하게 되면, 자료의 수가 증가함에 따라 변수명 등 신경써야 하는 부분이 늘어난다. 따라서 배열을 만들고 '몇 번째'라고 지정해 자료를 좀 더 효율적으로 이용할 수 있도록 한다.

• 배열은 같은 자료형의 변수로 이루어진 구성요소(component)가 모인 것이다. 자료형은 int형이나 double형이나 어떤 형이든 상관없다.
• 배열 선언하기

int[] a; // 형식 A
int a[]; // 형식 B

• 구성요소의 자료형이 int형이고, 구성요소의 개수가 5개인 배열 선언하기

a = new int[5];

• 첫 번째 배열 요소의 인덱스는 0으로 정해져 있다.
  구성요소에 접근하기 위해서 a[0],a[1]... 이런식으로 사용한다.
  즉, 표현식 a[i]는 배열 a에서 처음부터 i개 뒤의 구성요소로 접근하는 것을 뜻한다.

배열 변수 이름[인덱스]

• 구성요소의 개수 : length (=배열의 길이)

배열 변수 이름.length

⬆️배열의 구성요소는 자동으로 0으로 초기화되는 규칙이 있다.
이 부분은 변수와 다른점!!! 값을 대입하지 않은 변수 (초기화하지 않은 변수)는 값을 꺼낼 수 없다.

• 배열의 복제

 배열 이름.clone()

1-3. 배열의 MAX와 MIN구하기

1. 키가 가장 큰 사람의 키를 구하는 프로그램을 만들어보기 (MAX)

maxOf(height)부분은 상단에 미리 만들어 둔 maxOf 메소드를 호출하여 최대값을 구하는 부분이다.

❗️접근 제한자

• public : 모든 접근 허용
• protected : 같은 패키지(폴더)의 객체, 상속 관계의 객체 허용
• default : 같은 패키지(폴더)의 객체 허용
• private : 현재의 객체 안에서만 허용

2. 키가 가장 작은 사람의 키를 구하는 프로그램을 만들어보기 (MIN)

1-4. 난수를 사용해 배열의 요솟값 설정하기

배열의 요소에 값을 직접 입력하는 것이 귀찮다면, '난수'를 이용해 본다.

1-4-1. 난수

❗️ '난수' :
java.util 패키지에 속한 Random클래스는 Java가 제공하는 아주 큰 클래스 라이브러리다.
Random 클래스의 인스턴스는 일련의 의사 난수를 생성한다.
난수는 'seed' 라는 수의 값을 바탕으로 여러 연산을 수행하여 얻는다.
Random 클래스에서는 48비트의 seed를 사용하고, 이 seed는 선형 합동법이라는 계산법에 의해 특정수(난수)로 바뀐다.

 //1. 난수 생성
 Random rand = new Random(); // A형식
 Random rand = new Random(n); // B형식
 // 2. 난수생성 받아오기
 int num = rand.nextInt();
 //3. nextInt(n)가 반환하는 것은 0부터 n-1까지의 난수이다.
 int num = rand.nextInt(90);
 -> 생성한 난수를 90으로 나눈 나머지(0~89)값으로 받는다.

2. 역순으로 정렬하기

2-1. 값 바꾸기 기초

• 교환 횟수 : 요소개수/2

 for(i = 0; i < n/2 ; i++)

• 교환을 위해서 작업용 변수를 하나 더 만들자!

int a=1 ;  int b =2; //가 있다면
int t; // 를 만들어서 b와 a의 값을 교환한다.
t = a // 1. t에 a 값을 넣고
a = b // 2. a에 b 값을 넣고
b = t // 3. b에는 t에 들어있던 a값을 넣는다. 

2-2. 배열에 값을 받아 역순으로 정렬하는 프로그램 만들기

배열 요소를 역순으로 정렬하는 알고리즘.
예를들어 {1,2,3,4,5} 배열이 있다면, {5,4,3,2,1}로 바꾸기
2-1에서 확인했던 기초부분을 가지고 응용해보면 만들 수 있을 것 같다.

2-3. 배열을 역순으로 정렬하는 과정을 보여주는 프로그램 만들기

배열 요소를 역순으로 정렬하는 과정을 하나하나 나타내는 프로그램

2-4. 배열의 모든 요소의 합계를 구하는 프로그램

3. 증가 연산자

• 전위형 증가 연산자 : ++a
  ++를 앞에 놓으면 식 전체를 평가하기 전에 피 연산자의 값을 증가시킨다.
  그러므로 a의 값이 3일 때 b = ++a를 실행하면 a와 b는 4가 된다.
• 후위형 증가 연산자 : a++
  ++를 뒤에 놓으면 식전체를 평가한 후에 값을 증가시킨다.
  그러므로 a의 값이 3일 때 b = a++ 를 실행하면 a가 3일때 b에 먼저 값을 넣고 실행 후에 a가 4로 올라간다. 즉, a는 4 b는 3이 된다.

4. 다차원 배열

4-1. 다차원 배열?

'표'와 같은 이미지로 '행'과 '열'이 늘어선다.
다차원 배열 가운데 가장 간단한 것이 2차원 배열이다.

int[][] x = new int[2][4];

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

2차원 배열을 활용하여 어떤 날짜의 '그 해 경과 일 수'를 구한다.
4월 15일을 예로 들어 그 해의 경과 일 수를 구한다.

1월의 일 수 + 2월의 일 수 + 3월의 일 수 + 15일

위와 같은 원리를 이용하여
m월 d일의 그 해 경과 일 수는

1월,2월,...,m-1월의 일 수의 합+d

2월의 일 수는 윤년과 평년에 따라 달라지기 때문에, 2차원 배열을 이용한다.

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}  //윤년
}

❗️1년은 365일이라고 하지만,
지구가 태양을 한바퀴 도는 일 수는 정확히 365일이 아니기 때문에, 
이를 조정하기 위해서 4로 나누어 떨어지는 해를 윤년으로 1년을 366일을 만든다.
또한, 100으로 나누어 떨어지고 400으로 나누어 떨어지지 않는 해는 평년으로 한다.

5. 확장 for문 (향상된 for문)

for(double i : a)
    sum += i;

• 확장 for문:
  'for-in문' 또는 'for-each문' 이라고도 부른다.
• 배열 a의 처음부터 끝까지 모든요소를 한 개씩 스캔한다. 루프 본문에서는 현재 주목하고 있는 요소를 i라고 표현한다.
• 확장 for문은 배열의 요소수의 길이를 알아야 하는 번거로움을 줄여준다.

배열은 내가 가장 어려워하는 부분 중 하나이다.
때문에, 이번 연습으로 끝이 아니라 매일매일 새로운 예제를 접해보는 식으로 진행하고 싶다.
오늘은 기본적인 배열의 개념을 이용한 알고리즘을 연습했지만,
언젠가는 배열을 자유롭게 활용한 알고리즘을 척척 짜낼 수 있겠지? :)