2차원배열, 버블,선택,스왑,디버깅,퀵솔트

1. 메서드(객체지향 1번째 원칙)

1. 2차원 배열

1. 버블정렬, 선택정렬, 삽입정렬, 퀵솔트

1. 로또

2차원 배열

package ex03;

public class TheaterSeats {
    public static void main(String[] args) {
        //배열은 구조 변경 불가능
        int[][] seats = {
                {0,0,0,1,1,0,0,0,0,0},
                {0,0,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,1,1,0},
                {1,1,0,0,0,0,1,1,1,0},
        };

        int sum = 0;
        int count = 0;
        //int row = -1;

        for (int row = 0; row < seats.length ; row++) {
            count = 0;
            for(int i=0; i<  seats[row].length; i++){
                count = count +  seats[row][i];
            }
            System.out.println(row+"번째 행의 관객수는 : " +count);
            sum = sum + count;
        }
        System.out.println("전체 관객수는 :" +sum);
//        row++;
//        count = 0;
//        for(int i=0; i<  seats[row].length; i++){
//            count = count +  seats[row][i];
//        }
//        System.out.println(row+"번째 행의 관객수는 : " +count);
//        sum = sum + count;
//
//        row++;
//        count = 0;
//        for(int i=0; i< seats[row].length; i++){
//            count = count + seats[row][i];
//        }
//        System.out.println(row+"번째 행의 관객수는 : " +count);
//        sum = sum + count;
//
//        row++;
//        count = 0;
//        for(int i=0; i< seats[row].length; i++){
//            count = count + seats[row][i];
//        }
//        System.out.println(row + "번째 행의 관객수는 : " +count);
//        sum = sum + count;
//
//        row++;
//        count = 0;
//        for(int i=0; i< seats[row].length; i++){
//            count = count + seats[row][i];
//        }
//        System.out.println(row + "번째 행의 관객수는 : " +count);
//        sum = sum + count;
//
//
//
//        System.out.println("전체 관객수는 :" +sum);
    }
}

버블 정렬

• 버블 정렬(bubble sort) 알고리즘의 개념 요약 서로 인접(붙어있는)한 두 원소(인덱스)를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다. https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

• 버블 정렬(bubble sort) 알고리즘의 구체적인 개념 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

* 디버깅

chat gpt 무료로 쓸 수 있음 :wrtn.ai

static으로 찾을 때는 클래스명으로 찾음

정렬의 목적

정렬하면 이진트리 가능, 클러스트링이 있어서 중복있어도 빠름

클러스트링
5,9,10,3,4,3,2
->정렬 ->2,3,3,4,5,9,10
군집화 가능, search 빨라짐

선택 정렬

버블정렬 연습문제_내가 연습

이진검색

package ex03.test;

public class BinaryTest01 {
    public static void main(String[] args) {
        //이진 검색 => 반드시 정렬이 되어 있어야 한다.
        int[] arr = {1,2,3,4,5,6,7,8,9}; // 9(갯수)/2=4 =>4번지 정중앙 find -> 8을 찾고자 함

        //target =8

        //0~8번지비교
        // mid = N/2= 4(index 위치값) -> arr[4]=값 5
        //if(8 ==5) -> mid 위치에 타겟이 있다.

        //if(8>5) 참->

        // 5번지[mid+1]부터 8번지까지 비교
        //mid = 7=arr[7]->값 8
        //if(8 ==5) -> mid 위치에 타겟이 있다.
        //if(8>8)

    }
}

package ex03.test;

public class BinaryTest01 {
    public static void main(String[] args) {
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 9 / 2 = 4

        // target = 8

        // start=0 ~ end = 8
        //        // mid = N/2 = 4 -> arr[4] -> 값 5
        //        // if(8==5) -> mid 위치에 타겟이 있다.
        //        // if(8>5) 참
        //
        //
        //        // start=5 (mid+1) ~ end=8
        //        // mid = 7 = arr[7] -> 값 8
        //        // if(8==8) -> mid 위치에 타겟이 있다.
        //        // if(8>8)
        //
        //
        //        // target = 3
        //
        //        // start=0 ~ end = 8
        //        // mid = N/2 = 4 -> arr[4] -> 값 5
        //        // if(3==5) -> mid 위치에 타겟이 있다.
        //        // if(3>5) 거짓
        //
        //
        //        // start=0 ~ end = mid-1
        //        // mid = 7 = arr[7] -> 값 8
        //        // if(8==8) -> mid 위치에 타겟이 있다.
        //        // if(8>8)
    }
}

• 시간복잡도(최악으로 검색하는 횟수) : 풀스캔,선형적으로 늘어남

수가 늘어나면 너무 큰 수는 int로는 부족할 수 있다.
그래서 
2의 8승 = 256
2의 16승 = 65536
2의 4승 = 16
=> 수를 8승, 16승, 4승으로 나타내면 편함=> log사용함
ex> 2의 50000승을 log를 이용하여 간단하게 표현할 수 있다.

시간복잡도는 log 밑이 2

log 2의 n

• 이진트리는 값들이 늘어나도 시간복잡도가 선형적으로 늘지 않음. 검색횟수가 완전 적고(O(logN)) 장점이다.

* 이 정도는 외우자! (단위를 쉽게 알수 있게)

2^8 = 256

2^10 = 1024

2^16 = 65,536

2^32 =42억 9천~~~

package ex03;

public class BinarySearch {
    public static void main(String[] args) {
        // N = 21
        // 시간복잡도 log2(N) -> log2(21) -> 4.xx (max. 뭘 찾는 지에 따라 최대 5번(올림 시킴)만에 찾는 다는 이야기 함.)
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        // 16 / 2*2*2*2*2 -> logn -> log17
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        int N = arr.length;
        final int target = 3;
        int start = 0;
        int end = N - 1;
        int mid;

        int round = 1;
        while (true) {
            // 1 회전
            mid = start + ((end - start) / 2); // 기대값 7
            System.out.println("mid: " + mid);

            if (arr[mid] == target) {
                System.out.println(round + "회전 : " + target + "값은 " + mid + "번지에 있습니다");
                break;
            }

            if (arr[mid] < target) { // 기대값 start 5, end 8
                start = mid + 1;
            }

            if (arr[mid] > target) {
                end = mid - 1;
            }

            System.out.println(round + "회전 start : " + start);
            System.out.println(round + "회전 end : " + end);

            round++;
        }

        System.out.println("시간복잡도 : " + (Math.log(N) / Math.log(2)));
    }
}

퀵솔트

Algorithm Concept

1. 주어진 배열에서 하나의 요소를 선택하고 이를 pivot(피벗) 으로 삼는다.

2. 배열 내부의 모든 값을 검사하면서 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치한다.

3. 이렇게 하면 배열이 두 부분으로 나뉜다. 나뉜 이 두 개의 배열에서 각각 새로운 피벗을 만들어서 두개의 배열로 다시 쪼개어 준다.

4. 더 이상 배열을 쪼갤 수 없을 때까지 진행한다.

Example

Phase 1

Phase 2

Phase 3

Phase 4

Phase 5

Phase 6

Phase 7

Phase 8

Phase 9

More...

implement

#include <stdio.h>
 
int partition (int arr[], int p, int r){
    int low, high;
    int pivot = arr[p]; // pivot 값 설정
 
    low = p + 1; // low 는 pivot의 바로 다음 위치에서부터
    high = r; // high는 전달된 끝지점
 
    while(low <= high){
        while(arr[low] < pivot) low++; // pivot 보다 작은 값이 나올때마다 이동
        while(arr[high] > pivot) high--; // pivot 보다 큰 값이 나올때마다 이동
 
        if (low <= high){ // low와 high 가 중단된 지점이 서로 위치가 역전된 지점이 아니라면
            int temp = arr[low];    // low 와 high 의 값 변경
            arr[low] = arr[high];
            arr[high] = temp;
        }
    }
 
    // 피벗과 high 위치 교환
    int temp = arr[p];
    arr[p] = arr[high];
    arr[high] = temp;
 
    return high; // 피벗 위치 반환
 
}
 
void quick_sort(int arr[], int left, int right){
    if (left < right){
        int pivot = partition(arr, left, right);
 
        quick_sort(arr, left, pivot-1); // 피벗을 기준으로 왼쪽 배열 정렬
        quick_sort(arr, pivot+1, right); // 피벗 기준으로 오른쪽 배열 정렬
    }
}
int main (){
    int arr [] = {3, 2, 1, 5, 7, 9, 6};
 
    quick_sort(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
 
    for (int i = 0 ; i < sizeof(arr)/sizeof(arr[0]) ; i++){
        printf("%d ", arr[i]);
    }
}

5
신고하기
구독하기이 글은 본 저작자 표시, 비영리 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons본 저작자 표시비영리

TISTORY[알고리즘 정리] 퀵정렬(Quick Sort)

[알고리즘 정리] 퀵정렬(Quick Sort)

퀵소트 퀵 정렬은 이름 그대로 매우 빠르게 정렬을 수행하는 알고리즘이다. 기본적으로 분할정복의 성격을 가지고 있고 실제로도 많이 사용되는 대표적인 정렬 알고리즘이다. 동시에 자료구조 수강생들을 괴롭게 하는 친구 중 한명이긴 하지만.. Algorithm Concept 퀵 정렬은 다음과 같은 과정으로 정렬을 진행한다. 정렬은 오름차순으로 진행한다고 가정하자. 주어진 배열에서 하나의 요소를 선택하고 이를 pivot(피벗) 으로 삼는다. 배열 내부의 모든 값을 검사하면서 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치한다. 이렇게 하면 배열이 두 부분으로 나뉜다. 나뉜 이 두 개의 배열에서 각각 새로운 피벗을 만들어서 두개의 배열로 다시 쪼개어 준다. 더 이상 배열을 쪼갤 수 없을 때까지 진행한다. ..

TISTORY