골드에그

Spring Boot 에서는 Spring 모듈들의 설정들을 자동으로 셋팅해주어 일일히 구현하지 않더라도 빠르게 사용할 수 있다.

이를 Auto-Configuration 이라고 한다. 예를 들어, 서버의 IP 나 포트 설정 정보 등을 받기 위해 클래스를 구현하고 외부 파일에서 값을 받아와 셋팅을 해야 하는데 이러한 절차를 각자 코딩하여 셋팅하면 설정 파일들도 중구난방이 되고 유지보수 하기가 불편해진다. 다행히도 Spring Boot 에서는 외부에서 값을 설정할 수 있는 방법을 통일했다.

Spring Boot 가 애플리케이션을 구동할 때 자동으로 로딩하여 참조하는 파일이 applicatioin.properties 이다.

이 application.properties 에 정의된 형식에 맞게 key 와 value 를 셋팅하면, @Value("${변수 이름}") 어노테이션으로 가져와서 사용할 수 있다. 그런데 내가 작성한 프로퍼티가 아니라 써드 파티 모듈의 프로퍼티라면 이야기가 달라진다.

모듈이기 때문에 현재 프로젝트의 application.properties 파일에 정의되어 있지도 않고, 공식 문서도 옛날 것이라면 어디서 이러한 정보를 찾아야 될까? 정답은 아래 spring-projects/spring-boot 프로젝트 github 소스코드를 직접 살펴보아야 한다.

써드 파티 모듈에서 application.properties 설정 값 찾는 방법

spring-boot/spring-boot-project/spring-boot-autoconfigure/src/main/java/org/springframework/boot/autoconfigure at main · spring-projects/spring-boot (github.com)

예를 들어, rsocket 관련 spring boot 설정 값들을 보고 싶다면, 위 github 에서 rsocket 관련 소스코드를 찾아 @ConfigurationProperties 어노테이션이 선언된 클래스를 확인하면 된다.

@ConfigurationProperties(" 속성 이름 ") 에서 첫 번째 속성을 찾고, 클래스 내부에 변수들을 콤마 뒤에 붙여 설정 값을 기입하면 된다. 이 예제에서는 @NestedConfigurationProperty 어노테이션이 추가로 붙어 있으므로 두 번째 속성을 기입해야 Server 클래스 내부의 변수들을 설정 값으로 사용할 수 있다. 사용 방법은 아래와 같다.

spring.rsocket.server.port = Integer 형식

spring.rsocket.server.address = InetAddress 형식

spring.rsocket.server.transport = RSocketServer.Transport 형식

spring.rsocket.server.mappingPath = String 형식

1. 문제요약

코딩테스트 연습 - 양과 늑대 | 프로그래머스 스쿨 (programmers.co.kr)

이진 트리에 양과 늑대가 배치되어 있다. 각 노드에 방문할 때마다 양과 늑대를 모두 모아 데리고 다닐 수 있고,

모은 양의 수보다 늑대의 수가 같거나 더 많아지면, 양이 모두 잡아먹힌다. 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아 다시 루트 노드로 돌아오려 할 때, 최대로 모을 수 있는 양의 수를 구하라.

2. 문제예제

아래 접은 글을 확인해서 트리 노드를 어떻게 방문하는지 확인하면 된다.

3. 팩트추출

Fact 1 : 최대한 양을 많이 모아야 하므로 DFS 를 생각할 수 있다. 그런데 한 번 방문했던 자식 노드도 다시 탐색해야 하므로 일반적인 DFS 알고리즘과 다르다. 2번 문제 예제를 예로 들면, 0 => 1 노드로 탐색 실패했지만, 0 => 2 방문 후 1번 노드로 다시 방문할 수 있기 때문에 DFS 경로와는 다르다. 직접 탐색 리스트를 만들어 주어야 한다. 아래 Fact 2 번에서 자세히 다룬다.

Fact 2 : 현재 노드에서 갈 수 있는 경로를 정리해보자면, 아래 자식 노드들 뿐만 아니라 형제 노드의 자식 노드까지 가능하다. (거의 완전 탐색...) 일반적인 DFS 알고리즘은 다음 탐색할 노드가 자식 노드로 고정되어 있기 때문에 형제 노드를 가지고 오려면 부모 노드로부터 받아와야 한다. 탐색 실패해서 다시 부모노드로 돌아가더라도 갈 수 있는 모든 경로를 기억해야 한다. 부모 노드로부터 자식 노드의 경로들을 받아 그 리스트를 계속해서 전달해준다면 모든 탐색이 가능하다.

"경로" 를 인자로 주고 그 경로에서 뽑아 다음 방문할 지역을 선택하면 원래 DFS 경로 중간에 다른 경로를 추가로 검색할 수 있게 되는 트릭이 생긴다.

이 예제로 설명을 해보자면, 오른쪽 트리에서 DFS 를 수행하다가 자식 노드 끝까지 마저 탐색하지 않고 왼쪽 트리로 방문한다. 이렇게 해도 정보가 꼬이지 않는 이유는 부모 노드로부터 정보를 받은 것은 재활용할 수 있기 때문이다. DFS 이기 때문에 또 트리(순환하지 않는 그래프)이기 때문에 같은 정보를 공유하는 다른 형제노드부터 탐색이 가능한 것이다. 

Fact 3 : 부모 노드에서 자식 노드들을 탐색 리스트에 넣고 그 리스트가 삭제가 되지 않고 계속 추가되므로 자신의 노드가 리스트에 계속 살아있을 수 있다. 따라서 자기 자신은 경로 리스트에서 제외해야 한다.

4. 문제전략

팩트추출에서 소개한 DFS 변형 알고리즘을 사용해서 문제를 푼다.

5. 소스코드

import java.util.*;

class Solution {
    private static int answer;
    private static final List<List<Integer>> GRAPH = new LinkedList<>();

    public int solution(int[] info, int[][] edges) {
        answer = 0;
        for (int i = 0; i < info.length; i++) {
            GRAPH.add(new LinkedList<>());
        }

        for (int[] edge : edges) {
            GRAPH.get(edge[0]).add(edge[1]);
        }

        final List<Integer> next = new LinkedList<>();
        next.add(0);

        dfs(info, next, 0, 0, 0);

        return answer;
    }

    private void dfs(int[] info, List<Integer> list, int node, int sheep, int wolf) {
        if (info[node] == 0) {
            sheep += 1;
        } else {
            wolf += 1;
        }

        if (sheep <= wolf) {
            return;
        }

        answer = Math.max(answer, sheep);

        List<Integer> next = new ArrayList<>(list);
        if (!GRAPH.get(node).isEmpty()) {
            next.addAll(GRAPH.get(node));
        }
        next.remove(Integer.valueOf(node));

        for (int n : next) {
            dfs(info, next, n, sheep, wolf);
        }
    }
}

1. 문제요약

코딩테스트 연습 - 등산코스 정하기 | 프로그래머스 스쿨 (programmers.co.kr)

출입구에서 산봉우리까지 갔다가 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다.

등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 할 때 이 intensity 가 가장 짧은 코스를 찾아라. (등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.)

2. 문제예제

등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같다.

각 경로의 가중치가 가장 큰 값이 3 이며, 이 보다 intensity가 낮은 등산코스는 없다.

3. 팩트추출

Fact 1 : Dijkstra 다이젝스트라 알고리즘처럼 항상 최단 거리를 선택한다면, 경로의 intensity 배열은 항상 단조 증가 형태이다. 이 점을 활용하면 출발점에서 산봉우리까지 갔다가 다시 출발점으로 돌아오지 않아도 된다. 출발점에서 산봉우리까지 가는 반쪽짜리 최단 경로만 찾으면 된다. 출발 경로와 회귀 경로가 틀릴 수 있을지 언정 intensity 는 같을 것이기 때문이다. 이 문제에서는 경로를 구하라고 하지 않았으므로 가능하다. => 따라서 큐에 꺼낸 위치가 산봉우리라면 탐색을 종료한다.

Fact 2 : Fact 1 과 마찬가지로 경로를 구하라고 하지는 않았으므로, 출발점에서 동시에 출발하여 intensity 배열을 수정하여도 상관이 없다. 문제에서 요구하는 정답은 산봉우리와 그 산봉우리의 intensity 이다. 그러니까 어느 출발점에서 출발하여도 도착지점의 intensity 가 최소가 되는 경로만 찾으면 된다. 따라서 우선순위 큐에 출발지점을 모두 넣어놓고 시작한다.

Fact 3 : 일반적인 Dijkstra 다이젝스트라 알고리즘과 다른 점은 각 지점의 비용을 합한 거리가 최소가 되는 경로를 찾는 것이 아니라 각 구간의 최대 비용이 최소가 되는 경로를 찾는 것이다. 따라서 아래와 같이 로직을 수정한다.

if(dist[adjNode.to] > curNode.weight + adjNode.weight){
	dist[adjNode.to] = curNode.weight + adjNode.weight;
}

↓↓↓↓↓↓

if (dist[adjNode.to] > Math.max(curNode.weight, adjNode.weight)) {
	dist[adjNode.to] = effort;
}

Fact 4 : 산봉우리까지 가는 intensity 가 같은 경로가 여러 개라면, 산봉우리의 번호가 가장 작은 것을 반환하라고 지문에서 나와있으므로 산봉우리-intensity 배열에서 최소값을 찾을 때 산봉우리 배열을 먼저 정렬해야 한다.

4. 문제전략

팩트추출에서 소개한 다이젝스트라 변형 알고리즘을 사용하면 된다.

5. 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    static class Node implements Comparable<Node> {
        int index;
        int effort;
        public Node(int index, int effort) {
            this.index = index;
            this.effort = effort;
        }
        @Override
        public int compareTo(Node o) {
            return this.effort - o.effort;
        }
    }
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] efforts;
    static int[] gatesSave, summitsSave;
    private static void initGraph(int v, int[][] data) {
        for(int i=0; i < v+1; i++){
            graph.add(new ArrayList<>());
        }
        for (int[] datum : data) {
            graph.get(datum[0]).add(new Node(datum[1], datum[2]));
            graph.get(datum[1]).add(new Node(datum[0], datum[2]));
        }
        efforts = new int[v+1];
        for (int i = 1; i < v+1; i++) {
            efforts[i] = Integer.MAX_VALUE;
        }
    }

    private static int[] dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        // 시작지점 삽입
        for (int gate : gatesSave) {
            pq.offer(new Node(gate, 0));
            efforts[gate] = 0;
        }

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isSummit(curNode.index))
                continue;
            if (efforts[curNode.index] < curNode.effort) {
                continue;
            }
            for (Node adjNode : graph.get(curNode.index)) {
                int effort = (adjNode.effort == Integer.MAX_VALUE) ? curNode.effort : Math.max(curNode.effort, adjNode.effort);
                if (efforts[adjNode.index] > effort) {
                    efforts[adjNode.index] = effort;
                    pq.offer(new Node(adjNode.index, efforts[adjNode.index]));
                }
            }
        }

        Arrays.sort(summitsSave);
        int index = -1;
        int minEffort = Integer.MAX_VALUE;
        for (int summit : summitsSave) {
            if (efforts[summit] < minEffort) {
                minEffort = efforts[summit];
                index = summit;
            }
        }
        return new int[]{index, minEffort};
    }

    private static boolean isSummit(int num) {
        for (int summit : summitsSave) {
            if (num == summit) return true;
        }
        return false;
    }

    public static int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        gatesSave = gates;
        summitsSave = summits;
        initGraph(n, paths);
        return dijkstra();
    }
}

[문제]

[원인]

Resolve | 웹팩 (webpack.kr) resolve 부분을 살펴보면 아래와 같은 문구가 보인다.

node.js 의 핵심모듈들을 Webpack 5 부터 포함하고 있지 않는다. 직접 에러가 나는 모듈을 설치하고 resolve fallback 에 추가해야 한다.

참고로, CRA(Create React App) 로 만든 React 의 경우, Webpack 설정파일이 숨겨져 있어 덮어 씌워야 한다. 그럴 바에는 React 와 Webpack, Babel, TypeScript 를 직접 설정하여 구축하는 것이 더 나을 수도 있다. 아래 방법은 CRA 없이 React 구축한 상태에서 해결한 방법이다.

[해결방법]

(1) npm install buffer 로 buffer 모듈 설치

(2) webpack.config.js 파일에서 아래 문구 삽입

  plugins: [
  ...
    new webpack.ProvidePlugin({
      Buffer: ['buffer', 'Buffer'],
    }),
  ...
  ]

plugins 에 buffer 플러그인 추가

  resolve: {
  ...
    fallback: {
      buffer: require.resolve('buffer'),
    },
  ...  
  },

resolve 에 buffer fallback 추가

Reactor 는 Reactive Streams 의 구현체이다.

백 프레셔가 가능한 PUB/SUB 모델로 싱글 스레드에서 이벤트 처리를 하는 이벤트 처리 프로세스이다.

( 여담이지만, NodeJS 따라하는 것처럼 보이지만 사실 Spring 진영에서 먼저 나왔다고 한다. 관심이 없었을 뿐 )

Reactor 를 이해하려면 Reactive Streams 의 PUB/SUB 모델의 디자인 패턴을 살펴보아야 한다.

Application 에서 Publisher 객체와 Subscriber 객체를 생성하고 Publisher.subscribe 메서드를 호출한다.

Publisher 에서는 생성된 데이터를 포장하여 Subscription 객체를 생성하고, subscribe 메서드에서 전달받은 Subscriber 의 onSubscribe 메서드를 호출하여 생성된 Subscription 객체를 인자로 넘긴다. Publisher 역할은 여기서 끝이다.

한 마디로 Publisher 는 정보를 생성하여 포장하고 그것을 구독자와 연결시켜주는 중매자이다.

onSubScribe 메서드에서는 인자로 넘어온 Subscription 의 request 를 호출하여 데이터들을 요청된 크기만큼 가져온다.

(백 프레셔 기능이다.) 요청된 크기만큼 데이터를 넘겨줄 때까지 데이터들을 하나씩 SubScriber 의 onNext 메서드를 호 출하고 다 넘겨주었다면 onComplete 메서드를 호출한다. 자세한 내용은 아래 동영상을 참고하자.

1. 문제요약

11658번: 구간 합 구하기 3 (acmicpc.net)

N×N 크기의 표에 숫자들이 채워져 있다. 수의 변경이 빈번히 일어나고 연속 구간에 대한 부분합을 구하려고 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 비슷한 문제인 10999번: 구간 합 구하기 2 (acmicpc.net) 와 다른 부분은 2차원 배열에서 수정 및 조회하며 구간 업데이트가 아니라 한 곳만 업데이트한다는 점이다. 연속된 공간의 연산이므로 세그먼트 트리와 펜윅 트리 모두 가능하다. 펜윅 트리에 대한 자세한 내용은 아래 블로그 글을 참고한다.

펜윅 트리 (바이너리 인덱스 트리) (acmicpc.net)

Fact 2 : 펜윅 트리를 2차원 배열에 적용하면 행과 열 모두 값이 업데이트된다. 맵 전체에 그 해당 인덱스가 필요하는 구간들이 업데이트된다. 예를 들어 map[0][0] 에 해당하는 부분이 펜윅 트리 맵에 저장될 때 다음과 같다.

map[0][0] 이 펜윅트리 tree[x][y] 에 저장될 때의 모습이다. 0 번째 인덱스이기 때문에 0번, 1번, 3번 인덱스 구간합에 모두 저장되는 것을 볼 수 있다.

4. 문제풀이(수동)

문제 예제 입력 1번 map 을 펜윅 트리(tree)에 저장하면 아래와 같다.

여기서 만약 (2, 2) 부터 (3, 4) 까지 구간합을 구하고 싶다면 아래 공식과 같이 전체 사각형에서 변두리 사각형 부분들을 빼주면 된다. 이 때 중복으로 제거한 부분을 다시 한 번 더해주어야 한다.

sum(3, 4) - sum(3, 2-1) - sum(2-1, 4) + sum(2-1, 2-1)

= 27

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 펜윅 트리방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] inputArray;
    static int[][] fenwickTree;

    private static void update(int x, int y, int val) {
        while(x <= N){
            int yIndex = y;
            while(yIndex <= N) {
                fenwickTree[x][yIndex] += val;
                yIndex += yIndex & -yIndex;
            }
            x += x & -x;
        }
    }

    private static int sum(int x, int y) {
        int result = 0;
        while(x > 0){
            int yIndex = y;
            while(yIndex > 0) {
                result += fenwickTree[x][yIndex];
                yIndex -= yIndex & -yIndex;
            }
            x -= x & -x;
        }
        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        inputArray = new int[N+1][N+1];
        fenwickTree = new int[N+1][N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                inputArray[i][j] = Integer.parseInt(st.nextToken());
                update(i, j, inputArray[i][j]);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            if(operation == 1) {
                int x2 = Integer.parseInt(st.nextToken());
                int y2 = Integer.parseInt(st.nextToken());
                sb.append((sum(x2, y2) - sum(x2, y1-1) - sum(x1-1, y2) + sum(x1-1,y1-1))+"\n");
            }else {
                int change = Integer.parseInt(st.nextToken());
                update(x1, y1, change - inputArray[x1][y1]);
                inputArray[x1][y1] = change;
            }
        }
        System.out.println(sb.toString());
    }
}

1. 문제요약

1520번: 내리막 길 (acmicpc.net)

지도의 각 칸에는 그 지점의 높이가 주어지며 (0, 0) 지점에서 (n-1, m-1) 지점으로 내려가려고 한다. 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 할 때 이동할 수 있는 경로의 수를 구하시오.

2. 문제예제

3. 팩트추출

Fact 1 : 전형적인 BFS 와 DFS 문제인 것처럼 보이지만, 입력의 범위를 보면 완전 탐색 시 시간 초과가 발생할 수 있다. 최대 칸 수가 500 * 500 으로 250000 이며 상하좌우 4방향으로 움직일 수 있으니 4 의 250000 제곱 경우의 수가 존재한다. 경우의 수를 줄일 수 있는 방법을 찾아야 한다.
 

Fact 2 : 문제 예제를 살펴보면 전체 문제의 답이 작은 부분 문제의 답의 합으로 구성되어 있다. 50 번 지점에서 목적지까지 가는 경로의 수는 45번 지점에서 가는 경로의 수 + 35번 지점에서 가는 경로의 수로 이루어져 있다. 35번 지점이나 30번 지점, 27번 지점은 경로의 수가 하나로 나중에 이 지점을 방문하더라도 계산할 필요가 없다. 즉 DP 문제이다.

Fact 3 : 기존 DFS 나 BFS 에서 사용하던 visited 배열을 응용하여 "해당 지점에서 목적지까지 가는 경로의 수" 로 생각하여 해당 값을 재활용하면 탐색 범위를 줄일 수 있다. 여기서 중요한 점은 DFS 와 BFS 의 visited 배열 활용도가 조금 다르다는 것이다. BFS 는 주변부터 탐색하기 때문에 단순 방문했는지 여부만 파악할 수 있지만 DFS 는 한 가지 경우의 수부터 모두 탐색하고 다시 원래 위치로 돌아오기 때문에 수행 도중 visited 배열을 오염시킨다면 그 경로는 다시 탐색하지 않아도 된다. 4 번 문제 풀이 (수동) 부분에서 자세히 확인한다.

Fact 4 : DP[x][y] 배열을 0 으로 초기화하면 이 경로의 수가 0 인지 노드를 방문하지 않은 것인지 확인이 불가능하다. DP 배열이 visited 배열의 역할도 하기 때문에 -1 로 초기화한다.

4. 문제풀이(수동)

문제 예제 입력 1을 DFS 알고리즘 + DP 방식으로 문제를 풀었을 때 애니메이션이다.

손수 애니메이션으로 만들어준 우투리와툴툴 티스토리 블로그님께 감사의 말씀을 전한다. 덕분에 이해하기가 쉽다.

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. DFS + DP 방식으로 문제를 풀었다.

6. 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int M, N;
    static int[][] map;
    static int[][] dp;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        dp = new int[M][N];

        for(int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                map[j][i] = Integer.parseInt(st.nextToken());
            }
        }
        initDP();
        System.out.println(dfs(0, 0));
    }
    private static void initDP() {
        for(int j = 0; j < M; j++) {
            for (int i = 0; i < N; i++) {
                dp[j][i] = -1;
            }
        }
    }
    private static int dfs(int x, int y) {
        if(x == M-1 && y == N-1){ return 1; }
        if(dp[x][y] != -1) return dp[x][y];

        dp[x][y] = 0;
        for (int i=0; i<4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX < 0 || newX >= M || newY < 0 || newY >= N) continue;
            if (map[x][y] <= map[newX][newY]) continue;

            dp[x][y] += dfs(newX, newY);
        }
        return dp[x][y];
    }
}