개발 다이어리

코드

import java.util.*;


class 중복순열DFS{
	static int[] pm;
	static int n //수 크기
		     , m// m 배열 길이
	         , cnt;
	static void DFS3(int L) {
		if(L==m) {
			System.out.println(cnt+" "+Arrays.toString(pm));
			return;
		}else {
			for (int i = 1; i <= n; i++) {
				cnt++;
				pm[L] = i;
				DFS3(L+1);
			}
		}
	}
	
	public static void main(String[] args){
		n=3;
		m=2;
		pm=new int[m];
		DFS3(0);
	}
}

결과

2 [1, 1]
3 [1, 2]
4 [1, 3]
6 [2, 1]
7 [2, 2]
8 [2, 3]
10 [3, 1]
11 [3, 2]
12 [3, 3]

나머지 빈 숫자 값 추측해보기

확인 방법은?

코드

package algorithm08;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 최대점수구하기DFS{
    static int answer=Integer.MIN_VALUE
            , n =5 /*문제 수*/
            , m =50/*제한 시간*/
            , sumN  /*문제 합*/
            , sumM; /*제한 시간 합*/
    
    static int[] nArr,mArr;
    
    //L은 레벨로 깊이라고 이해하면 된다.
    static void DFS3(int L) {
        //제한 시간을 넘기면 더 이상 볼 필요없다.
        if(sumM>m) return;
        
        //모든 노드 순회 완료
        if(L==n) {
            answer = Math.max(answer,sumN);
        //아직 순회할 것이 남았다.
        } else {
            //더 했을 때
            sumN+=nArr[L];
            sumM+=mArr[L];

            DFS3(L+1);
            //안 더했을 때
            sumN-=nArr[L];
            sumM-=mArr[L];
            DFS3(L+1);
        }
    }
    
    public static void main(String[] args){
        nArr=getIntArray(1, 15, n);
        mArr=getIntArray(10, 20, n);
        System.out.println(Arrays.toString(nArr));
        System.out.println(Arrays.toString(mArr));
        DFS3(0);
        System.out.println("제한 시간 내 최대 문제 "+ answer);
    }
    
    static int[] getIntArray(int start, int end, int limit) {
        return ThreadLocalRandom.current()
                .ints(start,end+1)
                .distinct()
                .limit(limit)
                .toArray();
    }
}

결과

[6, 1, 12, 8, 7]
[15, 12, 14, 17, 18]
제한 시간 내 최대 문제 27

주어진 문제 묶음에서 제한 시간내에 가장 많이 풀 수 있는 문제 수를 구한다.

고려해야할 값이 두 개라 헛갈릴 수 있지만, 사실상 한 값처럼 처리하면 된다.(같이 더 하고 같이 빼고)

그리고 조건만 좀 더 신경쓰면 그만이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Test {
    public static void main(String[] args) {
        
        List<int[]> list = IntStream.rangeClosed(1, 10)
            .mapToObj(n->getIntArray())
            .collect(Collectors.toList());
        
        
        //Arrays.stream은 인자로 int[]을 받아 우리가 생각하는 int하나하나를 요소로하는 스트림을 만든다.
        IntStream intStream = Arrays.stream(getIntArray());
        //Arrays.asList는 얼핏보면 List<Integer>로 만들어 줄 것 같지만, 아니다.
        List<int[]> list2 = Arrays.asList(getIntArray());
        
        //방법 1 반복문 이용
        List<Integer> list3 = arrayToList(getIntArray());
        //방법 2 스트림 이용
        List<Integer> list4 = intStream.boxed().collect(Collectors.toList());
        
        //번외, List<int[]> List<Integer>로 변환
        List<Integer> list5 = list.stream()
            .map(Test::arrayToList)
            .flatMap(li->li.stream())
            .collect(Collectors.toList());
    }
    
    static List<Integer> arrayToList(int[] arr){
        List<Integer> tmpList = new ArrayList<>();
        for(int v : arr) {
            tmpList.add(v);
        }
        return tmpList;
    }
    
    static int[] getIntArray() {
        return ThreadLocalRandom.current()
                .ints(1, 101)
                .limit(50)
                .toArray();
    }
    
}

구아바 같은 라이브러리를 사용하지 않고는

기본형 배열에서 리스트로 변환은 방법1이 가장 현실적인 것 같다.

코드

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 바둑이승차DFS{

    static int answer=Integer.MIN_VALUE, c, n;

    static int[] arr;
    static int sum;


    void DFS2(int L) {
        if(sum>c) return;
        if(n==L) {
            System.out.println(answer+"    "+sum);
            answer = Integer.max(answer, sum);
            return ;
        } else {
            sum+=arr[L];//가산 했을때
            DFS2(L+1);
            sum-=arr[L];//가산 안했을때
            DFS2(L+1);
        }
    }


    public void DFS(int L, int sum, int[] arr){
        if(sum>c) return;
        if(L==n){
            answer=Math.max(answer, sum);
        }
        else{
            DFS(L+1, sum+arr[L], arr);
            DFS(L+1, sum, arr);
        }
    }

    public static void main(String[] args){
        바둑이승차DFS T = new 바둑이승차DFS();
        arr= ThreadLocalRandom.current()
            .ints(10, 100)
            .distinct()
            .limit(5)
            .toArray();

        //제한 무게
        c = Arrays.stream(arr).sum()/2;
        n=arr.length; //받은 요소 수
        System.out.println(Arrays.toString(arr));
        T.DFS2(0);
        System.out.println("제한무게 "+c);
        System.out.println("최대무게 "+answer);
    }
}

결과

[34, 84, 50, 63, 49]
-2147483648    118
118    133
133    84
133    97
133    83
133    34
133    134
134    133
134    84
134    113
134    99
134    50
134    112
134    63
134    49
134    0
제한무게 140
최대무게 134

모든 경우의 수를 따라 제한무게에 최대한 같은 수 찾기

코드

import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;

//집합 요소를 두 개 부분 집합으로 나눴을 때
//두 집합은 서로소 관계며 값이 같을 경우 YES 출력
class 합이같은부분집합DFS{
    static String answer="NO";
    static int n, total=0;
    boolean flag=false;
    static int[] ch ;
    static int[] arr;
    static int sum = 0;
    static Stack<Integer> stack = new Stack<Integer>();
    static int pushCnt = 0;
    static int popCnt = 0;
    
    
    void DFS2(int L) {
        if(flag||L==n||total/2<sum) return;
        
        if(sum==total-sum) {
            List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
            list.removeAll(stack);
            System.out.println("집합 "+Arrays.toString(arr));
            System.out.println("서로소 집합1 "+stack);
            System.out.println("서로소 집합2 "+list);
            System.out.println("종합 "+total);
            
            System.out.println("푸쉬 수 "+pushCnt);
            System.out.println("팝 수 "+popCnt);
            
            flag = true;
            answer = "YES";
            return;
        } else {
            sum += arr[L];
            stack.push(arr[L]);
            pushCnt++;
            DFS2(L+1);
            sum -= arr[L];
            stack.pop();
            popCnt++;
            DFS2(L+1);
        }
        
    }
    

    public static void main(String[] args){
        합이같은부분집합DFS T = new 합이같은부분집합DFS();
        //집합 요소
        arr = ThreadLocalRandom.current()
            .ints(1, 10)
            .distinct()
            .limit(5)
            .toArray();
        
        n= arr.length ;
        ch= new int[n];
        total = Arrays.stream(arr).sum();
        T.DFS2(0);
        System.out.println(answer);
    }
}

결과

집합 [1, 5, 3, 6, 9]
서로소 집합1 [1, 5, 6]
서로소 집합2 [3, 9]
종합 24
푸쉬 수 6
팝 수 3
YES

주어진 집합을 두 집합으로 나눈 후 서로소 관계이면서 합이 같으면 YES를 출력한다.

나머지 정보는 절차지향적으로 코드를 추적해보기 위함

sum==total-sum 설명

종합에서 누적한 값을 뺀다. 그 값이 누적한 값과 같다면, 현재까지 누적한 집합 요소와 나머지는 합이 같다

추가로 왜, sum==total-sum  블록 안에 콘솔로그를 출력했을까? 

T.DFS2(0);

아래에 출력하게 되면 어떻게 될까?

코드

//각 정점으로 가는 최소 이동 간선수
class 그래프최단거리BFS {
    static int n, m, answer=0;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
    static int[] ch, dis;
    
    public void BFS2(int v){
        LinkedList<Integer> q = new LinkedList<Integer>();
        ch[v] = 1;
        dis[v] = 0;
        
        q.offer(v);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            
            for(Integer next : graph.get(cur)) {
                if(ch[next] == 0) {
                    ch[next] = 1;
                    dis[next] = dis[cur]+1;
                    q.add(next);
                }
            }
        }
    }

    
    public static void main(String[] args){
        그래프최단거리BFS T = new 그래프최단거리BFS();
        n=6;//최대 노드
        ch=new int[n+1];
        dis=new int[n+1];
        int[] aArr= {1,1,2,2,3,4,4,6,6};
        int[] bArr= {3,4,1,5,4,5,6,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        T.BFS2(1);
        for(int i=1; i<=n; i++){
            System.out.println(i+" : "+dis[i]);
        }
        System.out.println(Arrays.toString(dis));
    }   
}

결과

1 : 0
2 : 3
3 : 1
4 : 1
5 : 2
6 : 2
[0, 0, 3, 1, 1, 2, 2]

시작 정점에서 각 정점으로 가는 최소 횟수

간선 시각화

ch체크를 적용한 상태 트리, 각 레벨 별 횡단은 Q에 저장된 노드다.

브레이크 포인트를 지정하고 디버깅 해보면, 확실히 알 수 있다.

코드

import java.util.*;

class 경로탐색인접리스트 {
    static int n, m, answer=0;
    static List<List<Integer>> graph = new ArrayList<List<Integer>>();
    static int[] ch;
    static Stack<Integer> s = new Stack<Integer>();
    
    public void DFS2(int v){
        if(v == n) {
            System.out.println(s);
            answer++;
        } else {
            for(Integer nx : graph.get(v)) {
                if(ch[nx]==0) {//첫방문
                    ch[nx] = 1;//방문함
                    s.push(nx);//로그용
                    DFS2(nx);
                    s.pop();
                    ch[nx] = 0;
                }
            }
        }
    }
    
    
    public static void main(String[] args){
        경로탐색인접리스트 T = new 경로탐색인접리스트();
        n=5; // 목표 목적지 노드
        ch=new int[n+1];
        // aArr와 bArr를 조합
        // 1->2  , 1->3  , 1->4 이렇게 내가 갈 경로 배열
        int[] aArr= {1,1,1,2,2,2,3,4,4};
        int[] bArr= {2,3,4,1,3,5,4,2,5};
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i=0; i<bArr.length; i++){
            int a= aArr[i];
            int b= bArr[i];
            graph.get(a).add(b);
        }
        ch[1]=1;
        s.push(1);
        T.DFS2(1);
        System.out.println(answer);
    }   
}

결과

[1, 2, 3, 4, 5]
[1, 2, 5]
[1, 3, 4, 2, 5]
[1, 3, 4, 5]
[1, 4, 2, 5]
[1, 4, 5]
6

간선 정보 시각화

List<List<Integer>>  는 리스트 속에 리스트이다. 배열로 치환하면 int[][] 와 같은 2차원 배열 형태다.

ArrayList를 사용한 이유는 크기가 가변인 배열이기 때문이다.

최대 경로좌표가 10000*10000 라면 2차원 배열을 사용하면 메모리 낭비가 심하다.

반면에 ArrayList의 경우 크기가 부족하면 현재 크기에 1.5배에 해당하는 크기 배열을 새로 생성해서 사용한다.

즉, 필요한 크기 만큼만 사용한다.

코드

import java.util.*;

class Node{ 
    int data; 
    Node lt, rt; 
    public Node(int val) { 
        data=val; 
        lt=rt=null; 
    } 
} 
  
public class Tree말단노드까지의가장짧은경로BFS{ 
    Node root; 
    
    public int BFS2(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L = 0 ;
        
        while(!Q.isEmpty()) {
            int len = Q.size();
            
            for (int i = 0; i < len; i++) {
                Node cur = Q.poll();
                if(cur.lt ==null && cur.rt == null) return L;//자식노드가 없다면 말단
                if(cur.lt != null) Q.add(cur.lt);
                if(cur.rt != null) Q.add(cur.rt);
            }
            L++;
        }
        return 0;
    } 
    
    
    public int BFS(Node root){ 
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L=0;
        while(!Q.isEmpty()){
            int len=Q.size();
            for(int i=0; i<len; i++){
                Node cur=Q.poll();
                if(cur.lt==null && cur.rt==null) return L;
                if(cur.lt!=null) Q.offer(cur.lt);
                if(cur.rt!=null) Q.offer(cur.rt);
            }
            L++;
        }
        return 0;
    } 
  
    public static void main(String args[]) { 
        Tree말단노드까지의가장짧은경로BFS tree=new Tree말단노드까지의가장짧은경로BFS(); 
        tree.root=new Node(1); 
        tree.root.lt=new Node(2); 
        tree.root.rt=new Node(3); 
        tree.root.lt.lt=new Node(4); 
        tree.root.lt.rt=new Node(5); 
        System.out.println(tree.BFS(tree.root)); 
    } 
}

결과

1

자식 노드가 없으면 당연히 말단이다. 그리고 BFS탐색 특성상 가장 먼저 발견한 것이 가장 최단 거리이므로 바로 리턴한다.

코드

import java.util.*;

class BFS송아지찾기상태트리 {
    int answer=0;
    int[] dis={1, -1, 5};
    int[] ch;
    
    Queue<Integer> Q = new LinkedList<>();
    public int BFS2(int s, int e){
        ch = new int[10001]; // 상태체크 배열
        ch[s]=1; //시작위치 방문 체크
        int L = 0;
        Q.add(s); //시작 
        
        while(!Q.isEmpty()) {
            int length = Q.size();
            for (int i = 0; i < length; i++) {
                int v = Q.poll();
                for(int move : dis) {
                    int nextV = v+ move;
                    if(nextV == e) return L+1;//목적지 찾음
                    if(0<nextV && nextV <=10000 &&ch[nextV]==0) {//ch[nextV]==0 첫방문
                        ch[nextV] =1; //이제 방문 표시
                        Q.add(nextV);
                    }
                }
            }
            L++;
        }
        return 0;
    }
    
    

    public static void main(String[] args){
        BFS송아지찾기상태트리 T = new BFS송아지찾기상태트리();
        int start = 5; // 시작 위치
        int end = 14;  // 목적지 위치
        System.out.println(T.BFS2(start, end));
    }   
}

결과

3

앞 뒤로만 갈 수있다고 가정하고, 시작 위치에서 목적지까지 최소 회수를 찾는 문제다.

1~10000은 주어진 경계값으로 무시해도 된다.

핵심은 주어진 경계값 만큼에 상태값을 측정할 배열을 만들어 내가 방문한 곳인지 아닌지를 체크하는 것이다. 10001로 생성한 것은 배열이 0부터 시작이라 보기 편하게 1부터 사용하려고 한 것

ch 배열이 중요한 이유는 재방문을 줄여 시간복잡도 개선과 무한반복을 방지하기 위함이다.

위 상태트리에선 공간 문제로 5가 왜 큐에 저장이 안됐는지만 표시했다.

끝까지 탐색한다면 위 상태 노드를 만다고 종료할 것이다.

HTTP 상태코드

• 1xx (Informational): 요청이 수신되어 처리중
• 2xx (Successful): 요청 정상 처리
• 3xx (Redirection): 요청을 완료하려면 추가 행동이 필요
• 4xx (Client Error): 클라이언트 오류, 잘못된 문법등으로 서버가 요청을 수행할 수 없음
• 5xx (Server Error): 서버 오류, 서버가 정상 요청을 처리하지 못함

큰 분류에 대한 개념만 잡고 상세 코드는 그때그때 찾아보면 된다.

3xx (Redirection)

웹브라우저는 300번대 응답 헤더에 Location이 있으면 해당하는 값 주소로 자동이동한다.(리다이렉트)

리다이렉트 관련 알아둘 개념, PRG 패턴, 캐시

4xx (Client Error)

클라이언트 오류로 크게 3가지 관점에서 보면된다.

• 문법 오류(부정확한 주소)
• 인증되지 않은 접근(로그인)
• 권한이 불충분한 접근(일반 사용자인데 관리자 페이지 접근)

5xx (Server Error)

400번대 오류랑 헛갈리면 안됨. 500번대 오류는 진짜 서버 문제인 경우에만 사용

DDNS 공격을 받아 응답을 못할 경우 500번대 에러가 될 수 있음

다른 예시로 400번대 오류랑은 다르게 똑같은 시도를 여러 번 했을 시 성공할 수도 있으면 500번대 에러는 아님

HTTP 헤더

HTTP 전송에 필요한 모든 부가정보를 담는다.

실질적인 정보는 바디

표준헤더가 엄청나게 많다.

추가로 커스텀 헤더를 정의해 사용할 수 있다.(클라이언트 단과 서버 단에서 처리할 수 있게 설정한다면)

Content-Type

HTTP 바디가 무엇인지 설명해주는 헤더

JSON인지, XML인지, text인지 등등, 미디어 타입이 무엇인지 

Referer

이전 웹 페이지 주소, 

이 헤더 정보를 토대로 유입 경로를 분석한다.

User-Agent

유저 브라우저 정보라 생각해도 된다.

이 값으로 장애가 발생한 브라우저가 무엇인지 특정할 수 있다.

HOST

이 헤더값 덕분에 (외부에 노출된) 하나의 IP를 공유하는 여러 서버를 구분할 수 있다.

Location

리다이렉션 시 이동할 주소를 알려준다.

쿠키

HTTP는 기본적으로 무상태 프로토콜이다.

쿠키는 이런 상태정보를 유지할 때 사용된다.

쿠키 사용 예시, 쇼핑몰에서 로그인 하지 않은 사용자가 장바구니에 물건을 담을때 그 정보를 유지할 때 쿠키를 사용한다.

쿠키는 초 단위로 유효시간을 정해 사용한다. 

쿠키를 삭제하는 기능은 따로 없다. 삭제하고 싶다면 서버에서 0초 쿠키를 발행하면 된다.

쿠키는 도메인 구조를 지원한다. 이 정보로 어느 경로에 이 쿠키가 유효한지 세밀하게 지정할 수 있다.