14일차 수업 정리(String, Encoding, Sort & Search )

**java.lang.String

1. static String format(String format, Object data...)
    => 서식에 맞추어 데이터를 문자열로 만들어 리턴해주는 메소드
    => System.out.printf와 사용법이 동일(printf : 화면에 출력, format : 문자열을 만들어서 리턴 해주는 메소드)

    => GUI(graphic User Interface - 화면이 있는 인터페이스 : Mac OS, Linux, Windows, Android, iOS등)
        - 프로그래밍의 화면에 보여지는 클래스들은 문자열이나 이미지만 출력할 수 있음
        - 문자열이 아닌 데이터들은 문자열로 변환을 해야만 출력이 가능

    => 문자열이 아닌 데이터 1개를 숫자로 변환 : toString메소드
    => 문자열 + 문자열 = 문자열문자열  ->  "ab" + "gh" = "abgf";
    => 문자열 + 숫자 = 문자열숫자(문자열)  ->  "gg" + 5 = "gg5";
        - 위 3가지 방식으로 문자열을 만들수 있지만 위의 방식은 서식설정 불가
        - 서식에는 자릿수 확보, 맞춤, 숫자데이터의 경우 빈자리에 0을 추가해 주는 것등이 있음
        - 이 메소드 이외의 방법으로 자바에서는 java.text 패키지에 있는 Format클래스를 이용

    => 서식 : %다음에 숫자와 영문자 1개로 설정
        %숫자d : 정수를 숫자 만큼의 자리로 생성(f: 실수, b: boolean, c: char, s: String - 인스턴스명 매핑시 toString 호출
        - default : 숫자는 오른쪽 맞춤, 문자열은 왼쪽 맞춤
        - 데이터의 길이보다 작은 숫자를 설정시 설정된 숫자는 무시
        - 정수 데이터의 경우 숫자 앞에 0을 붙이면 앞 빈자리에 0을 추가( %03d -> 12 : 012)
        - 소수 자릿수보다 아래자리에서는 반올림(default : 소수 6째자리)
        - 전체 자릿수를 생략하고 .소수 자릿수만 입력하기도 함

2. Encoding
    => Encoding : 데이터가 메모리에 저장되는 형태로 변환하는 것
    => Decoding : 메모리에 저장된 값들을 사용하기 위해서 변환하는 것
        - 'A' -> 65 : Encoding(암호화라고 번역하기도 함)
        - 65 -> 'A' : Decoding(복호화라고 번역하기도 함)
    => 영문, 숫자, 키보드내 특수문자는 전세계 모든 운영체제에서 인코딩, 디코딩 방식이 동일
        - 한글같이 영문이 아닌 문자들은 인코딩 방식이 여러개 존재 할 수 있음
        - 인코딩 방식이 다르면 해석시 다른문자로 해석(출력시 글자가 깨짐)
    => 한글 인코딩 방식 : Ms949(cp949 - MS-Window), EUC-KR : web에서 한글 표션, UTF-8 : 전세계 모든 문자 표현,

        iso-8859-1(iso-latin-1):서유럽

    => byte[] getBytes() : 문자열을 byte 배열로 리턴 해주는 메소드
        - 이 메소드에 문자열로 인코딩 방식을 대입하면 인코딩 방식으로 바이트 배열을 생성하여 리턴
    => byte 배열을 가지고 문자열을 생성 - new String(byte[] bytes, String enctype)

//면접전에 읽어볼거(call by value, call by referance 차이 / StringBuilder / 다형성 등)
3. StringBuilder
    => String의 문제점을 해결하기 위해서 등장한 클래스(메모리 낭비 절감)
    => String에 Literal을 저장하면 데이터가 static 영역에 저장됨(static영역의 데이터는 변경 불가)
        - '+'연산을 이용해 결합시 복사 작업이 발생(메모리 낭비)
    => 해당 메소드는 여분의 공간을 가지고 인스턴스가 만들어져 문자열 추가시 복사작업을 하지 않음
    => 문자열 추가시 void append(String str)을 이용
    => 다시 원래의 문자열로 되돌릴때는 toString()을 호출
    => 최근의 자바버전에서는 String사용시, StringBuilder처럼 동작하기 때문에 StringBuilder를 이용하지 않아도 됨

**Generics
    => 자료형을 미리 지정하지 않고 인스턴스를 만들때 지정하여 사용하는 것(==템플릿프로그래밍)
    => 동일 알고리즘을 사용하는 경우, 데이터의 종류로 인해 별도의 메소드를 만드는 번거로움을 없애기 위해 사용
         (최근 등장하는 언어의 경우 대부분 지원)
    => 자료구조 클래스에 이용되는 경우가 많음
1. 클래스 생성
    => 형식 : class 클래스명 <미지정 자료형명 나열>{ (클래스 내용) (미지정 자료형 사용) }

2. 인스턴스 생성
    => 형식 : 클래스명 <실제 자료형> 변수 = new 클래스명 <실제 자료형>();
                  (v1.7 부터는 인스턴스 생성시 자료형 생략 가능 - new 클래스명<>();)

3. 인스턴스 생성시 실제 자료형 미기재시 Object로 간주

4. 실제 자료형은 참조형만 가능(기본형 X)
    => boolean, byte, short, char,        int,       long,  float, double는 안됨
        (Boolean, Byte, Short, Character, Integer, Long, Float, Double로 설정)

**java.util 패키지
    => Data Structure(자료구조) :  여러개의 데이터 저장시, 어떤 방법으로 저장 및 사용할 것인지
        - 자료구조를 제대로 선택하지 않으면 알고리즘도 제대로 동작하지 못함
    => 자료구조는 List, Set, Map(Dictionary)로 구분
    => Java에서는 자주 사용하는 자료구조를 클래스나 인터페이스 형태로 제공(각 구조의 특성 이해가 필요)
        - 장점보다는 단점을 기억하여 선택하는 것이 용이
    => 코딩테스트를 하는 기업지원시 자료구조는 학습이 마아아않이 필요!
    => List : 배열(Array-Dense List), Vector(ArrayList), LinkedList, Stack, Queue, Deque 등
    => Set : 데이터를 중복없이 해싱을 이용하여 저장
    => Map : 데이터를 Key(Name)와 Value쌍으로 저장

1. 배열(Array)
    => 동일한 자료형으로 만들어진 데이터들의 연속적인 모임
    => 한번 생성시 크기 변경 불가
  1) 장점 : 메모리 낭비가 없음
  2) 단점 
    => 데이터를 삽입, 삭제시 복사 작업을 이용하여 수행
    => 연속된 빈 공간이 없으면 생성 불가
  3) 생성
    => 처음부터 데이터가 존재하는 경우 - 공부할때만 사용
         자료형[] 배열명 = {데이터 나열};

    => 데이터를 다른 곳에서 가져와서 생성
         자료형[] 배열명 = new 자료형[데이터 개수];
         배열명[인덱스] = 데이터;
  4) 배열의 데이터 접근
    => 배열명[인덱스]  //읽기
    => 배열명[인덱스] = 데이터  //데이터 변경
    => 인덱스는 0부터 시작하고 갯수-1까지, 인덱스가 잘못되면 ArrayOutOfBoundsExecption발생
  5) 배열의 데이터 갯수 : 배열명.length
  6) 배열 데이터를 전체 접근
    => 일반 반복문 사용 : for(int i = 0; i<size; i+=1){ ar[i]; }
    => 빠른 열거 이용 - 대부분 이 방법 사용 for-each라고도 함
         for(int temp : ar){ temp; }

2. java.util.Arrays
    => 배열과 관련된 작업을 위한 메소드를 소유한 클래스
  1) sort : 정렬을 해주는 메소드
    => 정렬 : 데이터를 순서대로 나열
    => 정렬 방식 : 오름차순(ascending - 작은것에서 큰 것 순으로 배치, 기본)
                          내림차순(descending - 큰 것에서 작은것 순으로 배치)
    => 정렬 알고리즘 : 정렬 방법에 따른 분류
        - selectionsort : 선택정렬
        - bubble sort : 버블 정렬
          ==> 여기까지는 제어문 연습을 위해 수행
        - insertion sort : 삽입 정렬
        - quick sort
          ==> 면접 보러갈때는 여기 정도까지
        - heap sort
        - merge sort
        - radix sort
    => 정렬의 목적 : 데이터를 순서대로 나열하여 검색을 빠르게 하기 위해
    => static void sort(Object[] ar) : Comparable 인터페이스를 implements한 데이터의 배열이어야 함
                                               (Comparable : 크기비교가 가능한 메소드를 소유한 인터페이스)
        - Comparable 인터페이스를 implements 하지 않은 클래스의 인스턴스 배열 정렬을 위해서는 
          static void sort(Object[] ar, Comparable <> comp) 메소드를 이용
        - Comparator 인터페이스를 implements한 클래스의 인스턴스를 매개변수로 1개 더 대입하면 됨
        - Comparator 인터페이스를 가지고 인스턴스를 만들때 1개의 자료형을 설정해야 하고 메소드에 양수를 리턴하

          면 앞의 데이터를 뒤로 배치하고 음수를 리턴하면 앞의 데이터를 앞에 배치
        -  숫자데이터는 뺄셈을 이용하고 String과 Data는 compareTo 메소드를 이용하여 크기를 비교함



1. 순차 검색(sequential search) : 처음부터 끝까지 조회

2. 제어 검색() : 데이터 정렬후 검색(없을 경우 음수 반환)
  1) binarySearch(이분 검색) : 작으면 왼쪽, 크면 오른쪽(중앙과 비교)
  2) Fibonacci search(피보나치 검색) : 
  3) 보간 검색 : 데이터가 균등하지 않으면 별로 안좋음
  4) binaryTree 검색 : 작으면 왼쪽 트리, 크면 오른쪽 트리

3. 블럭 검색 : 블럭은 정렬이 되어있지만 내부는 안되있음

4. 해싱(hashing) : 위의 방식들은 찾는 시간이 자료에따라 제각각이지만 이 방식은 모든 접근시간이 같음(가장 빠른 방식)