66일차 - TIL

오늘 한것

• SELECT 구문 문제풀이
  • 조인
    • 이너조인
      • where 조인의 경우 : 조인 후,  where 절로 필터링
      • INNER JOIN ON의 경우 : ON의 조건절 먼저 수행후 조인 수행
  • 서브쿼리
    • 주로 검색 결과를 좁히기 위해 사용, SELECT문에 사용할 경우 한 줄의 결과일 때만 사용 가능
    • FROM절에서 사용할 경우 인라인 뷰라고 부르며, 특정 조건식을 갖는 SELECT 문을 테이블처럼 사용할 수 있다.
    • WHERE절에서 사용할 경우 집계함수를 사용해야 하는 경우에도, GROUP BY로 그룹화하지 않고 결과 출력 가능
  • GROUP BY 여러개 사용할 경우, 세부분류되어 있는 상태에서 대분류, 소분류와 같이 따로 집계가 가능하다.
• 운영체제 - 스레드와 동시성
  • 싱글 스레드와 멀티 스레드
    • 스레드는 CPU 활용의 기본 단위로, 스레드 ID, 프로그램 카운터, 레지스터 집합, 스택으로 구성
      • 같은 프로세스에 속한 다른 스레드와 운영체제 자원을 공유 가능
      • 프로세스 생성 시간보다 스레드 생성 시간이 시간과 리소스가 적게 소요된다.
    • 멀티 스레딩 모델
      • 다대일 모델
      • 일대일 모델
      • 다대다 모델
      • 2단계 모델
    • 유저 스레드와 커널 스레드
  • 암묵적 스레딩 방식 : 스레드의 생성 및 관리를 컴파일러, 실행시간 라이브러리에게 책임을 전가한다.
    • 스레드 풀
    • OpenMP
    • GCP
• 알고리즘 전략 - 동적계획법과 (분할과 정복)
  • 동적 계획법 - 메모이제이션을 이용해 중복 값을 재사용한다.
    • 피보나치 수열
  • 분할과 정복 - 재귀함수를 이용해 하나의 문제를 작은 단위로 나누어 해결하고 부분 해결한 문제들을 합치면서 해결
    • 병합정렬
    • 퀵정렬

---

#스레드와 동시성

싱글 스레드와 멀티 스레드

스레드의 동시성

---

#동적 계획법 - 메모이제이션 이용

package org.algorithms.strategy.dpanddivideconquer.dp;

public class Dp {
    //알고리즘 풀이 전략 중 하나인 동적 계획법과 분할&정복의 공통점과 차이점
    //동적 계획법 (Dynamic Programming) : 메모이제이션 기법 사용
    //상향식 접근법으로 가장 최하위 문제 해결 후 해결한 해답을 재사용해 상위 문제를 해결해 나가는 기법
    //: 입력 크기가 작은 중복되는 부분 문제를 해결하고 메모이제이션 기법을 사용함으로써, 이전에 계산한 값을 다시 계산하지 않도록 저장한다.
    // 저장한 값을 재사용해서 실행 속도를 빠르게 하는 기술
    //Ex) 피보나치 수열


    //피보나치 문제 - strategy
    public int fibonacci(int data, int[] arr){
        //1~data까지
        //배열로 intStream만들기
//        IntStream stream = Arrays.stream(arr);
        for(int i=1;i<=data;i++){
            if(i==1||i==2) arr[i]=1;
            else arr[i]=arr[i-2]+arr[i-1];
        }
        return arr[data];
    }
    public static void main(String[] args) {
        Dp dp = new Dp();
        int n=9;
        int[] arr = new int[n+1];
        System.out.println("dc.fibonacci("+n+") = " + dp.fibonacci(n, arr));
    }
}

 

# 분할과 정복 - 재귀 함수 이용

 

package org.algorithms.strategy.dpanddivideconquer.dc;

public class Dc {
    //알고리즘 풀이 전략 중 하나인 동적 계획법과 분할&정복의 공통점과 차이점
    //문제를 작은 단위로 분할해 푸는 것은 동일

    //분할과 정복 (Divide & Conquer) : 재귀함수 사용
    //하향식 접근법으로 상위의 해답을 구하기 위해, 아래로 내려가면서 분할하지 못할 때까지 내려가 최하위의 해답을 구해서 합치는 방식
    //문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 합치는 방식이기 때문에
    //부분 문제가 중복되지 않으므로, 메모이제이션을 사용해 저장하지  않아도 된다.
    //Ex) 병합 정렬, 퀵 정렬
    
    //피보나치 문제 - divide&conquer : 재귀함수 이용하면, 재사용하지 않기 때문에 낭비
    public int fibonacci(int data){
        if(data<=1){
            return data;
        }else return fibonacci(data-1)+ fibonacci(data-2);
    }
    public static void main(String[] args) {
        Dc dc = new Dc();
        System.out.println("dc.fibonacci(3) = " + dc.fibonacci(3));
    }
}

---

 

 

# 병합 정렬

1. 재귀함수를 이용해 나눌 수 있는 최소 단위로 분리
2. 분리한 단위들을 해당하는 로직을 구현해 병합과정 수행

package org.algorithms.strategy.dpanddivideconquer.dc;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Mergesort {
    //병합 정렬
    //: 상위의 문제 해결을 위해 분할 가능한 작은 단위까지 분할 후, 합친다.
    //(1) split
    //: 더이상 분리가 불가능할 때까지 분리
    //(2) merge(left, right)
    //: 각각의 포인터를 비교하기 시작하는데 넣어진 인덱스에는 +1하면서 끝까지 비교

    // 4, 1, 2, 5, 7, 5

    /*
    *두 개의 리스트로 분할하는 메서드
     */
    public void splitFunc(ArrayList<Integer> dataList){

        //예외처리
        if(dataList.size()<=1) return;

        //중간 지점 변수
        int mid= dataList.size()/2;

        ArrayList<Integer> leftArr= new ArrayList<>(dataList.subList(0, mid));
        ArrayList<Integer> rightArr= new ArrayList<>(dataList.subList(mid, dataList.size()));
        System.out.println("leftArr = " + leftArr);
        System.out.println("rightArr = " + rightArr);
    }

    /*
    *배열 개수가 1개가 될때까지 분할하고 -> 각각 splitFunc으로 분할해
    * 1개가 되면 합치는 메서드 -> 합치는 메서드인 mergeFunc의 인자로 전달한다.
    * 합치는 메서드 -> 비교 후, 작은 경우 넣고 작은 쪽의 포인터를 이동하면서 하나의 배열로 만든다.
     */
    public ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> dataList){
        if(dataList.size()<=1){
            return dataList;
        }
        int mid= dataList.size()/2;
        ArrayList<Integer> leftArr=mergeSplitFunc(new ArrayList<>(dataList.subList(0, mid)));
        ArrayList<Integer> rightArr=mergeSplitFunc(new ArrayList<>(dataList.subList(mid, dataList.size())));

        return mergeFunc(leftArr, rightArr);
    }
    public ArrayList<Integer> mergeFunc(ArrayList<Integer> leftArr, ArrayList<Integer> rightArr){
        ArrayList<Integer> result = new ArrayList<>();
        int lt=0;
        int rt=0;
        while(lt!= leftArr.size() && rt!=rightArr.size()){
            if(leftArr.get(lt)<=rightArr.get(rt)){
                result.add(leftArr.get(lt++));
            }else{
                result.add(rightArr.get(rt++));
            }
        }
        while(lt!=leftArr.size()){
            result.add(leftArr.get(lt++));
        }
        while(rt!=rightArr.size()){
            result.add(rightArr.get(rt++));
        }
        return result;
    }


    /*
    *랜덤 테스트 데이터 추가
     */
    public static void main(String[] args) {
        Mergesort mergesort = new Mergesort();
//        ArrayList<Integer> dataList= (new ArrayList<>(Arrays.asList(4, 1, 2, 5, 7, 5)));
//        mergesort.splitFunc(dataList);
        ArrayList<Integer> dataList= new ArrayList<>();
        for(int i=0;i<100;i++){
            dataList.add((int) (Math.random()*100));
        }

        System.out.println("mergesort.mergeSplitFunc(dataList) = " + mergesort.mergeSplitFunc(dataList));
    }
}

 

#퀵 정렬

1. 기준점 정하기
2. left, right 리스트로 분류하기
3. 분류한 결과가 데이터 수가 1개가 될 때까지 재귀적으로 메서드 수행 후, 합친다

package org.algorithms.strategy.dpanddivideconquer.dc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QuickSort {
    //퀵 정렬
    //1. 기준점을 정하기
    //2. left, right 리스트로 분류하기
    //3. 데이터 수가 1개가 될때까지 분류한 리스트에서 다시 기준점 잡고 분류하는 작업 수행

    static ArrayList<Integer> result = new ArrayList<>();

    public ArrayList<Integer> sort(ArrayList<Integer> dataList){

        if(dataList.size()<=1) return dataList;
        int pivot=dataList.get(0);

        ArrayList<Integer> leftArr =new ArrayList<>();
        ArrayList<Integer> rightArr = new ArrayList<>();

        for(int index=1; index<dataList.size();index++){
            if(dataList.get(index)>pivot){
                rightArr.add(dataList.get(index));
            }else{
                leftArr.add(dataList.get(index));
            }
        }
//        System.out.println("분류");
//        System.out.println(leftArr);
//        System.out.println(pivot);
//        System.out.println(rightArr);

        ArrayList<Integer> mergedArr = new ArrayList<>();
        mergedArr.addAll(this.sort(leftArr));
//        mergedArr.add(pivot);
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(this.sort(rightArr));
//        System.out.println(mergedArr);

        return mergedArr;
    }

    public static void main(String[] args) {
//        Integer[] dataList= {9,4,1,2,5,7,8};
//        QuickSort sort = new QuickSort();
//        System.out.println("sort.sort(new ArrayList<>( Arrays.asList(dataList))) = " + sort.sort(new ArrayList<>(Arrays.asList(dataList))));

        //테스트 데이터 생성
        ArrayList<Integer> testData=new ArrayList<>();
        for(int index=0;index<100;index++) testData.add((int)(Math.random()*100));;
        QuickSort quickSort = new QuickSort();
        System.out.println("quickSort.sort(testData) = " + quickSort.sort(testData));
    }
}

 

 

내일 할것

• SELECT 구문 문제풀이 (2)
• 순차 탐색과 이진 탐색
• 스프링 -서블릿과 JSP