KOMAS

배열을 컬렉션 프레임워크로 변환

방법 1

int[] arr = {1,2,3,4,5};
List<Integer> list1 = new ArrayList<>();

for(int i = 0 ; i<arr.length; i++)
    list1.add(arr[i]);

방법 2

int[] arr = {1,2,3,4,5};
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

int 기본형 배열은 boxed()가 필요하다.

String[] strArr = {"K", "O", "M"};
List<String> strList = Arrays.stream(strArr).collect(Collectors.toList());

일반적인 객체 배열은 boxed()가 필요하지 않다.

IntStream is = IntStream.of(1,2,3,4);
List<Integer> list2 = is.collect(Collectors.toList()); // 컴파일에러

그 이유는 Arrays.stream()을 이용해서 기본형 배열을 스트림으로 바꾸게 되면, 타입이 IntStream이 된다.

IntStream을 다시 Stream<T>와 같은 형태로 만들기 위해 boxed()를 사용한다.

컬렉션 프레임워크를 배열로 변환

방법 1

List<Integer> list = Arrays.asList(1,2,3,4,5);
int[] ar = new int[list.size()];

for(int i = 0; i<list.size(); i++)
    ar[i] = list.get(i);

방법 2

List<Integer> list = Arrays.asList(1,2,3,4,5);
int[] arr = list.stream().mapToInt(e->e).toArray();

배열을 컬렉션 프레임워크로 바꿀때와 마찬가지로 Stream<T>를 IntStream으로 변환 후 toArray()

자바코드와 database 테이블 칼럼 매핑

applicationProperty에 해당 기능을 추가했을 경우

mybatis.configuration.map-underscore-to-camel-case=true

자바는 camelCase, Mybatis 연동 databse는 snake_case

일 때 정상적으로 가져온다.

자바가 snake_case로 선언되어있지 않은가 확인해본다.

자바 코드 변경이 불가능한 경우 Mapper sql문에서 snake_case를 camelCase로 변경해줄 수 있다.

ex) @Select("select user_id as userId from User");

JPA 에서 Unable to find user id / id 2번을 못찾는다는 오류가 있었는데, 

data.sql 에 user id 2번이 분명히 존재했다.

data.sql을 다른 곳을 수정하니 정상 동작함

이전에 진행했던 장고 프로젝트를 재가동 시키기로 했다.

(2003, "can't connect to mysql server on 'localhost' ([winerror 10061] 대상 컴퓨터에서 연결을 거부했으므로 연결하지 못했습니다)")

정말 간단한 오류였는데 프로퍼티 키값을 대문자로해야 오류가 나지 않는다.

장고는 데이터베이스 스키마를 소스파일로 작성하여

연동된 데이터베이스에 테이블을 만들어 줄 수 있다.

또한 작성된 migration 파일은 버전관리가 가능하다.

오랜만에 실행하면 적용되지 않은 migrations가 있다고 알려준다.

python manage.py makemigrations

- models.py에 변경 사항이 있다면 마이그레이션 파일을 만들어 준다.

python manage.py migrate

- 데이터베이스에 테이블을 마이그레이션 파일을 보고 맞게 생성해준다.

python manage.py runserver

-서버 실행

이전에 만들어둔 웹이 잘 보인다.

쿠키와 세션 - 서버에서 정보 자체를 갖고있다. 쿠키의 세션ID 매칭을 확인

JWT - 서버에서 정보의 위조만 검사한다.

쿠키와 세션

로그인 유지를 위해선 세션과 쿠키를 활용해야 한다.

하지만 HTTP는 기본적으로 stateless하다.

Stateful

채팅과 같이 지속적으로 연결되어있는 상태를 stateful (지속적 연결)이라고 하고,

HTTP에서 이러한 stateful과 같은 효과를 주는 것이 쿠키와 세션

기존에는 쿠키만 사용했는데, 로그아웃을 안 하면 브라우저가 종료돼도 남아있기 때문에 문제가 되었다.

세션을 도입하여 브라우저가 종료되면 자동 로그아웃되게 했다. (기간 지정 가능)

서버에 중요 데이터를 보관하는 것이 보안적으로도 우수

{세션 ID : Session}으로 서버에 저장하고, 쿠키에 세션 ID를 담아서 브라우저에게 응답

브라우저는 다음부터 쿠키와 함께 서버에 요청.

서버는 쿠키를 열어보고 세션 ID를 확인, 매칭 되는 Session을 사용한다.

톰캣의 SESSION 구조

{ 세션Id : {key : value} }

한번 더 감싸 져 있기 때문에 key:value는 여러 개가 가능하다. 여러 값을 저장할 수 있다.

JSESSION은 쿠키 이름 (세션 ID를 갖고 있다.)

서버상에서는 세션 ID로 이미 분리된 상태이기 때문에, KEY가 똑같아도 전부 구분된다.

JWT

 Http 헤더에 JSON 토큰을 넣은 후 서버는 헤더에 포함되어 있는 JWT 정보를 통해 인증.

서버는 유저 정보를 갖고 있지 않고, 비밀키만 갖고 있기 때문에 부담이 적다. (stateless)

세 부분으로 구성

(1) Header

토큰 유형: JWT

암호방식: (HS256 또는 RSA) 

(2) Payload   (Map 형태)

유저 정보,

만료 시간

(3) Signature

해시알고리즘(

Header +

Payload +

Secret key

) = 시그니처 값

주의점

기본적으로 토큰은 공개되어지면 안된다. (HTTPS)

토큰으로 악용할 가능성이 있다.

JWT의 중점은 위변조 관점, 탈취될 가능성이 있으므로 시간 제한이 있는 Access Token 사용

(1)Header, (2)Payload 는 암호화가 아니다. (Base 64 encoder)

인가에 사용되는 부분은 (3)Signature

HTTPS덕에 정보를 보긴 어렵다.

그래도 중요한 정보는 저장하지 말자. (비밀번호가 있다면 토큰이 만료되도 접근할 가능성 존재)

인증 방식

Header + Payload + SecretKey가 (3) Signature이 나오나 확인한다.

인증 흐름

(1) + (2) + Secret key 이용해 해시 암호화해서 Signature를 만들고, 유저에게 전달한다.

토큰이 다시 왔을 때는 (1) + (2)와 서버의 Secret Key로 Signature를 만들어 본다.

유저가 보내온 Signature 값과 같은지 확인한다. 

일치한다면 서버에서 만들어낸 토큰이고, 위조가 없는 것이니 사용한다.

 - 유저는 Secret Key를 모르기 때문에 Payload를 위조해도 서버와 일치하는 Signature를 만들 수 없다.

 - JWT의 인가 과정은 서버에서 만든 토큰이 맞는지, 데이터가 위조되지 않았는지를 확인하는 것이다.

RSA를 사용하면,

Header + Payload를 개인 키로 암호화하여 Signature를 생성, 토큰을 유저에게 준다.

유저가 다시 서버에게 토큰을 주면, 서버는 공개 키로 Signature를 복호화를 한다.

복호화된 Signature(Header + Payload)를 전달받은 Header, Payload와 일치하는지 확인한다.

두 값이 일치하면 서버의 개인 키로 서명한 위조가 안된 토큰이 맞다.

 - 유저는 개인 키를 모르므로 Header, Payload가 일치하는 암호화 Signature를 만들 수 없다.

Refresh Token, Access Token

로그인 시 JWT 토큰을 두개를 생성해서 사용자에게 주는 방식EXP 기간이 다르기 때문에 해시 값은 완전히 다르다.

기존에는 Access Token만 사용

 - 토큰은 유효 시간이 짧으면 재 로그인으로 불편하고, 유효 시간이 길면 탈취의 위험이 있다.

 - 토큰 요청시마다 새로 발급하면, 서버에 부담을 준다.

Refresh Token을 추가로 사용

 - Refresh Token은 유효기간이 길다. Access Token 만료 시 새로운 Access Token의 발급으로 사용된다.

 - 클라이언트는 브라우저 스토리지에 저장한다.

서버에서는 Access Token이 만료된 것이 확인되면, 

Refresh Token을 달라고 응답을 내려준다.

클라이언트는 Access Token이 만료되면 Refresh Token도 같이 줘야 한다.

두개의 Token을 전부 갖고 있음을 증명해야하기 때문.

Refresh Token이 만료되지 않았다면, Access Token을 재발급해준다.

둘다 만료라면 재로그인 필요.

Spring Security

JWT 

권한 관리가 필요없다면 SecurityContext에 Authentication 객체를 안넣어도 된다.

Security Context에 Authentication을 넣는 이유는, 스프링 시큐리티의 권한 관리 사용을 위해

인증 시 DB 접근 -> 토큰 생성 -> 토큰 반환

인가 시 토큰 검증 -> 토큰 Signature 정상 -> Security Context에 Authentication 객체 담는다.

세션

세션 안에 있는 Security Context에서 꺼내와서 SecurityContextHolder에 담는다.

https://www.inflearn.com/questions/558844

알아야 할 개념

시간복잡도, 공간 복잡도

알아야 할 자료구조

배열, 연결 리스트, 스택, 큐, 덱, 힙, 트리, 해시, 그래프

알아야 할 알고리즘

정렬, 구현, 재귀, 그리디, 탐색(+DFS/BFS, 백트래킹, 이분 탐색), 다이내믹 프로그래밍, 그래프 알고리즘

알고리즘

배열 문제

Array, LinkedList

Sliding window

Two Pointer

1차원 BFS/DFS

구현

재귀

Back Tracking

Union-Find

Divide and Conquer

그리디

정렬

기본 정렬 문제

Merge Sort

Quick Sort

탐색

DFS/BFS

Back Tracking

이분 탐색

Binaray Search

Parametric Search

다이내믹 프로그래밍

기본 DP

2차원 DP

최장 증가 부분 수열(LIS)

그래프

최단경로

Dijkstra

Floyd-Warshall

최소 신장 트리(Minimum Spanning Tree)

Kruscal

Prim

위상 정렬(Topology sort)

도메인 무결성 제약조건

각 속성의 도메인에 지정된 값만을 가져야 한다는 조건이다.

ex) 주문 일자 속성 -> 날짜 값만을 가져야 함

개체 무결성 제약조건

기본키는 NULL이면 안되며, 유일해야 한다.

참조 무결성 제약조건

부모 릴레이션에서 튜플을 삭제할 경우

RESTRICTED : 자식에서 참조하고 있다면 삭제를 거부

CASCADE : 자식의 튜플까지 삭제

DEFAULT : 자식의 외래 키 값을 DEFAULT 값으로 변경

NULL : 자식의 외래키 값을 NULL로 변경

제4 정규형

1 대 N 다치 종속의 제거이다.

하나의 결정자가  다른 속성에서 여러 종속자를 결정할 때 다치 종속한다고 한다.

한 릴레이션에서 1 대 N으로 관계가 나타나도 되지만, 문제가 되는 부분은 1 : N, 1: N 두 개 이상으로

다치 종속이 구성되어있을 때 이상현상이 발생하므로 중심이 되는 속성을 기준으로 릴레이션을 분리해주어야 한다.

해당 테이블에서 과목을 추가하게 되면, 동아리도 추가를 해줘야 하는 문제가 발생한다.

그러므로 이름, 과목 / 이름, 동아리로 분리해줘야 한다.

제 5 정규형

조인 종속성이 존재하면 제5 정규형 대상이다.

조인 종속성이란 마치 조인을 한 것과 같은 릴레이션의 중복을 제거해주는 것을 말한다.

해당 테이블만 놓고 보면 이름과 과목은 연관성이 있고, 이름과 동아리 또한 연관성이 존재한다.

즉, 이름 속성을 기준으로 연관성을 가지므로 조인 종속성이 존재한다고 볼 수 있다.

조인 종속성을 제거하여 분리하면

이름, 과목 / 과목, 동아리 / 이름, 동아리 3개의 테이블이 나오게 된다.

이름, 과목

과목, 동아리

이름 동아리

2개의 테이블을 조인하면 본래의 릴레이션을 형성할 수 없다.

3개의 테이블을 전부 사용하여 조인해야 본래 테이블로 복구가 가능하다.

https://www.acmicpc.net/problem/18111

구현 문제다.

가장 높은 높이부터 0까지 위에서 아래로 차례대로 계산해주는 함수를 호출하며 내려갔다.

로직은 간단한데 구현이 오래 걸린다.

채울 때는 시간을 1초 추가해주는 것도 있지만,

박스가 충분한지 확인해줘야 한다.

출력은 가장 높은 높이의 값을 출력해줘야 해서 우선순위 큐를 사용했다.

코드

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[][] arr;
    static int[] temp;
    static int globalMin = Integer.MAX_VALUE;
    static int globalMax = Integer.MIN_VALUE;
    static int[] su;

    public static void main(String[] args) throws IOException {

        // 입력부
        StringTokenizer st = new StringTokenizer(br.readLine());
        int low = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());
        int boxes = Integer.parseInt(st.nextToken());

        int maxHeight = 0;
        arr = new int[low][col];
        for(int i = 0 ; i<low; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j<col; j++ ) {
                int num = Integer.parseInt(st.nextToken());
                arr[i][j] = num;
                maxHeight = Math.max(maxHeight, num);
            }
        }

        int ans = Integer.MAX_VALUE;
        Queue<HB> q = new PriorityQueue<HB>((o1, o2)->{
            if( o1.time == o2.time)
                return o2.height - o1.height;
            return o1.time - o2.time;
        });

        for(int i = maxHeight; i>=0; i--){
            int[] answer = findTime(i, boxes, arr);
            q.offer(new HB(answer[0], answer[1]));
        }
        System.out.println(q.poll());


    }
    public static int[] findTime(int height, int boxes, int[][] arr){
        int[] ans = new int[2];
        int time = 0;
        // 제거시간
        for(int i = 0 ; i<arr.length; i++){
            for(int j = 0; j<arr[0].length; j++){
                if(arr[i][j] > height){
                    int tt = arr[i][j] - height;
                    time += tt * 2; // 제거 2초
                    boxes += tt;
                }
            }
        }

        // 채우기 시간
        for(int i = 0 ; i<arr.length; i++){
            for(int j = 0; j<arr[0].length; j++){
                if(arr[i][j] < height){
                    int tt = height - arr[i][j];
                    time += tt; // 설치 1초
                    boxes -= tt;
                    if(boxes < 0) {
                        ans[0] =Integer.MAX_VALUE;
                        return ans;
                    }
                }
            }
        }
        ans[0] = time;
        ans[1] = height;
        return ans;
    }
}

class HB{
    int time;
    int height;
    public HB(int time, int height){
        this.time = time;
        this.height = height;
    }
    public String toString(){
        return this.time + " " + this.height;
    }
}

https://www.acmicpc.net/problem/15686

구현 문제를 풀다 보면 삼성 기출을 자주 만난다.

해당 문제도 삼성 sw 역량테스트 기출문제다.

2차원이 나오면 bfs dfs를 의심하게 된다. 하지만 문제를 읽어보면

거리 계산은 단순 수식으로 할 수 있고

백트래킹 문제인 것을 알 수 있다.

주어진 M이 치킨집의 개수이니 

치킨집을 조합으로 선택해서 치킨 거리 MIN을 구해주면 끝이다.

처음 문제를 풀 때 M을 못 보고

1~N까지 조합 백 트래킹 하며 왜 안될까 생각했다.

문제를 잘 읽자

항상 주의할 점 문제를 잘 읽자

제공해주는 변수(입력)가 무엇인지 보자.

코드

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[][] arr;
    static int[] temp;
    static List<Node> clist;
    static List<Node> hlist;
    static int globalMin = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        // 입력부
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int size = Integer.parseInt(st.nextToken());
        int chicken = Integer.parseInt(st.nextToken());
        arr = new int[size][size];

        clist = new ArrayList<>();
        hlist = new ArrayList<>();
        for(int i = 0; i<size; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j<size; j++){
                int cHorHo = Integer.parseInt(st.nextToken());
                arr[i][j] = cHorHo;

                if(cHorHo == 2){ // 치킨집
                    clist.add(new Node(i+1, j+1));
                }else if( cHorHo ==1)
                    hlist.add(new Node(i+1, j+1));
            }
        }
        temp = new int[chicken];
        bt(chicken, 0, 0);
        System.out.println(globalMin);
        
    }public static void bt(int limit, int n , int idx){
        if(limit == n){
            int minSum = 0;
            int[] mins = new int[hlist.size()]; // 모든 집 min 저장
            Arrays.fill(mins, 10000);
            for(int i = 0 ; i<hlist.size(); i++){ // 집
                Node hnode = hlist.get(i);
                for(int j = 0; j<limit; j++){ // 치킨
                    Node cnode = clist.get(temp[j]);

                    int n1 = Math.abs(hnode.x - cnode.x) + Math.abs(hnode.y - cnode.y);

                    mins[i] = Math.min(mins[i], n1);
                }
            }
            for(int e : mins)
                minSum+=e;

            globalMin = Math.min(globalMin, minSum);
            return;
        }

        for(int i = idx ; i<clist.size(); i++){
            temp[n] = i;
            bt(limit, n + 1, i + 1);
        }
    }
}
class Node{
    int x;
    int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    public String toString(){
        return this.x+" " + this.y;
    }
}

https://www.acmicpc.net/problem/1326

1차원 BFS 활용 문제다.

주의할 점은 앞도 확인해줘야 한다는 점, 방문하면 최소이므로 방문한 곳을 방문처리해줘야 한다는 점이다.

방문처리를 하지않고 풀었다가 메모리 초과가 생겼다.

idx를 이용해서 해당 위치의 배수 값을 찾고배수 값으로 방문하지 않았다면 방문처리해주고 큐에 넣어주면 풀 수 있다.

앞과 뒤를 둘다 확인하는 점에 주의하자.

코드

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int[] arr;
    static int[] dp;
    static boolean[] v;

    public static void main(String[] args) throws IOException {

        int count = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        arr = new int[count];
        for(int i = 0 ; i<arr.length; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        dp = new int[10001];
        v = new boolean[10001];
        Arrays.fill(dp, 100_000);

        st = new StringTokenizer(br.readLine()," ");
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        bfs(s - 1, e - 1, count);
        if(dp[e-1] == 100_000)
            System.out.println(-1);
        else
            System.out.println(dp[e-1]);

    }
    public static void bfs(int s, int e, int count){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(s, 1));
        v[s] = true;

        while(!q.isEmpty()){
            Node numbers = q.poll();
            int mul = arr[numbers.idx]; // 배수
            int front = numbers.idx; // <-
            int back = numbers.idx; // ->


            // 뒤를 확인한다.
            while(true){
                back += mul;
                if(back >= count)
                    break;

                if(back == e) { // 찾았다.
                    dp[e] = numbers.jump;
                    return;
                }

                if(!v[back]) {
                    v[back] = true;
                    q.offer(new Node(back, numbers.jump + 1));
                }
            }


            // 앞을 확인한다.
            while(true){
                front -= mul;
                if(front < 0)
                    break;

                if(front == e) { // 찾았다.
                    dp[e] = numbers.jump;
                    return;
                }

                if(!v[front]) {
                    v[front] =true;
                    q.offer(new Node(front, numbers.jump + 1));
                }
            }
        }


    }
}
class Node{
    int idx;
    int jump;
    public Node(int idx, int jump){
        this.idx = idx;
        this.jump = jump;
    }
}