[Java 풀스택 과정 강의] 2월 26일

※ TIL와는 별개로 적는 개인 개발 일지라서 말은 좀 편하게하는 페이지입니다.
일지이기 때문에 일기의 성격이 더 강합니다.

 

 

1차원 배열

사실 배열은 이미 배운 부분이 있어서 간단한 부분만 톺아본다.

 

// 배열 초기화 방법
int arr = new int[3];

int[] arr = {10, 20, 30, 40, 50};

int[] arr = new int[]{10, 20, 30};

// 아래 방법은 불가능하다(길이 지정 및 요소 지정)
int[] arr = new int[3]{10, 20, 30};

 

 

배열의 길이를 알기 위해서는 length를 사용한다. 메서드가 아님에 주의할 것.

 

 

배열 순회 패턴

기본적인 순회는 for문을 사용한다.

 

int[] arr = {1,2,3};

for(int i = 0; i < arr.lenght; i++){
	System.out.print(arr[i]);
}

 

 

그리고 for-eacth 순회도 존재한다. for-each는 아쉽게도 인덱스 사용이 불가능하여 for문보다 덜쓰일 때도.

 

int[] arr = {1,2,3};

for(int num : arr) {
	System.out.print(num);
}

 

역방향 순회도 존재한다. length -1에서 시작하여 >=0이 될때까지 i를 감산한다.

 

int[] arr = {1,2,3};

for(int i = arr.length - 1; i >= 0; i--){
	System.out.print(arr[i]);
}

 

이러한 배열 순회를 통해 max값이나 min 값을 사용할 수도 있다.

 

int[] arr = {1,2,3};
int min = arr[0];
int max = arr[0;]

for(int i = 0; i < arr.lenght; i++){
	if(arr[i] > max) max = arr[i];
    if(arr[i] < min) min = arr[i];
}

System.out.print("최대값 : " + max);
System.out.print("최소값 : " + min);

 

합계 및 평균도 활용이 가능하다.

 

int[] arr = {1,2,3};
int sum = 0;

for(int num : arr) {
	sum += num;
}

System.out.println("합계: " + sum);

double avg = (double) sum / arr.length;

System.out.println("평균: " + avg);

 

 

배열을 활용하여 값을 검색하거나 카운팅도 가능하다. 탐색의 경우 선형탐색으로, 경우에 따라서는 오래 걸리기 때문에 다른 방법들을 사용한다. 실제 선형 탐색에서도 break;로 시간을 최적화하는 방식을 사용한다.

 

 

검색

검색에는 순차 검색, 이진 검색, 인덱싱, 깊이 우선(DFS), 너비우선(BFS), 해싱(Hashing) 등의 방법이 있다. 수업에서는 순차와 이진을 우선하였다. 순차의 경우 간단히 값이 일치하느냐에 따라서 확인하는 것이므로, 생략한다.

 

이진 검색

자료의 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 다만 자료가 오름차순이든 내림차순이든 정렬되어 있어야 한다. 과정은 다섯단계라고 할 수 있다.

 

중앙 선택 → 값 비교 → 구간 축소(left) → 구간 축소(right) → 이를 반복하여 결과 도출

 

int binarySearch(int[] a, int key) {
    int left=0, right=a.length-1;
        while (left <= right) {
            int mid = (left+right) /2;
            if (a[mid] == key) return mid; // 성공
            if (a[mid] > key) right = mid - 1; // 왼쪽 구간
            else left = mid + 1; // 오른쪽 구간
        }
    return -1; // 실패
}

 

이런 식으로 반절로 줄여가며 검색하는 방법이다.

 

선택 정렬

가장 작은 값을 선택해서 앞으로 보내는 정렬 방식이다. 지난 시간에도 했었으나 더 자세한 설명이 있다.

 

https://bbbbabbbababababa.tistory.com/89#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC

[Java 풀스택 과정 강의] 2월 25일

 

실 코드는 이런 느낌이 된다.

 

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        int n = arr.length;

        // 1. 현재 채울 자리(i)를 정한다.
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i; // 일단 현재 자리가 최솟값이라고 가정

            // 2. i 뒷부분을 전부 뒤져서 진짜 최솟값의 위치(minIdx)를 찾는다.
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j; // 더 작은 쪽을 발견하면 인덱스 갱신
                }
            }

            // 3. 찾은 최솟값과 현재 자리(i)를 딱 한 번 바꾼다(Swap).
            if (minIdx != i) {
                int temp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = temp;
            }
        }

        // 결과 확인
        for (int num : arr) System.out.print(num + " ");
    }
}

 

 

카운팅 정렬

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여 선형 시간에 정렬하는 효율적인 알고리즘이다. 전제 조건으로는 정수형이어야 한다. 인덱스를 사용하기 때문. 정렬 코드는 다음과 같다.

 

int[] countingSort(int[] a, int k) {
    int n = a.length;
    // 1. 빈도 세기
    int[] count = new int[k + 1];
    for (int v : a) { count[v]++; }
    
    // 2. 누적합 계산
    for (int i = 1; i <7 k; i++) { count[i] += count[i - 1]; }
    
    // 3. 안정 배치 (뒤에서 앞으로)
    int[] b = new int[n];
    for (int i = n - 1; i >- 0; i-/) {
        int v = a[i];
        int idx = -/count[v];
        b[idx] = v;
    }
    return b;
}

 

과정은 다음처럼 1. 빈도를 세어 값의 등장 횟수를 카운트 배열에 기록한다. 그리고 각 누적합을 계산한다. 이후 배치를 한다.

좋은 카운팅 정렬의 예제로는 다음이 있다.

 

[코딩 테스트 RUN] SWEA 수업 : 1204. 최빈수 구하기

[코딩 테스트 RUN] SWEA 수업 : 1204. 최빈수 구하기