JAVA 웹개발 과정 국비 8일차 정리
8일차
※ 배우는 과정이므로 정확하지 않을 수 있습니다.
잘못된 점은 알려주시면 수정하도록 하겠습니다!
1. Array
동일한 타입을 가지는 변수들의 집합.
4개의 데이터를 받을 때에는 변수를 4개 선언해주면 된다.
그러나 100개, 1000개, 10000개의 데이터를 받아야한다면..?
여러개의 변수를 한번에 선언이 가능한 배열을 사용한다.
자바에서는 배열보다 좋은 개념들이 많지만 결국 원리는 모두 배열부터 출발하기 때문에 잘 알아두는 것이 좋다.
사용빈도와 중요성은 낮은 편이다.
1) 배열의 선언
배열을 선언하려면 두개의 문법이 필요하다.
- DataType[] 배열이름;
배열의 주소를 저장하기 위한 참조 변수 생성.
(배열을 선언한 것은 아직 아니다.) - new DataType[배열크기];
실질적인 배열을 Heap메모리에 생성한다.
따라서 아래 배열 선언 예시에서 주소값이 1000이라고 가정할 때,
int[] arr = new int[4];
1. Stack 메모리에 변수 arr를 선언.
2. Heap 메모리에 크기가 4인 배열을 생성.
3. int[4]는 주소값으로 1000을 갖는다.
4. 변수 arr는 주소값 1000을 갖는다.
이렇게 작동 순서를 나타내볼 수 있다.
2) 만든 4칸 중 각각에 공간에 어떻게 접근하는가?
① 각 인덱스에 값을 넣어준다
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
arr[3] = 40;
arr[4] = 50; // 오류! -> ArrayIndexOutOfBoundsException
② 초기화
int[] arr = new int[] {10,20,30,40};
뒤쪽에 중괄호{ }를 이용해 값을 초기화하여 넣어줄 수 있다.
주의할 점은 초기화 시, 사이즈를 대괄호[ ] 안에 넣으면 오류가 난다.
중괄호 안에 숫자를 넣었기 때문에, 컴퓨터가 자동으로 몇개인지 세기 때문에 써줄 필요가 없다.
3) index(첨자)가 0부터 시작하는 이유
index는 offset의 의미를 가지기 때문.
offset : 기준점으로부터 얼마나 떨어졌는가?
따라서 0부터 시작하는 이유는 배열의 맨 처음 index는 값으로 갖는 주소값의 맨 처 음, 즉 동일한 주소이기 때문이다.
ex) arr[2] = 30; -> 1000번지에서 2만큼 떨어진 곳에 30을 넣어라
4) 값을 꺼내올 때
System.out.println(arr[3-1]); // 산술식 가능
int a = 2;
System.out.println(arr[a]); // 변수 가능
결과적으로 대괄호 안에 숫자가 오기만 하면 된다.
5) 배열의 길이
.length
보통 반복문과 함께 쓴다.
public class Quiz_02 {
public static void main(String[] args) {
// int형 배열 100칸짜리 arr1을 만들고, 1부터 100까지 저장한다.
int[] arr1 = new int[100];
for(int i=0;i<arr1.length;i++) { // 100 대신 arr1.length
arr1[i] = i+1;
}
System.out.println(arr1[0]); // 1
System.out.println(arr1[99]); // 100
}
}
2. SWAP
자바에서는 두 값을 바꿀 때 임시 저장 변수를 만들어서 바꿔준다.
그렇지 않으면 두 값이 동일해져서 제대로 값이 바뀌지 않는다.
public class Exam_03 {
public static void main(String[] args) {
int[] arr = new int[] {10, 20};
System.out.println(arr[0] + " : " + arr[1]); // 10 : 20
// SWAP 코드
int tmp = arr[0];
arr[0] = arr[1];
arr[1] = tmp;
System.out.println(arr[0] + " : " + arr[1]); // 20 : 10
}
}
3. Bubble Sort (거품 정렬)
두개의 인접한 원소를 비교하여 정렬하는 방식
int[] arr = new int[] {38, 22, 19};
Bubble Sort의 과정은 아래 순서로 이루어진다.
1) 맨 앞의 원소와 그 다음 원소를 비교한다.
if(arr[0] > arr[1]) {
// 0번 인덱스 값과 1번 인덱스 값 SWAP
}
2) 앞의 원소가 다음 원소보다 크다면 두 값을 SWAP(교환)한다.
if(arr[0] > arr[1]) {
int tmp;
tmp = arr[0];
arr[0] = arr[1];
arr[1] = tmp;
}
3) 한칸씩 이동하여 다음 원소와 그 다음 원소를 비교한다.
if(arr[1] > arr[2]) {
int tmp;
tmp = arr[1];
arr[1] = arr[2];
arr[2] = tmp;
}
4) 결과
정렬 전 : 38 22 19
정렬 후 : 22 19 38
5) 결과 정리
위의 예제로 봤을 때, 결과 비교는 총 2번 이루어졌고, 1~3의 과정도 2번 이루어졌다.
정리하자면,
요소가 n개 일 때, (n - 1번의 SWAP) X (n - 1) 과정 반복
위와 같은 규칙으로 Bubble Sort 가 이루어진다.
따라서 위의 3가지 요소를 가지고 있는 arr 를 공식을 적용해 정렬해보면 아래와 같다.
int[] arr = new int[] {38, 22, 19};
for(int i=0;i<arr.length-1;i++) {
for(int j=0;j<arr.length-1;j++) { // j<arr.length-1-i(9/15추가)
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
6) 시간복잡도, 특징
$O(n^2)$ 가장 쉽고 기본적인 알고리즘
사실상 잘 쓰이지 않는 정렬 방법이다.
9/15일 추가
배웠던 버블 정렬 코드와 검색해서 나오는 코드가 달라(두번째 for문에서 j<arr.length-1-i) 강사님께 질문했는데, 어떤 코드던지 작동 방식에는 크게 차이가 없어 상관 없다고 하셨다.
물론 배웠던 코드보다 더 발전된 코드가 있지만, 차이는 미미해서 이해하기만 하고 넘어가는 것으로 결론내렸다.
4. Selection Sort (선택 정렬)
수업에서 배우지는 않았지만, 같이 알아두면 좋다고해서 공부 겸 정리해본다.
선택 정렬은 카드를 무작위로 뽑아 손에 들었을 때, 제일 작은 값을 가진 카드를 뽑아서 앞 자리에다 끼워넣는 모습을 상상하면 된다.
int[] arr = new int[] {8, 3, 10, 9, 14};
1) 일단 맨 앞 index를 최솟값으로 설정
for(int i=0; i<arr.length-1;i++) {
int min = i;
}
2) 최솟값이 나오면 최솟값을 바꿔준다.
for(int j=i+1;j<arr.length;j++) {
if(arr[min]>arr[j]) {
min = j;
}
}
3) 그 다음자리 값과 그다음 최솟값을 SWAP 한다.
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
4) 3번 반복
// 맨 뒤 요소는 이미 정렬되어 있으므로 제외
for(int i=0; i<arr.length-1;i++) {
// 1. 일단 맨 앞 index를 최솟값으로 설정
int min = i;
// 2. 최솟값이 나오면 최솟값을 바꿔준다.
for(int j=i+1;j<arr.length;j++) {
if(arr[min]>arr[j]) {
min = j;
}
}
// 3. 최솟값과 맨 앞 요소를 SWAP
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
5) 결과
정렬 전 : 8 3 10 9 14
정렬 후 : 3 8 9 10 14
혼자서 코드를 작성했을 때, 3번의 위치를 2번 for문 안으로 위치시켰었다.
2번 for문이 모두 완료되었을 때 최종 최솟값이 나오는 것이므로 for문이 끝나고 난 뒤 SWAP을 해줘야한다.
6) 시간복잡도, 특징
Bubble Sort와 마찬가지로 $O(n^2)$
마찬가지로 쉽고 기본적인 알고리즘
역시 잘 쓰이지 않는 것 같다. (확실하진 않지만 좋은 알고리즘은 아니므로)
알고리즘은 따로 계속 정리하지는 않을 것 같다.
알고리즘 문제를 풀면서 필요하면 그때그때 정리할 생각이고, 동빈북도 있고 다른 좋은 강의나 포스팅도 많으므로….
물론 수업에서 나오면 정리할 것이다.
5. Shuffle Algorithm (카드섞기 알고리즘)
중복되지 않는 수를 만드는 방법
카드를 뽑는 것을 구현했기 때문에 중복이 없다.
어떤 수를 무작위로 뽑을 때, 중복이 되지 않게 하는 방법을 배웠다.
중복인지 아닌지 아는 방법은 앞전에 뽑은 수는 기억하는 것이 필수이다.
그래서 배열을 많이 쓴다고 한다.
대부분 아는 배열에 뽑은 값이 있냐 없냐로 구현하는 방법을 배울 줄 알았는데, 이런 코드는 배운 적이 없어서 재미있었다.
int[] arr = new int[] {1, 2, 3, 4, 5};
1) 카드를 섞는다.
for(int i=0;i<arr.length*100;i++) {
}
2) 0~마지막 인덱스까지 랜덤으로 각각 1개씩 총 2개를 뽑는다. (카드를 1개씩 뽑는 과정과 동일)
int x = (int)(Math.random()*arr.length);
int y = (int)(Math.random()*arr.length);
3) 뽑은 두개의 카드를 바꿔준다.
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
4) 그럼 동일한 카드가 뽑힐 수도 있잖아요?!
그래서 1번 과정에서 100번정도로 반복문을 돌려준다.
동일한 카드가 뽑히더라도 100번 셔플하는 과정에서 큰 차이가 없이 섞어질 것이다.
5) 최종 코드
int[] arr = new int[] {1, 2, 3, 4, 5};
for(int i=0;i<arr.length*100;i++) {
int x = (int)(Math.random()*arr.length);
int y = (int)(Math.random()*arr.length);
int tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
6. 그외..
\t은 탭(tap)을 의미하며, 띄어쓰기 8번과 같다.
댓글남기기