디바이스 융합 자바(Java) day05 - 버블정렬,최대값 찾기,이진검색,배열 이진검색,flag 변수

지난 주
1. 중첩반복문
  - 별찍기
2. 배열
  - 서로 관련된 데이터
  - 서로 동일한 자료형
  - 몇 개인지 분명히 알아야 함

5일차 수업 내용
       << tab
1. 회사에서 코딩테스트로 많이 보는
   - 사이즈가 큰 중견기업 + 대기업
   - 배열에는 자료구조와 함께 익혀놓으면 좋은 알고리즘 존재
   문제상황 ) 30명 학생 성적 데이터를 저장 -> 배열
   랜덤으로 저장함 : 28번 30번 3번 ..( 방식으로 0번 인덱스부터 저장)
 
    사용하는 상황 : 랜덤하게 데이터를 저장하면
                          무조건 처음부터 끝까지 하나하나 탐색할 수 밖에 없다!
 
    문제상황 ) 만화카페 -> 도서검색대 - 검색 + 위치
                         카테고리, 이름 순서대로 저장
                         만약 위 과정을 하지 않는다면?
                              - 시간낭비.. 책을 찾는 것이 쉽지 않다

   - 배열 -> 자료구조 + 알고리즘
      배열은 "정렬"이 중요!!
   - "정렬" -> "탐색(검색)"
   - 배열을 사용한다는 건, 여러 개의 데이터를 다루는 상황!
      -> 탐색(검색)하겠다는 이야기!
   - "탐색을 효율적으로 빠르게 하려면? -> 정렬"
   
   Google검색 : 배열 정렬 알고리즘
       - 버블, 삽입, 선택, 퀵, 셀, 도수 ...
           -> 6/13 버블정렬을 하고 퀵의 경우 잘 따라올 경우 수업을 할 것


   [버블(거품) 정렬]
   ex ) [ 5 4 3 1 2 ] - 배열의 길이(요소의 개수)가 5개인 배열 
      if. 오름차순 정렬 - 최소 4번 정렬
       1. 5 4 비교하고 큰 수 뒤로
          교환 알고리즘 사용하여...
          [ 4 5 3 1 2 ]
        2. 5 3 비교하여 큰 수 뒤로
          [ 4 3 5 1 2 ]
        3. 5 1 비교
          [ 4 3 1 5 2 ]
        4. 5 1 비교
          [ 4 3 1 2 5 ]
         -> 1회전 정렬
         : 가장 큰 수가 본인 자리를 찾아갈 수 밖에 없다!
         -> 2회전 정렬
          [ 3 1 2 4 5 ] 
              -> 마지막에 4와 5비교해서 작으면 이동 x
         -> 3회전 정렬
          [ 1 2 3 4 5 ]
         -> 4회전 정렬
          [ 1 2 3 4 5 ]

        -> 버블 정렬이 가장 빠른 로직은 아님!
            상대적으로 느린편인데 왜 버블 정렬을 쓰는가?
            각자가 다 맞는 상황이 존재하기 때문!
            
         (?)TMI 뉴스
          - 회사 면접
            -> 현재 핫한 이슈 질문할 때 있음
            -> "대충한 코딩" 이슈가 엄청 나옴
              "자율 주행"(드론배달)
              -> 핫한 이슈 : [돌발상황]
                                : ex ) 공이 갑자기 날라오기, 새가 날라오는 것

   스도코딩으로 버블정렬 짜보기
     data[0]이랑 data[1]이랑 비교함
     더 큰 수를 뒤로([1]로) 보낼 예정
     만약에, 앞의 수가 더 크다면 교환! -> if문

 

오름차순 정렬
package class01;

public class Test01 {
       public static void main(String[] args) {

              // 배열 -> 자료구조 + 알고리즘
              // "정렬"
              /*
               배열을 사용한다는 건, 여러 개의 데이터를 다루는 상황!
               탐색(검색)하겠다는 이야기!
               탐색을 효율적으로 빠르게 하려면? -> 정렬
               */

              // 배열 정렬 알고리즘
              // : 버블, 삽입, 선택, 퀵, 셀, 도수, ...

              // [버블(거품) 정렬]

              int[] data = {5,4,3,2,1};
              // int[] data = new int[5];
              // -> { 0, 0, 0, 0, 0 }

              // 유지보수 유리한 코드(data.length)
              for(int i = 0; i < data.length; i++) {
                     System.out.print(data[i] + " ");
              }
              System.out.println();
              for(int a = 0; a < data.length; a++) { // data.length -1로 써도 가능
                     for(int i=0; i < data.length-1; i++) {
                            if(data[i] > data[i+1]) {
                                   int tmp = data[i];
                                   data[i] = data[i+1];
                                   data[i+1] = tmp;
                            }
                     }
                     for(int i = 0; i < data.length; i++) {
                            System.out.print(data[i] + " ");
                     }
                     System.out.println();
              }
       }
}
만약 28번 라인에 data.length; 로 하게 되면?

 

디버깅표[4,3,5,1,2]
data[i]       data[i+1]       교환
-----------------------------------
   0                1              o
   1                2              x
   2                3              o
   3                4              o
[3,4,1,2,5]
data.length = 최대 4=(i+1)

그러니 data.length-1 로 해야함

+ 1회전 정렬 이후에도 계속 정렬해야 하기에
   for(int a = 0; a < data.length; a++){
 
    } 
    안에 1회전 정렬의 for문 써놓기

----------------------------------------
내림차순 정렬
package class01;

public class Test01 {
       public static void main(String[] args) {

              // 배열 -> 자료구조 + 알고리즘
             // "정렬"
              /*
               배열을 사용한다는 건, 여러 개의 데이터를 다루는 상황!
               탐색(검색)하겠다는 이야기!
              탐색을 효율적으로 빠르게 하려면? -> 정렬
               */

              // 배열 정렬 알고리즘
              // : 버블, 삽입, 선택, 퀵, 셀, 도수, ...

              // [버블(거품) 정렬]

              int[] data = {1,2,3,4,5};
              // int[] data = new int[5];
              // -> { 0, 0, 0, 0, 0 }

              // 유지보수 유리한 코드(data.length)
              for(int i = 0; i < data.length; i++) {
                     System.out.print(data[i] + " ");
              }
              // 40분까지 내림차순으로 새로 작성해보기!!!
              for(int a = 0; a < data.length; a++) {
                     for(int i = 0; i < data.length-1; i++) {
                            if(data[i] < data[i+1]) {
                                   int tmp = data[i];
                                   data[i] = data[i+1];
                                   data[i+1] = tmp;
                            } 
                            // 1개만 바꾸고 출력 
                     } // 1회전 정렬
                     // 1회전 정렬 후 출력
                     System.out.println();
                     for(int i = 0; i < data.length; i++) {
                            System.out.print(data[i] + " ");
                     }
              }
       }
}

디버깅표[1,2,3,4,5]
data[i]       data[i+1]   교환
--------------------------------
   0               1            o
   1               2            o
   2               3            o
   3               4            o

------------
package class01;

public class Test01 {
       public static void main(String[] args) {

              // 배열 -> 자료구조 + 알고리즘
              // "정렬"
              /*
               배열을 사용한다는 건, 여러 개의 데이터를 다루는 상황!
               탐색(검색)하겠다는 이야기!
               탐색을 효율적으로 빠르게 하려면? -> 정렬
               */

              // 배열 정렬 알고리즘
              // : 버블, 삽입, 선택, 퀵, 셀, 도수, ...

              // [버블(거품) 정렬]

              int[] data = {1,2,3,4,5};
              // int[] data = new int[5];
              // -> { 0, 0, 0, 0, 0 }

              // 유지보수 유리한 코드(data.length)
              for(int i = 0; i < data.length; i++) {
                     System.out.print(data[i] + " ");
              }
              System.out.println();
              // 40분까지 내림차순으로 새로 작성해보기!!!
              for(int a = 0; a < data.length; a++) {
                     for(int i = 0; i < data.length-a-1; i++) {
                            if(data[i] < data[i+1]) {
                                   System.out.println("정렬");
                                   int tmp = data[i];
                                   data[i] = data[i+1];
                                   data[i+1] = tmp;
                            }
                     }
                     for(int i = 0; i < data.length; i++) {
                            System.out.print(data[i] + " ");
                     }
                     System.out.println();
              }
       }
}

조건식 더 빨리 끝내는 방법(data.length -a -1)

>> 점점 차수를 줄여나감으로서 조건식을 금방 끝낼 수 있다.

--------------------강사님 방법
package class01;

public class Test02 {
       public static void main(String[] args) {

              int[] data = {1,2,3,4,5};

              // 버블정렬
              for(int a = 0; a < data.length; a++) {
                     for(int i=0; i<data.length-1; i++) {
                            if(data[i]<data[i+1]) {
                                   int tmp = data[i];
                                   data[i] = data[i+1];
                                   data[i+1] = tmp;
                            }
                            // 1개만 바꾸고 출력
                     } // 1회전 정렬
                     // 1회전 정렬 후 출력
                     for(int i = 0; i < data.length; i++) {
                            System.out.print(data[i] + " ");
                     } 
                     System.out.println();
              }
       }
}

---------------------------------------------------

[ 최대값 찾기 ] 알고리즘

ex ) [ 1 3 5 4 2 ]

MAX값 = 1이라고 가정
[1] 인덱스부터 MAX가 잘 설정되었는지 검증!
->[0]이 아닌 이유 : MAX값을 1[0]로 설정했기에 [1]부터

MAX가 [1]인덱스보다 큰가요?(올바른가요?)
   -> MAX가 올바르지 않으면 변경됩니다... 3
MAX가 [2]인덱스보다 큰가요?
   -> MAX가 올바르지 않으면 변경됩니다... 5
MAX가 [3]인덱스보다 큰가요?(올바른가요?)
   -> MAX가 올바르면 변화 없음

디버깅표
data : [1 8 5 9 2]
MAX     i      i<5            MAX<data[i]
--------------------------------------------
  1        1       T            T   -> MAX변경 
  8        2       T                    F
            3       T            T   -> MAX변경
  9        4       T                    F
            5       F : 탈출!     

--------------------------------------------

package class01;

public class Test03 {
       public static void main(String[] args) {
              // [최대값 찾기] 알고리즘
              int[] data = {3,8,5,1,2};
              int MAX=data[0]; // [0]의 값을 MAX라고 단정한다!

              // [최소값 찾기] 알고리즘
              // 최소값은 1이고 [0]에 존재합니다!

              int MIN = data[0]; // [0]의 값을 MIN이라고 단정한다!
              int length = 0;

              // "검증"
              for(int i = 1; i < data.length; i++) {
                     if(MAX < data[i]) {
                            // MAX가 올바르지 않으면 변경됩니다..
                            MAX=data[i];
                            System.out.println("MAX변경 : " + MAX);
                     }
              }

              // MIN "검증"
              for(int i = 1; i < data.length; i++) {
                     if(MIN > data[i]) {
                            MIN=data[i];
                            length = i;
                     }
              }

              System.out.println("최댓값은 " + MAX + "입니다.");
              System.out.println("최소값은 " + MIN + "이고, [" + length + "]에 존재합니다!");
       }
}

---------------------
디버깅표[3 8 5 1 2]
MIN    i     i< 5         MIN>data[i]        length
----------------------------------------------------
  3      1      T                 F
          2      T                 F
          3      T                 T                     3
  1      4      T                 F
          5      F  : 탈출!

-----------------------------강사님 방법

package class01;

public class Test04 {
       public static void main(String[] args) {
              int[] data = {-2,8,5,1,9};
              int MIN=data[0];
              int INDEX=0; // 최소값의 위치(index)를 저장할 변수
              // INDEX 초기화해야만 하는 이유
              // 1) 최소값이 [0]에 존재할 때
              // 2) 스도코딩에 의해 

              for(int i=1; i<data.length;i++){
                     if(MIN > data[i]) {
                            MIN = data[i];
                            INDEX= i; // 최소값을 찾았다! 그 위치를 저장!
                     }
              }
              System.out.println("MIN : " + MIN);
              System.out.println("INDEX : " + INDEX);
       }
}

*INDEX를 초기화해야만 하는 이유*
1) 최소값이 [0]에 존재할 때
2) 스도코딩에 의해

 

----------------------------------

아침 수업 
 - 정렬 : 버블
  : 탐색을 잘 하기 위함
    + 최대값 찾기

 

1~~~10 중에서 정수를 1개 랜덤으로 강사님이 생각
   3번만에 정답! UP/DOWN
5->3->?

최적화된 탐색 방법을 알고있음!
== 이진탐색(이분검색)

전제조건 : "데이터가 정렬되어 있어야만 합니다!!"

[1] 사용자의 편의성 고려
1~100 중에서 정답입력 : 50
UP!
51~100 중에서 정답입력 :90
DOWN!
51~89중에서 정답 입력:79
정답입니다!

[2]유효성 검사
1~100중에서 정답입력: 123
다시입력해주세요!
1~100중에서 정답입력: -10
다시입력해주세요!
1~100중에서 정답입력: 79
정답입니다!

1~~~100
L         H
L         R
S         E

----------------------강사님 방법(+ 내 방식)

// 나의 경우 첫 편의성 고려에서
// 여러가지 입력하는 수가 많았음
// 어쩌고 보면 반복이 많았는데 
// 그 반복을 줄여버리는 것이 min = 1, max = 100값 입력

package class04;

import java.util.Scanner;

public class Test05 {
       public static void main(String[] args) {
              // 1 ~ 100까지
              Scanner sc = new Scanner(System.in);

              int ans = 79; // 정답 정수
              int min = 1; // 입력한 값 중에 최소값
              int max = 100; // 입력한 값 중에 최대값

              while(true) {
                     // [1] 사용자의 편의성 고려

                     System.out.print(min + "~" + max + " 중에서 정답입력 : ");

                     int num = sc.nextInt();
                     // [2]유효성 검사
                     // : 입력 즉시 진행되는 편!
                     if(num < min || num > max) { 
                            // min보다 작거나 max보다 크면
                            System.out.println("다시 입력해주세요!");
                            continue; // 다시 위로 돌아가라!!!!
                     }

                     if(num == ans) { // 지정한 숫자와 입력한 숫자의 값이 같으면
                            System.out.println("정답입니다~");
                            break; // if문 탈출!
                     }
                     else if(num>ans) {
                            System.out.println("DOWN");
                            max = num - 1; // 최대값 - 1 지정
                     }
                     else if(num<ans) {
                            System.out.println("UP");
                            min = num + 1; // 최소값 + 1 지정
                     }
              }
       }
} 
----------------------------------------------
{1,40,50,55,60,70,81,92,94,100}
↑              ↑                   ↑
 L               M                   H
[0]                                   [9]
(0+9)/2 -> -> M[4]

50이 60보다 크니작니?
    ->DOWN!
{1,40,50,55,60,70,81,92,94,100}
↑         ↑
 L          H
50이 40보다 크니작니?
     -> UP!
{1,40,50,55,60,70,81,92,94,100}
        ↑ ↑
         L  H

if(77)
대상 데이터가 없으면 
CROSS(교차)현상이 발생한다!!!!

------------강사님 방법
package class04;

import java.util.Scanner;

public class Test06 {
       public static void main(String[] args) {
              // [이진탐색(이분검색)]
              // -> 탐색할 대상 배열이 "정렬"되어 있어야만 합니다! :D

              int[] data = {1,40,50,55,60,70,81,92,94,100};
              // low point = 1[0], High point = 100[9] Middle point = 60 [4]

              // 도서검색 -> [가] 3번째...
              Scanner sc = new Scanner(System.in);
              // [아이템] 동굴
              boolean flag = true; // 어떠한 행위가 잘 되었는지를 체크하는 변수
              // T / F 밖에 없다

              while(true) {
                     System.out.print("검색 : ");
                     int num = sc.nextInt();

                     int L = 0; // 작은 숫자(인덱스의 작은 수)
                     int H = data.length-1; // 인덱스는 0부터 시작하기에 -1, 큰 숫자(인덱스의 큰 수)

                     while(true) {
                            int M = (L+H)/2; // M : 중간 인덱스 숫자 

                            if(data[M] == num) {
                                   System.out.println("[" + M + "]에 " + num + "가 존재합니다!"); 
                                   break;
                            }
                            else if(data[M] > num) { // DOWN 상황
                                   H=M-1;
                            }
                           else { // UP 상황
                                  L=M+1;
                            }

                            if(L>H) { // 교차(CROSS) 상황
                                   System.out.println("찾는 데이터가 없습니다!");
                                  break;
                            }
                     }
                     if(flag) { // flag 변수가 T상태를 유지하면 멈출 수 있다!
                            // 내가 원하는 데이터를 찾은 상황 -> T
                            System.out.println("찾는 데이터가 없습니다!");
                            // 내가 찾으려는 데이터가 없는 상황 -> F
                            flag = false;
                            break;
                    }
              }
       }
}

----------------------------

1. 버블정렬
2. 최대값 찾기
3. 이진검색
    while()
4. 배열 이진검색
5. flag 변수

 

-----------------------------강사님 문제
package class05;

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

public class Test07 {
       public static void main(String[] args) {
              // 코딩테스트 : 삽입정렬, 선택 정렬 << 
              // + ) 퀵 정렬

              // 랜덤 관련 알고리즘

              // 주사위 눈금, 랜덤 파편, 로또
              // java.util.Random
              Random random = new Random();
              // System.out.println(random.nextInt(6)+1); 
              // 0~5 + 1 => 1~6

              int ans = random.nextInt(100) + 1; // 1~100
              Scanner sc = new Scanner(System.in);
              int L = 1;
              int H = 100;

              while(true) {
                     System.out.print(L+"~"+H+" 정답 : ");
                     int num = sc.nextInt();

                     if(num==ans) {
                            System.out.println("정답입니다! " + ans);
                            break;
                     }
                     else if(num > ans) {
                            System.out.println("DOWN!");
                            H = num-1;
                     }
                     else {
                            System.out.println("UP!");
                            L = num+1;
                     }
              }
       }
}

 

if(ans = 45)
L       H       num        
--------------------
1      100      50
1       49       25
26     49       35
36     49       42
43     49       45 - "탈출"

---------------------
package class05;

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

public class Test07 {
       public static void main(String[] args) {
              // 코딩테스트 : 삽입정렬, 선택 정렬 << 
              // + ) 퀵 정렬

              // 랜덤 관련 알고리즘

              // 주사위 눈금, 랜덤 파편, 로또
              // java.util.Random
              Random random = new Random();
              // System.out.println(random.nextInt(6)+1); 
              // 0~5 + 1 => 1~6

              int ans = random.nextInt(100) + 1; // 1~100
              Scanner sc = new Scanner(System.in);
              int L = 1;
              int H = 100;
              int S = 5;
              boolean flag = true; // T/F

              while(flag) {
                     System.out.print("목숨 : ");
                     for(int i = 1; i <= S; i++) {
                            System.out.print("♥");
                     }
                     System.out.println();
                     System.out.print(L + "~" + H + " 정답 : ");
                     int num = sc.nextInt();
                     System.out.println();

                     if(num==ans) {
                            System.out.println("정답입니다! " + ans);
                            break;
                     }
                     else if(num > ans) {
                            System.out.println("DOWN!");
                            H = num-1;
                            S--; // 하트 감소
                     }
                     else {
                            System.out.println("UP!");
                            L = num+1;
                            S--;
                     }
                     if(S == 0) { // 0보다 작아지면 게임오버
                            System.out.println("게임오버...");
                            flag = false; // TRUE를 FALSE로 바꾸어 반복문 종료
                     }
              }

// 목숨이 3개
// 목숨 --
// 목숨이 0개 -> 게임오버
       }
}

if(ans = 45)
L       H       num     S    
-------------------------
1      100      50      5
1       49       25      4
26     49       35      3
36     49       42      2
43     49       49      1
43     48       46      0 -> "게임오버"


-----------강사님 방법
package class05;

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

public class Test07 {
       public static void main(String[] args) {
              // 코딩테스트 : 삽입정렬, 선택 정렬 << 
              // + ) 퀵 정렬

              // 랜덤 관련 알고리즘

              // 주사위 눈금, 랜덤 파편, 로또
              // java.util.Random
              Random random = new Random();
              // System.out.println(random.nextInt(6)+1); 
              // 0~5 + 1 => 1~6

              int ans = random.nextInt(100) + 1; // 1~100
              Scanner sc = new Scanner(System.in);
              int L = 1;
              int H = 100;
              int S = 5;

              while(true) {
                     System.out.print("목숨 : ");
                     for(int i = 1; i <= S; i++) {
                            System.out.print("♥");
                     }
                     System.out.println()
                     System.out.print(L + "~" + H + " 정답 : ");
                     int num = sc.nextInt();
                     System.out.println();

                     if(num==ans) {
                            System.out.println("정답입니다! " + ans);
                            break;
                     }

                     if(S == 0) { // 0보다 작아지면 게임오버
                            System.out.println("게임오버...");
                            break;
                     }
                     else if(num > ans) {
                            System.out.println("DOWN!");
                            H = num-1;
                     }
                     else {
                            System.out.println("UP!");
                            L = num+1;
                     }
                     S--;
              }

// 목숨이 3개
// 목숨 --
// 목숨이 0개 -> 게임오버
       }
}