풀이

아이디어

간단하게 BFS로 풀 수 있는 문제라고 생각합니다.

하지만 다른 풀이로 데이크스트라로 문제를 풀어보도록 해보겠습니다.

가장 맨 처음에 있는 위치 N을 기준으로 -1, +1 로 가는 경우의 가중치는 1입니다. 두배로 가는 경우의 가중치는 0입니다.

이것을 기분으로 문제를 풀어봅시다.

(N,0)을 우선순위 큐에 넣습니다.

이제 (N-1, 1), (N+1, 1), (2 * N, 0)을 큐에 넣습니다.

다만 다익스트라이기 때문에 거리가 갱신된 경우만 큐에 넣습니다!

그렇게 해서 모든 노드들간의 최소 거리를 구했다면 이제 K 노드로 가는 최소 거리를 구해주면 문제를 해결합니다.

상세 구현

다익스트라 문제를 풀기 위해서는 거리 배열, 우선순위 큐가 필요합니다!

각 노드에 대한 거리를 기록하기 위하여 배열을 최댓값으로 초기화하여 선언합니다.

        dist = new int[100_001];
        Arrays.fill(dist, 100_000);
        // 시작점의 거리는 0
        dist[N] = 0;

이제 우선순위큐를 선언하고 거기에 N을 넣어줍니다.

        PriorityQueue<Node13549> pq = new PriorityQueue<>();
        pq.add(new Node13549(N, 0));

이제 3가지 경우(+1, -1, *2)에 대해서 가장 최소로 가는 길을 탐색합니다.

        while(!pq.isEmpty()) {
            Node13549 cur = pq.poll();

            if(dist[cur.idx] < cur.dist)
                continue;

            if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
                dist[cur.idx - 1] = cur.dist + 1;
                pq.add(new Node13549(cur.idx-1, cur.dist + 1));
            }

            if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
                dist[cur.idx + 1] = cur.dist + 1;
                pq.add(new Node13549(cur.idx+1, cur.dist + 1));
            }

            if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
                dist[cur.idx * 2] = cur.dist;
                pq.add(new Node13549(cur.idx*2, cur.dist));
            }
        }

이를 통해 우리는 원하는 답인 dist[K]를 구할 수 있습니다.

코드

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

public class No13549 {
    static int N, K;
    static int[] dist;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void pro() {
        dijkstra();
        System.out.println(dist[K]);
    }

    private static void dijkstra() {
        dist = new int[100_001];
        Arrays.fill(dist, 100_000);
        dist[N] = 0;

        PriorityQueue<Node13549> pq = new PriorityQueue<>();

        pq.add(new Node13549(N, 0));

        while(!pq.isEmpty()) {
            Node13549 cur = pq.poll();

            if(dist[cur.idx] < cur.dist)
                continue;

            if(cur.idx - 1 >= 0 && dist[cur.idx-1] > cur.dist + 1) {
                dist[cur.idx - 1] = cur.dist + 1;
                pq.add(new Node13549(cur.idx-1, cur.dist + 1));
            }

            if(cur.idx + 1 <= 100_000 && dist[cur.idx + 1] > cur.dist + 1) {
                dist[cur.idx + 1] = cur.dist + 1;
                pq.add(new Node13549(cur.idx+1, cur.dist + 1));
            }

            if(cur.idx * 2 <= 100_000 && dist[cur.idx * 2] > cur.dist) {
                dist[cur.idx * 2] = cur.dist;
                pq.add(new Node13549(cur.idx*2, cur.dist));
            }
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        br.close();
    }
}
class Node13549 implements Comparable<Node13549> {
    int idx;
    int dist;

    public Node13549(int idx, int dist) {
        this.idx = idx;
        this.dist = dist;
    }

    @Override
    public int compareTo(Node13549 o) {
        return this.dist - o.dist;
    }
}

작년 11월 부터 새로 아이디를 만들었는데 드디어 300솔을 달성 하였습니다!

연속 문제 풀이는 143일 유지 중인데 딱 오늘이 이 아이디를 만든지 150일 되는 날이네요

150일 동안 정말 열심히 알고리즘 역량을 강화하였습니다.

그 과정에서의 회고와 앞으로의 계획에 대해서 여기에 이야기 해보겠습니다.

아이디를 새로 판 이유

사실 백준 아이디는 컴공 4학년 때부터 만들어서 계속 알고리즘을 하고 있었습니다. 방법도 모른채 주먹구구식으로 풀어가며 오랜 기간 동안 문제를 푼 결과 플레5를 달성하였습니다.

하지만 저의 실력은 진짜 플레5였을까요? 제가 푼 문제를 다시 풀라고 하면 막히는 것을 느꼈습니다.

분명 풀었던 문제인데? 왜 기억이 안나지? 아 이거 쉽게 풀었는데?

이런 문제가 계속 발생하였습니다. 이러한 문제의 원인은 다음과 같습니다.

답지를 참고하지만 오답노트를 사용 안 함

문제를 풀다가 막히게 될 경우 답지를 보고 문제를 풀었습니다. 답지를 한 번 보고 답지를 안 보고 다시 풀어보는 방식으로 백준 문제들을 풀었습니다. 하지만 시간이 지나면서 이걸 회고하거나 다시 풀어보지 않아 제 지식으로 만들지 못했습니다.

알고리즘 이론 벼락치기

막히는 문제에 대해서 백준 하단의 알고리즘을 보고 알고리즘 이론 관련 자료들을 봤습니다. 문제는 이 알고리즘에 대한 이론을 공부하지 않고 그냥 넘어갔다는 것입니다. 알고리즘을 충분히 이해하는 것이 아닌 그냥 아 이런거 구나 하고 문제에 푸는데 급급했습니다.

그렇기에 다른 응용 문제에서도 이러한 문제들이 계속 반복 되었습니다.

이러한 이유로 저는 플레를 달았지만 제 진짜 실력이 아닌 위장 티어를 달게 되었습니다.

다시 시작, 알고리즘 역량 강화!

코딩 테스트 문제에서 몇 번 떨어지자 저의 심각성을 알게 되었고 이를 해결하기 위하여 '류호석님의 알고리즘 특강'을 수강하고 '23 동계 삼성 전자 DX 알고리즘 특강'을 신청하여 수업을 들었습니다. 또한 알고리즘 스터디에 참가하여 매일 2문제를 풀이하였습니다.

덕분에 알고리즘 역량이 강화되었습니다. 만약 알고리즘 공부를 하시는 분들이 계신다면 이러한 알고리즘 스터디나 교육을 듣는 것을 추천드립니다.

앞으로는 어떻게 할 것인가?

오답노트 다시 쓰기

삼성 전자 DX 알고리즘 특강을 하면서 잠시 멈춰두었던 오답노트를 적을 예정입니다.

150일 동안 많은 문제를 풀면서 많이 막히거나 어려워했던 문제들이 있습니다. 이런 문제들을 하나하나 다시 풀어가면서 오답노트를 적어서 블로그에 포스트하여 기본기를 다질 것입니다.

목표 블로그에 요번 년도 까지 100문제를 기록하겠습니다!

편식하지 않기

기출문제들에 대해서 집중을 하였더니 이렇게 편향된 그림이 그려졌습니다. 이에 대해서 반성하며 좀 더 여러 문제를 풀도록 하겠습니다.

목표

다음 뱃지들은 얼마나 문제를 균등하게 풀었는지에 대한 뱃지들입니다. 6월 전까지 균형의 수호자 골드 x8을 획득하겠습니다.

알고리즘 이론 강화

알고리즘 강의를 한번 보고 그 내용들을 정리하였지만 이걸 다시 설명하면서 진짜 나의 실력을 쌓아야한다고 생각합니다. 블로그에 그 내용들을 포스트하며 공부를 하겠습니다.

마무리

150일 동안 300솔 1일 2코딩을 하였군요. 앞으로도 계속 노력하여 500일에는 1000솔을 달성하겠습니다! 화이팅!

풀이

아이디어

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

이 말을 쉽게 생각해보자. 자신의 키를 알 수 있는 경우는 무엇일까? 자신에 앞에 얼마나 있는지 그리고 자신의 뒤에 얼마나 있는지를 아는 사람이 자신이 몇 번째 인지 알것이다!

즉 내가 가거나 나한테 오는 노드들의 수들의 합이 N-1이면 되는 것이다.

만약 갈 수 없는 노드가 나한테 올 수 없다면 그 노드와의 우위를 정할 수 없게 되기 때문에 순위를 알 수 없게 된다.

이 문제를 플로이드 워샬 문제로 해결해보자

상세구현

노드가 다른 노드에 갈 수 있다면 몇 번째로 가는지를 적도록 하였습니다.

그리고 만약 나한테 오는 노드라면 0으로 기록하도록 하였습니다.

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            mat[a][b] = 1;
            mat[b][a] = 0;
        }

입력시 코드로 다음과 같이 나보다 몇명 거쳐서 갈 수 있는지를 적습니다. 그리고 반대의 경우는 0으로 기록!

이제 갈 수 있는 모든 경우와 받는 경우를 기록하기 위해 플로이드 워샬을 사용해봅시다.

        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(mat[i][j]==0 || mat[i][k]==0 || mat[k][j]==0)
                        continue;
                    if(mat[i][j] > mat[i][k] + mat[k][j]) {
                        mat[i][j] = mat[i][k] + mat[k][j];
                        mat[j][i] = 0;
                    }
                }
            }
        }

이를 통해서 우리가 갈 수 있는 경우들을 모두 찾아보고 만약 올 수 있는 경우는 0으로 명시하였습니다.

다음과 같이 입력에 대하여 갈수 있는 경우와 오는 경우를 체크 하였습니다.

501을 최댓값으로 계산하였기에 mat[i][j]가 501인 경우는 i에서 j를 비교하여 우위를 알 수 없음을 보여줍니다.

int count = 0;
        for(int i=1; i<=N; i++) {
            boolean check = true;
            for(int j=1; j<=N; j++) {
                if(mat[i][j]==501) {
                    check = false;
                    break;
                }
            }
            if(check)
                count++;
        }

이를 통해 노드들에 어느 정도로 갈 수 있는지를 기록 할 수 있습니다.

문제 해결!

코드

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

public class No2458 {
    static int N;
    static int[][] mat;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void pro() {
        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(mat[i][j]==0 || mat[i][k]==0 || mat[k][j]==0)
                        continue;
                    if(mat[i][j] > mat[i][k] + mat[k][j]) {
                        mat[i][j] = mat[i][k] + mat[k][j];
                        mat[j][i] = 0;
                    }
                }
            }
        }

        int count = 0;
        for(int i=1; i<=N; i++) {
            boolean check = true;
            for(int j=1; j<=N; j++) {
                if(mat[i][j]==501) {
                    check = false;
                    break;
                }
            }
            if(check)
                count++;
        }
        System.out.println(count);
    }
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        mat = new int[N + 1][N + 1];

        for(int i=1; i<=N; i++) {
            Arrays.fill(mat[i], 501);
            mat[i][i] = 0;
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            mat[a][b] = 1;
            mat[b][a] = 0;
        }

        br.close();        
    }
}    

스프링 웹 개발 기초

정적 컨텐츠

실제 수강 날짜 : 23-04-10

정적 컨텐츠란 무엇인가? 움직이지 않는 정적인 내용? 해석하면 이런 의미를 가지고 있는데 맞습니다! 정적 컨텐츠는 변화가 없는 파일 자체를 넘겨주는 방식입니다.

저번 예제와 같이 Welcome 화면 처럼 index.html을 그대로 파일로 넘겨주는 것을 정적 컨텐츠라고 합니다.

이러한 HTML 파일, 이미지 파일 자체를 건네주는 방식이고 클라이언트들은 그 파일들을 브라우저를 통해 보는데요.

스프링 부트는 정적 컨텐츠를 기본 지원! 스프링 부트는 기본적으로 이러한 정적 컨텐츠를 지원하고 있습니다. 그래서 우리는 /static 폴더에 html 파일을 올려 간단하게 Welcome 페이지를 작성할 수 있었습니다!

static으로 올라온 파일들은 spring이 올라가면서 자동으로 서버에 올라가게 됩니다!

어떻게 동작할까요?

1. 정적 파일을 요구하는 요청이 들어옵니다.
2. 스프링 컨트롤러에서 이것을 처리할 컨트롤러 여부를 확인합니다.
3. 처리하는 컨트롤러가 없다면 정적 파일로 가서 해당하는 html 파일이 있는지 확인합니다.
4. 그것을 클라이언트에게 넘겨줍니다.

정적 컨텐츠의 문제점 정적 컨텐츠는 요구사항이 오면 그에 해당하는 파일을 넘겨주는 방식으로 매우 단순합니다. 하지만 웹에서는 이런 단순한 것 보다는 복잡한 내용이 필요로 합니다.

오늘의 주식 상황에 대해서 알려주는 사이트가 있다고 해봅시다. 이러한 주식 상황은 매일 매 시간 마다 바뀔건데데 이를 정적 컨텐츠로 표현한다면 어떻게 될까요?
프로그래머는 바뀌는 순간마다 새로운 파일을 만들어서 건네줘야하는 문제가 발생합니다!
생각만해도 할일이 많군요! 기본적인 틀은 유지하고 값이 바뀌면 바뀐 부분만 동적으로 바뀌게 할 수는 없을까요?
그래서 탄생한 것이 바로 동적 컨텐츠입니다!

MVC와 템플릿 엔진

실제 수강 날짜 : 23-04-10

MVC란? M : Model V : View C : Controller

MVC는 설계 패턴입니다!

기존 JSP에서는 뷰에서 모든 것을 해결하려고 하였는데 이러한 방식을 "모델 1방식"이라고 하는데요.

모델 1방식은 코드의 역할이 구분되지 않아 코드를 이해하기 위해서 전체 코드를 보고 탐색해야 했습니다. => 유지보수성이 떨어지겠죠.

에러 발생 했는데 이게 어디서 문제일까 하고 찾으면 마치 놀이터에서 보물 찾기를 하듯이 코드를 봐야 할 겁니다.

이러한 방식을 없애기 위해 "모델 2방식"이 탄생하였습니다.

이 방식으로 우리는 화면, 컨트롤러, 데이터가 분리가 되었습니다.

이제 우리는 각 기능 별로 집중할 수 있게 되었습니다. 이를 통해서 기본적인 화면을 뷰에 정의하고 데이터들을 모델과 컨트롤러에서 관리하여 뷰에 넘겨줄 수 있게 되었습니다!

어떻게 동작할까요?

1. 요청이 들어옵니다
2. 요청을 스프링에서 해당하는 컨테이너가 있는지를 확인합니다.
3. 동적 컨텐츠는 이를 다루는 컨테이너가 있기에 컨테이너가 처리합니다.
4. 모델에 데이터를 key와 value로 묶어서 viewResolver에 넘겨줍니다.
5. 템플릿 엔진이 이것을 랜더링 해서 HTML 변환을 해서 넘겨줍니다!

템플릿 엔진이란 무엇인가?

템플릿 양식과 특정 데이터 모델에 따른 입력자료를 합성하여 결과 문서를 출력하는 소프트웨어 및 컴포넌트를 템플릿 엔진이라고 합니다.

위의 모델로 넘겨진 데이터와 templates에 있는 view를 합성하여 결과 HTML 문서를 변환하여 넘겨주는 역할을 템플릿 엔진에서 해주는 것입니다.

동적 컨텐츠의 부족한점

이제 우리는 실시간 주식들이 바뀌면 그 주식들이 바뀐 값들이 저장된 데이터를 참고하여 화면에 계속 바뀌어서 건네줄 수 있게 되었습니다!
근데 우리가 이러한 실시간 주식 데이터를 너무 잘 만들어서 만약 다른 사람들이 이 데이터를 사용하고 싶어하는데 어떻게 해야할까요?
데이터만 건네줄 수는 없을까요? 이런 부분을 해결하기 위한 것이 바로 API입니다.

API

실제 수강 날짜 : 23-04-10

API란 무엇인가? Application Programming Interface

API는 통신에 대한 응답으로 문자를 보내주는 방식입니다!

여태까지는 화면과 관련된 정보들을 보냈지만 이제는 데이터만 건네주는 방식으로 한거죠

보내지는 문자의 형식을 "데이터 포멧"이라고 하고 이러한 데이터 포멧은 문자열, XML, JSON이 있습니다.

현재 많은 사람들이 사용의 편리함과 우수한 성능으로 JSON을 사용하고 있습니다!

자세한 내용은 블로그로 포스팅하였습니다. https://velog.io/@fe26min_/API%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80

API를 이용하면 API를 통해서 객체를 JSON 형식으로 반환이 가능해지는데요.

어떻게 동작할까요?

1. 요청이 들어오게 되면 스프링 컨테이너에서 해당하는 컨트롤러를 찾아갑니다.
2. ResponseBody 어노테이션을 만나면 아 이거는 HTTP 바디에 데이터를 담는 형식으로 보내주는 애구나! 라는 것을 알게 됩니다.
3. 이를 HttpMessageConverter에게 넘겨주면 해당하는 형태에 맞춰서 응답 Body에 값을 담아서 보내주게 됩니다!

기본 정책은 JSON으로 보내는 방식이지만 설정을 통해서 다른 방식으로 보내줄 수 있습니다!

요약

우리가 요청에 대해서 응답하는 방식은 3가지로 구분됩니다. 그냥 파일을 그대로 보내주는 정적 컨텐츠, 템플릿 엔진을 통해 파일을 가공하여 그것을 보내주는 동적 컨텐츠, HTTP BODY에 데이터를 담아서 보내주는 API 이렇게 3가지 방식이 있습니다.

풀이

아이디어

다음 순열을 주어진 수 보다 큰 수입니다.

규칙을 한 번 찾아 봅시다.

1, 2, 3은 1, 3, 2로 바뀝니다. 2와 3의 위치가 바뀌었네요

1, 3, 2는 2, 1, 3으로 바뀝니다.

2, 1, 3은 2, 3, 1로 바뀝니다.

규칙을 살펴봅시다. 다음 순열과의 차이가 작기 때문에 뒤에서부터 비교하여 혹시 뒤에 있는 수가 앞의 있는 수보다 작다면 둘의 위치를 바꿔주는 것이 보여집니다.

1, 2, 3에서 2는 3보다 작았기 때문에 두 수의 위치가 바뀌면 커지겠죠

규칙 1. 앞에 있는 작은 수와 뒤에 있는 큰 수를 바꾼다.

그렇다면 1, 3, 2를 보고 규칙 1을 대입해봅시다.

뒤에서 부터 규칙 1을 봅니다. 3은 2보다 크니 넘어갑니다. 1은 3보다 작으니 바뀌어야 할 숫자를 찾았습니다. 하지만 1은 3과 2 둘 과 비교하여 작은데 무엇이랑 바꿔줘야 할까요?

답은 2랑 바꿔줘야 겠죠 2, 3, 1이 되어습니다. 하지만 2, 3, 1보다 2, 1, 3이 더 작은 수입니다. 이를 찾는 방법은 가장 뒤에 있는 1보다 큰 수를 찾으면 됩니다. 그게 가장 작은 수이기 떄문에 적게 변하는 방법입니다. 규칙 2. 뒤에 있는 수 중 앞에 있는 작은 수 보다 큰 수 중 제일 뒤에 있는 수를 바꿔줍니다.

2를 제외한 3, 1을 정렬을 해줘야 하는데 방법은 간단합니다. 뒤집어 주면 됩니다.

?? 왜 뒤집으면 되나요?? 1, 3, 2에서 1이 바뀌어야 되는 수가 되었다는 것은 1에 도달하기 전까지 숫자들이 감소하는 모습이었습니다.(내림차순)

이제 바뀌는 수가 바뀌었기 때문에 그 수 이후로는 가장 작은 수가 와야 합니다. 가장 작은 수는 결국 오름차순인데 그렇다면 내림차순을 반대로 뒤집으면 문제는 해결이 됩니다.

규칙 3. 바뀐 수 뒤로는 뒤집어서 내림 차순을 오름 차순으로 만들기

이 아이디어를 통해서 문제를 풀어보자!

실제 구현

규칙 1. 앞에 있는 작은 수와 뒤에 있는 큰 수를 바꾼다.

        // 규칙 1. 앞에가 뒤에 보다 작은 수 찾기
        int i = N-1;

        while(i>0 && arr[i-1] > arr[i])
            i--;
        // i가 0이라면 모든 배열이 내림차순이다.
        // 즉 배열 중에 가장 큰 수이다.
        if(i==0)
            return false;

규칙 2. 뒤에 있는 수 중 앞에 있는 작은 수 보다 큰 수 중 제일 뒤에 있는 수를 바꿔줍니다.

        int j = N-1;

        // 규칙 2 arr[i-1]보다 큰 수 중에 가장 뒤에 있는 수(가장 작은 수)를 찾기
        while(arr[j] <= arr[i-1]) {
            j--;
        }
        swap(i-1, j);

규칙 3. 바뀐 수 뒤로는 뒤집어서 내림 차순을 오름 차순으로 만들기

        // 규칙 3. 내림차순으로 가장 큰 수이기 때문에 오른차순으로 가장 작은 수로 바꾸기
        j = N-1;
        while(i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;

코드

package ThisWeek38;

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

public class No10972 {
    static int N;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void pro() {
        StringBuilder sb = new StringBuilder();
        if(check()) {
            for(int i : arr) {
                sb.append(i + " ");
            }
        }
        else
            sb.append(-1);
        System.out.println(sb);
    }

    private static boolean check() {
        // 규칙 1. 앞에가 뒤에 보다 작은 수 찾기
        int i = N-1;

        while(i>0 && arr[i-1] > arr[i])
            i--;
        // i가 0이라면 모든 배열이 내림차순이다.
        // 즉 배열 중에 가장 큰 수이다.
        if(i==0)
            return false;

        int j = N-1;

        // 규칙 2 arr[i-1]보다 큰 수 중에 가장 뒤에 있는 수(가장 작은 수)를 찾기
        while(arr[j] <= arr[i-1]) {
            j--;
        }
        swap(i-1, j);

        // 규칙 3. 내림차순으로 가장 큰 수이기 때문에 오른차순으로 가장 작은 수로 바꾸기
        j = N-1;
        while(i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }

    private static void swap(int j, int i) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        br.close();        
    }
}

강의 소개

강의 소개

실제 수강 날짜 : 23-04-10

강의의 목표

이 강의의 목표는 MVC 패턴과 실무적인 스프링부트 기술을 경험해보는 것입니다. 간단한 웹 애플리케이션을 개발하고 기초부터 차근 차근 하는 것이 목표입니다!

프로젝트 사용기술: Spring Boot, JPA, Tomcat, Gradle, HIBERNATE, Thymeleaf

이 스프링 입문이라는 강의를 통해서 내가 어느 정도 스프링에 대해 알고 있는지를 알아보자!

프로젝트 환경설정

프로젝트 생성

실제 수강 날짜 : 23-04-10

statr.spring.io

스프링 프로젝트를 처음 생성을 도와주는 사이트인 https://start.spring.io/가 있습니다. 이를 통해서 우리는 환경 설정을 간단하게 할 수 있습니다.

Gradle, Maven 설정, 언어 설정, 스프링 부트 버전, 등등

이 사이트를 사용하지 않는다면 스프링 부트와 맞는 디펜던시를 일일이 찾아서 넣어줘야 합니다.

디펜던시 추가

이제 실습을 위해서 디펜던시를 넣어줍니다!

여기서 추가되는 디펜던시들은 Spring에서 권장하는 그리고 선택한 스프링 부트의 버전과 맞는 디펜던시들입니다.

디펜던시 목록

• Spring Web : Spring Web provides integration features such as multipart file upload functionality and the initialization of the IoC container using Servlet listeners and a web-oriented application context. It also contains an HTTP client and the web-related parts of Spring remote support. Build web, including RESTful, applications using Spring MVC. Uses Apache Tomcat as the default embedded container.

• Thymeleaf : HTML을 만들어주는 템플릿 엔진, 템플릿 엔진은 템플릿 양식과 특정 데이터 모델에 따른 입력 자료를 합성하여 결과 문서를 출력하는 소프트웨어 또는 소프트웨어 컴포넌트를 말한다.

디펜던시란? 디펜던시 인젝션으로 우리에게 익숙한 디펜던시는 의존성이라는 뜻을 가지고 있습니다. 의존성은 어느 객체가 다른 객체에 의존하고 있는 것을 의미합니다. 여기서의 디펜던시는 외부 라이브러리라는 의미로 사용됩니다.

이렇게 설정한 프로젝트를 이제 Generate를 통해서 생성합니다. 생성된 프로젝트는 곧바로 실행할 수 있습니다.

프로젝트 보기

프로젝트를 이제 살펴봅시다. 프로젝트는 진행하는데 필요한 것들이 설정되어 있습니다.

다음과 같이 프로젝트들이 설정되었습니다.

main에는 서버 관련된 Java코드들이 있습니다. test에는 테스트 관련 코드가 들어있습니다. => 공식에서 권장할 만큼 TDD가 중요하다는 것을 알수 있습니다.

resources에는 프로젝트에 필요한 파일들을 넣어두는 곳입니다.

이제 build.gradle을 한 번 보겠습니다.

plugins {
    id 'java'
    id 'org.springframework.boot' version '3.0.5'
    id 'io.spring.dependency-management' version '1.1.0'
}

group = 'helllo'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = '17'

repositories {
    mavenCentral()
}

dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-thymeleaf'
    implementation 'org.springframework.boot:spring-boot-starter-web'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'
}

tasks.named('test') {
    useJUnitPlatform()
}

이 build.gradle은 설정 파일입니다. dependencies를 보면 우리가 설치한 외부 라이브러리들이 담겨 있는 것을 알 수 있습니다.

여기서 특이한 점이 있다. 우리가 설치한 라이브러리는 2개였는데 testImplementaion이라는 테스트 관련 라이브러리가 들어있음을 확인할 수 있습니다. 이는 스프링에서 기본적으로 Junit5를 내장하여 TDD를 권장하는 것입니다

여기 dependencies에 적은 라이브러리들은 mavenCentral을 통해서 다운로드가 됩니다.

프로젝트 실행

이제 설치된 프로젝트를 실행해봅시다.

다음과 같이 정상 작동을 확인 할 수 있습니다.

프로젝트가 실행이 되면 어떤 일이 벌어질까요? SpringApplication.run 메서드가 실행됩니다.

이때 SpringBootApplication 어노테이션이 실행이 되면 이를 띄워서 내장되어 있는 톰캣을 자체적으로 띄우면서 스프링부트가 같이 올라가게 됩니다!

이에 대해서는 좀 더 자세히 조사하여 스프링 부트 동작 시 벌어지는 일이라는 내용으로 포스트 하겠습니다.

라이브러리 살펴보기

이제 다시 build.gradle을 살펴보면 우리는 총 3개의 디펜던시가 기록되어 있는 것을 알 수 있습니다. 그러나 설치된 라이브러리들을 보면 더 많은 라이브러리들이 있는 것을 확인할 수 있습니다. 왜 이렇게 많은 라이브러리들이 있는 걸까요? -> 라이브러리들은 서로 서로 의존하고 있기 때문입니다!

그렇기 때문에 우리가 적은 라이브러리들이 의존하고 있는 다른 라이브러리들이 자동으로 다운로드 됩니다! 그렇기 떄문에 더 많은 라이브러리들이 설정되어 있습니다.

중요한 라이브러리들은 다음과 같습니다.

스프링 부트 라이브러리 spring-boot-starter-web

• spring-boot-starter-tomcat: 톰캣 (웹서버)
  • spring-webmvc: 스프링 웹 MVC
  • spring-boot-starter-thymeleaf: 타임리프 템플릿 엔진(View)
  • spring-boot-starter(공통): 스프링 부트 + 스프링 코어 + 로깅
    • spring-boot
    • • spring-core
    • spring-boot-starter-logging
    • • logback, slf4j

테스트 라이브러리

• spring-boot-starter-test
  • junit: 테스트 프레임워크
  • mockito: 목 라이브러리
  • assertj: 테스트 코드를 좀 더 편하게 작성하게 도와주는 라이브러리
  • spring-test: 스프링 통합 테스트 지원

View 환경 설정

이제 화면을 살펴 봅시다. 위에 그냥 실행하였을 때 에러 화면이 뜨는 것을 알 수 있습니다. 이는 홈 화면을 설정하지 않았기 때문에 벌어지는 에러입니다.

그렇다면 이제 홈 화면을 설정해봅시다!

홈 화면 설정

resources/static/index.html 파일을 만들어줍니다.

<!DOCTYPE HTML>
<html>
<head>
    <title>Hello</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body>
Hello
<a href="/hello">hello</a>
</body>
</html>

다음과 같이 화면이 설정되는 것을 알 수 있습니다.

이것이 바로 스프링 부트가 제공하는 Welocme Page 기능입니다. 이는 static/index.html을 첫 화면으로 인식을 하는 것입니다.

정적 컨텐츠

웰컴 페이지는 첫 화면을 보여주는 것인데 이러한 static에 있는 html 파일을 그대로 보여주는 방식을 정적 컨텐츠라고 합니다.

Spring boot는 이러한 정적 컨텐츠를 보여주는 기능을 가지고 있습니다.

동적 컨텐츠

정적 컨텐츠가 파일을 있는 그대로 보여주는 것이라면 동적 컨텐츠는 템플릿 엔진을 사용하여 웹의 페이지를 가공해서 HTML로 보여주는 방식을 말합니다!

이제 동적으로 작동하는 웹을 실습해봅시다!

java에 controller 폴더를 만들고 helloController.java를 만들어봅시다.

package helllo.hellospring.controller;

import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.GetMapping;

@Controller
public class HelloController {

    @GetMapping("hello")
    public String hello(Model model) {
        model.addAttribute("data", "hello!");
        return "hello";
    }
}

이제 resources/templates 폴더에 hello.html 파일을 만들어 줍시다.

<!DOCTYPE HTML>
<html xmlns:th="<http://www.thymeleaf.org>">
<head>
    <title>Hello</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body>
<p th:text="'안녕하세요. ' + ${data}" >안녕하세요. 손님</p>
</body>
</html>

이렇게 하면 "localhost:8080/hello"라는 URL을 들어가면 안녕하세요. hello라는 화면이 나오는 것을 확인할 수 있습니다.

무슨 일이 벌여졌는지 보면 다음과 같습니다.

1. localhost:8080/hello라는 GET 요청이 들어오면 이것을 처리하는 controller가 있는지 확인합니다.
2. 확인이 되었으니 해당하는 코드의 동작을 합니다. Model에다가 data, hello라는 키와 밸류를 담아줍니다.
3. 뷰 리졸버가 해당하는 화면을 찾아서 처리를 해줍니다.
4. Model에 data:hello가 들어왔으니 이것을 해당하는 HTML 코드에 적용해서 웹 브라우저에 띄워줍니다.

빌드하고 실행하기

이제 완성된 프로젝트를 배포하기 쉽도록 빌드를 해봅시다.

./gradlew명령어 실행 시 build/lib에 jar 파일이 빌드됩니다. 이 파일을 java -jar "이름".jar 명령어를 통해서 실행이 됩니다. 만약 빌드 파일을 지우고 싶다면 ./gradlew clean 명령어로 삭제합니다.

풀이

아이디어

간단하게 여태까지 만난 주요소 중에 가장 최저값들을 기록하면 됩니다.

다음과 같은 예제에서 보면 여태 만난 주요소 중에 최저값들을 기록하면 다음과 같을 겁니다.

이를 간단하게 거리 * 최저값의 합으로 문제를 풀 수 있습니다.

상세구현

이 코드에서 상세하게 구현할 부분은 기록하면서 최저값을 계속 보는 것입니다.

        st = new StringTokenizer(br.readLine());
        int min = 1_000_000_000;
        for(int i=0; i<N; i++) {
            int oil = Integer.parseInt(st.nextToken());
            min = Math.min(min, oil);
            cost[i] = min;
        }

다음과 같이 값을 계속 넣어줍니다.

        long sum = 0L;

        for(int i=0; i<N; i++) {
            sum += (long) dist[i] * cost[i];
        }
        System.out.println(sum);

계속 합을 구해주면 문제는 해결!

코드

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

public class No13305 {
    static int N;
    static int[] dist;
    static int[] cost;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void pro() {
        long sum = 0L;

        for(int i=0; i<N; i++) {
            sum += (long) dist[i] * cost[i];
        }
        System.out.println(sum);
    }
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        dist = new int[N];
        cost = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N-1; i++) {
            dist[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int min = 1_000_000_000;
        for(int i=0; i<N; i++) {
            int oil = Integer.parseInt(st.nextToken());
            min = Math.min(min, oil);
            cost[i] = min;
        }

        br.close();        
    }
}

풀이

아이디어

BFS로 균등한 경우를 탐색하면 됩니다. A와 B와 C의 합이 3의 배수가 아니면 균등하지 않기 때문에 0을 출력합니다. Queue에 A, B, C를 넣습니다.

이제 다음 스텝으로

1) (A, B)를 비교하여 넣거나 2) (B, C)를 비교 3) (A, C)를 비교

다음과 같이 비교하여 작은 수를 X + X로 큰 수를 Y -X로 만들어줍니다.

특이점으로는 visit를 통해서 방문 여부를 기록할 때 이차원으로만 해도 모든 경우를 확인 할 수 있습니다.

A, B, (모든 합 - (A + B))이기 때문에 C까지 Visit를 처리할 필요가 없습니다.

상세구현

A + B + C가 3의 배수가 아니라면 균등하게 분배가 되지 않습니다.

        if((A + B + C) %3 != 0) {
            System.out.println(0);
            return;
        }

큐에 처음 값인 A,B,C를 넣어줍니다.

        queue.add(new int[] {A, B, C});
          visit[A][B] = true;

이제 큐로 모든 갈 수 있는 경우를 탐색합니다.

만약 모든 탐색을 하였지만 A==B==C인 경우가 없다면 0을 출력합니다.

        while(!queue.isEmpty()) {
        // ------ 중략 -------- //
        }
        system.out.println(0);

이제 큐를 진행하면서

*1) (A, B)를 비교 2) (B, C)를 비교 3) (A, C)를 비교 *

를 구현합니다.

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();

            if(cur[0]==cur[1] && cur[1] == cur[2]) {
                System.out.println(1);
                return;
            }

            if(cur[0]<cur[1]) {
                int nx = cur[0] * 2;
                int ny = cur[1] - cur[1];

                if(!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    queue.add(new int[] {nx, ny, cur[2]});
                }
            }
            else if(cur[0]>cur[1]) {
                int nx = cur[0] - cur[1];
                int ny = cur[1] * 2;

                if(!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    queue.add(new int[] {nx, ny, cur[2]});
                }
            }
            //------중략-----//

다음과 같이 A와 B를 비교합니다.

코드

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

public class No12886 {
    static int A, B, C;

    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    private static void pro() {
        if((A + B + C) %3 != 0) {
            System.out.println(0);
            return;
        }

        boolean [][] visit= new boolean[1501][1501];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[] {A, B, C});
        visit[A][B] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();

            if(cur[0]==cur[1] && cur[1] == cur[2]) {
                System.out.println(1);
                return;
            }

            if(cur[0]<cur[1]) {
                int nx = cur[0] * 2;
                int ny = cur[1] - cur[1];

                if(!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    queue.add(new int[] {nx, ny, cur[2]});
                }
            }
            else if(cur[0]>cur[1]) {
                int nx = cur[0] - cur[1];
                int ny = cur[1] * 2;

                if(!visit[nx][ny]) {
                    visit[nx][ny] = true;
                    queue.add(new int[] {nx, ny, cur[2]});
                }
            }

            if(cur[1]<cur[2]) {
                int ny = cur[1] * 2;
                int nz = cur[2] - cur[1];

                if(!visit[cur[0]][ny]) {
                    visit[cur[0]][ny] = true;
                    queue.add(new int[] {cur[0], ny, nz});
                }
            }
            else if(cur[1]>cur[2]) {
                int ny = cur[1] - cur[2];
                int nz = cur[2] * 2;

                if(!visit[cur[0]][ny]) {
                    visit[cur[0]][ny] = true;
                    queue.add(new int[] {cur[0], ny, nz});
                }
            }

            if(cur[0]<cur[2]) {
                int nx = cur[0] * 2;
                int nz = cur[2] - cur[0];

                if(!visit[nx][cur[1]]) {
                    visit[nx][cur[1]] = true;
                    queue.add(new int[] {nx, cur[1], nz});
                }
            }
            else if(cur[0]>cur[2]) {
                int nx = cur[0] - cur[2];
                int nz = cur[2] * 2;

                if(!visit[nx][cur[1]]) {
                    visit[nx][cur[1]] = true;
                    queue.add(new int[] {nx, cur[1], nz});
                }
            }
        }
        System.out.println(0);
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        br.close();
    }
}

스프링을 기초부터 다시 공부하기 위해서 다시 로드맵을 시작하였습니다. 항상 시작만 여러번 하던 스프링 공부 이제는 처음부터 끝까지 최선을 다해 공부하겠습니다.

목표

위의 목표는 다른 로드맵으로 다시 하였기에 취소

하루에 9:30 ~ 11:40분까지 강의를 듣고 내용을 정리하여 강의 내용을 velog에 포스팅 할 예정입니다.

21년 8월에서 23년 3월까지의 긴 교육들을 끝맺히고 이제 스스로 공부를 할 시기가 되었습니다.

3월 이후에는 필요한 역량을 강화하기 위해 이것 저것 많이 시도를 하였지만 정확한 체계없이 공부를 계속하면서 특정 역량에만 취중하고 있다는 생각이 들었습니다.

이러한 문제를 해결하기 위하여 CS공부와 알고리즘, Spring 공부를 좀 더 시간 배분을 하고 정확히 공부해야 겠다고 생각이 들어 다음과 같이 글을 적게 되었습니다.

목표와 수단 정하기

배가 똑바로 가기 위해서는 나침반이 필요로 하겠죠. 공부의 목적과 방향성을 정해봅시다.

To be

나는 과연 어떤 개발자가 되고 싶은가? 나는 지금 어떤 개발자인가?

저는 늘 배우고 성장하는 능력있는 개발자이면서 이를 다른 사람들과 나눌 수 있는 개발자가 되고 싶습니다.

개발자가 되기 위해 노력하면서 많은 도움을 받았습니다. 개인적으로 존경하는 선생님을 만나기도 하였고 저를 응원해주는 친구들을 만나기도 하였습니다. 이름 모를 사람의 블로그 글을 보면서 문제를 해결한 적도 있습니다.

저 또한 누군가에게 도움이 되는 개발자가 되고 싶습니다.

To do

이러한 목표를 두었다면 이제 수단을 생각해봅시다.

제가 존경하는 혹은 본 받고 싶은 선배 개발자들이 어떻게 그 길을 걸었는지를 바라봅시다.

빠르게 그리고 실력있는 자바 개발자

[7개월간의 자바/스프링 독학 회고 (2021.11 ~ 2022.07)] (https://velog.io/@backfox/7%EA%B0%9C%EC%9B%94%EA%B0%84%EC%9D%98-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%94%84%EB%A7%81-%EB%8F%85%ED%95%99-%ED%9A%8C%EA%B3%A0-2021.11-2022.07) 밸로그에 '백여우'님입니다. 비전공자지만 정말 많은 양의 공부를 끊임없이 공부하고 이를 자신의 것으로 만들기 위해 노력하신 분입니다. 저도 SSAFY과정을 하면서 이분만큼 공부해야지라고 늘 다짐하면서 공부하였는데 이 분이 하신 것을 토대로 저도 공부를 진행하고자 합니다.

1. 영한님의 스프링 로드맵! 명실 상부한 영한님의 스프링 로드맵입니다. 이미 어느 정도 알고 있지만 빠르게 그리고 정확하게 내용을 숙지하고 넘어가는 것을 목표로 합니다.

2. 스프링 시큐리티 + 스프링 배치 + 스프링 클라우드 다음으로는 스프링에 심화 과정들을 배우고 맛보고 싶습니다. 이러한 새로운 기술들을 나의 것으로 만들고 더 좋은 스프링 개발자가 되고자 하겠습니다.

3. 다양한 토이 프로젝트 개발 패스트 캠퍼스의 '10개 프로젝트로 완성하는 백엔드 웹개발(Java/Spring) 초격차 패키지 Online.','백엔드 개발자를 위한 한 번에 끝내는 대용량 데이터 & 트래픽 처리 초격차 패키지 Online.'강의를 수강하여 토이 프로젝트 경험을 늘리겠습니다.

이렇게 자바 스프링 개발자로서의 역량을 강화하겠습니다.

기록하는 개발자가 되자

개발자의 능동적인 글쓰기를 통한 성장과 학습효과 : 왜 글쓰기를 꾸준히 진행해왔는가? - msung99

기억력을 높이는 방식 중에 가장 효율적인 방식은 '남에게 설명하기'입니다. 저 또한 제가 알고 있다고 넘어간 것을 남에게 설명하면서 사실은 그렇지 않았다는 것을 체감한 적이 많았습니다. 더 정확히 알기위하여 그리고 오래 기억하기 위하여 배운 내용들을 기록하고 남들이 보기 쉽게 정리를 하겠습니다!

기록의 방식은 '코넬노트' 방식으로 노션에 정리를 하고 이를 구어체와 제가 궁금해하는 것들을 다시 정리하여 Velog에 정리하도록 하겠습니다.

이를 통해 다른 사람들에게 도움이 되는 개발자가 되도록 하겠습니다.

체력있는 개발자가 되자

뜬금없이 왜 체력이라는 말이 나오는지에 대해서는 우연히 본 미생의 대사 때문입니다.

"네가 이루고 싶은 게 있다면 체력을 먼저 길러라. 체력이 약하면 빨리 편안함을 찾게 되고, 그러면 인내심이 떨어지고, 그리고 그 피로감을 견디지 못하면, 승부 따위는 상관없는 지경에 이르지. 이기고 싶다면, 네 고민을 충분히 견뎌줄 몸을 먼저 만들어. 정신력은 체력의 보호 없이는, 구호밖에 안 돼"

현재 재활 치료와 근력 운동을 병행하고 있지만 체력에 대해서는 깊게 생각을 해본 적이 없었기에 다시금 방향을 조정해 체력과 건강을 생각하며 운동을 진행할 예정입니다.

생존체력 이것은 살기 위한 최소한의 운동이다.' 오래된 책이지만 정말 도움이 되는 내용이 많아 다시 또 보는 책입니다.

1분 퍼피 테스트를 하여 22회를 돌파하는 것을 목표로 하겠습니다.

주 1회 월요일에 인바디 결과를 측정하고 1분 버피 테스트를 진행하여 포스팅 하도록 하겠습니다.

구체적인 계획

이제 방법들을 알았으니 이것들을 어떻게 조합할지에 대해서 이야기를 해야 할 것 같습니다.

일주일에 4회 이상 운동을 실시하겠습니다.

구체적으로 다음과 같이 시간을 분배 하겠습니다.

다음과 같이 시간 분배를 기본으로 하고 이 후 상태에 따라 유동적으로 바꾸겠습니다.

운동이 없는 날에는 스트레칭 및 가벼운 유산소 운동으로 대체하겠습니다.

커뮤니티의 활용

현재 알고리즘 스터디에 참가 하고 있는데 이 뿐만 아니라 다른 여러 스터디에 참가를 할 예정입니다.

현재 인프런 스터디를 이용하여 김영한 로드맵 스터디에 참가 신청을 한 상태입니다.

마치며

계획 없이 주먹구구식으로 공부를 진행하고 있었는데 좀 더 똑똑하게 공부를 할 필요성을 느꼈습니다. 더 열심히 공부를 하도록 하여 더 나은 개발자가 되도록 하겠습니다.

의존성주입이란?

의존성주입은 객체지향언어에서 SOLID 원칙을 지키는데 많은 도움을 주는 방식입니다. 이에 대해서 자세히 알아야 하겠죠? 의존성 주입을 알기 전!!! 우선 의존성에 대해서 이야기를 해보죠!

의존성이란?

의존성이란 무엇일까요? 의존을 하는 성질이라고 이해하면 됩니다. 의존? 프로그램에서 의존을 하나요?

네! 그렇습니다! 프로그램들은 서로 서로 의존을 하기도 합니다.

이를 쉽게 이야기하면 A가 B를 의존한다 즉 A가 B를 구현해서 사용하고 있는 경우를 생각해봅시다.

경찰이 총이라는 클래스를 갖고 있고 총에는 shoot이라는 메서드가 있다고 생각해봅시다!

police.getGun().shoot() 으로 우리는 police 개체가 가지고 있는 gun 개체를 갖고 shoot이라는 메서드를 통해 총을 쏘도록 만들었습니다!

익숙한 형태에 프로그램인데요. 하지만 이 프로그램에 경찰은 총에 의존하고 있습니다.

총에 의존한다는 의미는 총이 변하면 경찰의 코드들도 바뀐다는 것입니다.

자 총에 메서드인 shoot()을 shoooooooot()이라고 바꾸면 어떻게 될까요? police가 사용한 shoot()메서드 또한 모두 바꿔줘야 하는 것입니다.

이렇게 의존하고 있는 대상이 바뀌면 그걸 바라보는 객체도 바뀌어야 하는 것을 의존한다.라고 합니다.

딱 봐도 유지보수성이 떨어지는데요. 이를 해결하기 위한 것이 바로 의존성주입입니다.

의존성주입 원리

의존성주입이란 메인 모듈이 '직접' 다른 하위 모듈에 대한 의존성을 주기보다는 중간에 의존성 주입자가 이 부분을 가로채 메인 모듈이 '간접'적으로 의존성을 주입하는 방식입니다.

즉 위에 경찰이 직접 총을 갖고 있는 것이 아니라 중간에 관리자가 이를 가로채 원하는 결과가 나오도록 바꿔줍니다.

경찰이 shoot을 하면 총기 관리자는 이것이 shoot이 shoooooooot을 연결 시키면 됩니다. 즉 경찰이 총기를 의존하던 관계를 경찰과 총기들이 관리자를 의존하도록 만들어주었습니다.

이렇게 하면 유지보수성이 높아지고 한 곳에서 관리가 편합니다.

예를 들어 총이 아니라 수갑이라는 클래스가 새로 들어간다면 이를 관리자가 관리하고 경찰은 이 관리자에게서 사용하면 언제든지 편하게 사용이 가능합니다.

이러한 총기와 수갑이 경찰에게 의존 받는 것이 아닌 관리자를 의존하게 됩니다. 이렇게 의존의 관계가 역전되었기에 의존선 역전이라고 합니다

장점

외부에서 모듈을 생성하여 집어넣는 구조가 되기 때문에 모듈들을 쉽게 교체할 수 있는 구조입니다. 단위 테스팅과 마이그레이션이 쉬워집니다. 애플리케이션 의존성 방향이 좀 더 일관되어 코드를 추론하기가 수워집니다.

단점

코드의 양은 결국 늘어났습니다. 개발에서 이러한 코드의 증가는 COST라고 생각해야 합니다. 종속성 주입 자체가 컴파일이 아닌 런타임떄 실행하기 때문에 종속성 주입에 관한 에러를 잡기가 어려워질 수 있습니다.

요약

의존성 주입은 의존 관계 때문에 떨어지는 유지보수성 및 여러 불편함을 개선하기 위한 것이다. 의존성을 중간 관리자가 가로채서 이를 한 곳에서 관리하도록 합니다.

이러한 코드의 발생에 의해 COST가 발생하지만 유지 보수성과 테스트에 장점이 있기에 현업에서 많이 사용되고 있습니다.

Spring에서는 BEAN을 통해서 이를 관리하고 있습니다!

풀이

아이디어

그냥 수학 문제이다.

원금 + (주 * 당첨금 * 원래 잔고) / 티켓 수로 문제를 간단히 풀 수 있다.

        int num = Integer.parseInt(st.nextToken());
        int sum = num;

        for(int i=1; i<N; i++) {
            sum += Integer.parseInt(st.nextToken());
        }
        double J = Integer.parseInt(br.readLine());
        double C = Integer.parseInt(br.readLine());

        // 적어도 한 사람의 잔고는 0원보다 많기 때문에 sum이 0이 되는 경우는 없다.
        double ans = num + (num * J * C) / sum; 
        System.out.printf("%.10f", ans);

코드

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

public class No13258 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int num = Integer.parseInt(st.nextToken());
        int sum = num;

        for(int i=1; i<N; i++) {
            sum += Integer.parseInt(st.nextToken());
        }
        double J = Integer.parseInt(br.readLine());
        double C = Integer.parseInt(br.readLine());

        // 적어도 한 사람의 잔고는 0원보다 많기 때문에 sum이 0이 되는 경우는 없다.
        double ans = num + (num * J * C) / sum; 
        System.out.printf("%.10f", ans);
        br.close();
    }
}

풀이

아이디어

단순하게 이 그림을 길게 펼치면 된다.

다음과 같이 마치 전개도 처럼 쭉 펼치면 x와 다른 상점들과의 거리를 계산하기 쉬워집니다.

이를 각 방향에 맞춰서 좌표를 입력받아 처리하면 문제는 쉽게 해결이 됩니다!

1. dir, idx에 따라 좌표를 1차원으로 봐꿔준다.

이런 식으로 1차원으로 표현이 완료됬다면 이제 최솟값을 구해주면 되는데 단순하게 두 점 사이에 거리를 구하는 식과 뒤로 넘어가서 구하는 식으로 구하면 된다.

Math.abs(상점 위치 - 동근 위치)를 통해 길이 Path를 구하고

최대길이 - Path를 통해 Path의 반대 방향으로 갔을 때의 길이를 구할 수 있다.

2. 상점과 동근이의 위치의 최솟값을 더해준다.

상세구현

코드

1. dir, idx에 따라 좌표를 1차원으로 봐꿔준다.

    private static int func(int dir, int idx) {
        switch(dir) {
        // 북쪽
        case 1 :
            // 아무것도 하지 않는다.
            return idx;
        // 동쪽
        case 4 :
            // 가로 길이 만큼 더해준다.
            return N + idx;
        // 남쪽
        case 2 :
            // 가로 + 세로 + 가로 역방향
            return N + M + N - idx;
        case 3 :
            // 가로 + 세로 + 가로 + 세로 역방향
            return N + M + N + M - idx;
        }
        return 0;

2. 상점과 동근이의 위치의 최솟값을 더해준다.

        int sum = 0;
        int len = 2 * (N + M);
        for(int i : mat) {
            int path = Math.abs(x - i);
            int num = Math.min(path, len - path);
            sum += num;
        }
        System.out.println(sum);

코드

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

public class No2564 {
    static int N, M, x;
    static int[] mat;

    public static void main(String[] args) throws IOException {
        input();
        pro();
    }

    private static void pro() {
        int sum = 0;
        int len = 2 * (N + M);
        for(int i : mat) {
            int path = Math.abs(x - i);
            int num = Math.min(path, len - path);
            sum += num;
        }
        System.out.println(sum);
    }

    private static void input() 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());

        int num = Integer.parseInt(br.readLine());

        mat = new int[num];

        for(int i=0; i<num; i++) {
            st = new StringTokenizer(br.readLine());
            int dir = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken());

            idx = func(dir, idx);
            mat[i] = idx;
        }
        st = new StringTokenizer(br.readLine());
        int dir = Integer.parseInt(st.nextToken());
        int idx = Integer.parseInt(st.nextToken());
        x = func(dir, idx);
        br.close();
    }

    private static int func(int dir, int idx) {
        switch(dir) {
        // 북쪽
        case 1 :
            // 아무것도 하지 않는다.
            return idx;
        // 동쪽
        case 4 :
            // 가로 길이 만큼 더해준다.
            return N + idx;
        // 남쪽
        case 2 :
            // 가로 + 세로 + 가로 역방향
            return N + M + N - idx;
        case 3 :
            // 가로 + 세로 + 가로 + 세로 역방향
            return N + M + N + M - idx;
        }
        return 0;
    }
}

다가오는 9월 5일에 SQLD 시험을 준비하면서 좀 더 꼼꼼히 하기 위하여 수업을 수강 하였다.

사이트 : 제로베이스

강의명 : 34일 완주반 | SQL 100제 + 자격증 완성

제로 베이스 수강 화면

수강기간 : 2021.07.19 ~ 2021.08.20

34일 동안 하루에 정해진 커리큘럼의 수업을 수강하고 그것을 기록할 예정이다. 19일 개강이지만 블로그를 21일 부터 만들었기에 내용들을 간략히 하여 적을 예정이다.

분량 : 41시간

이터레이터 패턴이란?

이터레이터 패턴은 이터레이터를 사용하여 컬랙션의 요소들에 접근하는 디자인 패턴입니다. 이를 통해 순회할 수 있는 각기 다른 자료형의 구조와는 상관없이 이터레이터라는 하나의 인터페이스로 순회가 가능해서 코드의 효율화, 숫자형 index가 아닌 String등 다양한 인덱스를 기반으로 순회를 쉽게할 수 있습니다.

위에 명시된 하나의 인터페이스에 주목하면 됩니다.

여러 다양한 형태의 자료형들을 하나의 인터페이스로 묶어보는 걸로 이터레이터로 할 수 있습니다.

이터레이터 패턴 사용법

일반 적인 반복문에서는 for문을 사용합니다.

for(int i=0; i<N; i++){
    System.out.println(arr[i]);
}

다음과 같이 변수 i를 사용하여 배열의 각각의 요소에 차례대로 접근하기 위해 사용됩니다.

이렇게 사용되는 변수 i의 역할을 추상화 한 것이 Iterator 패턴입니다.

예제(https://zion830.tistory.com/33)

책꽂이 안에 책을 꽂고, 다시 책을 하나씩 확인하는 예제를 작성하겠습니다.

1) Book : 한 권의 책에 대한 정보를 가지고 있는 클래스

class Book {
    private String name;

    public Book(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

2) Aggregate : 집합체를 의미하는 인터페이스 Aggreagate는 Iterator 역할을 만들어내는 인터페이스를 결정한다.

interface Aggregate {
    public abstract Iterator createIterator();
}

3) BookShelf : 책을 보관하는 책꽂이 역할을 하는 클래스 BookShelf는 이러한 Aggregate의 구현체이다. 실제로 책꽂이 안을 돌아다닐 Iterator을 생성하고 책꽂이를 관리하는 역할을 한다.

class BookShelf implements Aggregate {
    private Book[] books;
    private int last = 0;

    public BookShelf(int size) {
        books = new Book[size];
    }

    public Book getBook(int index) {
        return books[index];
    }

    public int getLength() {
        return last;
    }

    public void appendBook(Book book) {
        if(last < books.length) {
            this.books[last] = book;
            last++;
        } else {
            System.out.println("책꽂이가 꽉 찼습니다.");
        }
    }

    @Override
    public Iterator createIterator() {
        return new BookShelfIterator(this);
    }
}

4) BookShelfIterator : BookShelf 클래스에서 검색을 수행하는 클래스 BookShelfIterator를 Iterator로 다루기 위해 Iterator 인터페이스를 상속받았습니다. Iterator 인터페이스는 Java에 이미 내장되어 있기 때문에 따로 구현하지 않습니다.

Iterator 인터페이스에 대한 공식 문서 https://docs.oracle.com/javase/8/docs/api/

class BookShelfIterator implements Iterator<Book> {
    private BookShelf bookShelf; // 검색을 수행할 책꽂이
    private int index = 0; // 현재 처리할 책의 위치

    public BookShelfIterator(BookShelf bookShelf) {
        this.bookShelf = bookShelf;
    }

    @Override
    public boolean hasNext() {
        return index < bookShelf.getLength();
    }

    @Override
    public Book next() {
        Book book = bookShelf.getBook(index++);
        return book;
    }
}

next()는 다음번 요소를 반환하고, hasNext()는 검색을 계속 수행해도 될지의 여부를 판별합니다.

이제 실제로 책꽂이에 책을 꽂고 책을 하나씩 검색해 이름을 출력합니다.

public class IteratorBookShelf {
    public static void main(String[] args) {
        BookShelf bookShelf = new BookShelf(10);

        Book book1 = new Book("Bilbe");
        Book book2 = new Book("Cinderella");
        Book book3 = new Book("Daddy-Long-Legs");

        bookShelf.appendBook(book1);
        bookShelf.appendBook(book2);
        bookShelf.appendBook(book3);

        System.out.println("현재 꽂혀있는 책 : " + bookShelf.getLength() + "권");

        Iterator it = bookShelf.createIterator();
        while(it.hasNext()) {
            Book book = (Book) it.next();
            System.out.println(book.getName());
        }
    }
}

다음과 같이 코드를 짤 수 있습니다.

총 코드

import java.util.Iterator;

// 한 권의 책에 대한 정보를 가지고 있는 클래스
class Book {
    private String name;

    public Book(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

// 집합체를 의미하는 인터페이스
// Aggreagate는 Iterator 역할을 만들어내는 인터페이스를 결정한다.
interface Aggregate {
    public abstract Iterator createIterator();
}

class BookShelf implements Aggregate {
    private Book[] books;
    private int last = 0;

    public BookShelf(int size) {
        books = new Book[size];
    }

    public Book getBook(int index) {
        return books[index];
    }

    public int getLength() {
        return last;
    }

    public void appendBook(Book book) {
        if(last < books.length) {
            this.books[last] = book;
            last++;
        } else {
            System.out.println("책꽂이가 꽉 찼습니다.");
        }
    }

    @Override
    public Iterator createIterator() {
        return new BookShelfIterator(this);
    }
}

class BookShelfIterator implements Iterator<Book> {
    private BookShelf bookShelf; // 검색을 수행할 책꽂이
    private int index = 0; // 현재 처리할 책의 위치

    public BookShelfIterator(BookShelf bookShelf) {
        this.bookShelf = bookShelf;
    }

    @Override
    public boolean hasNext() {
        return index < bookShelf.getLength();
    }

    @Override
    public Book next() {
        Book book = bookShelf.getBook(index++);
        return book;
    }
}

public class IteratorBookShelf {
    public static void main(String[] args) {
        BookShelf bookShelf = new BookShelf(10);

        Book book1 = new Book("Bilbe");
        Book book2 = new Book("Cinderella");
        Book book3 = new Book("Daddy-Long-Legs");

        bookShelf.appendBook(book1);
        bookShelf.appendBook(book2);
        bookShelf.appendBook(book3);

        System.out.println("현재 꽂혀있는 책 : " + bookShelf.getLength() + "권");

        Iterator it = bookShelf.createIterator();
        while(it.hasNext()) {
            Book book = (Book) it.next();
            System.out.println(book.getName());
        }
    }
}

왜 이터레이터 패턴을 사용할까요?

위에 for문으로 동일한 표현을 할 수 있는데 왜 이터레이터 패턴을 사용해야 할까요? 위에 보면 이것을 구현하기 위해 많은 코드를 썼는데요. Iterator 패턴을 사용하는 가장 큰 이유는 하나씩 꺼내서 처리하는 과정을 구현과 분리할 수 있기 때문입니다.

Iterator 패턴을 사용하였을 때의 코드입니다.

while(it.hasNext()) {
    Book book = (Book) it.next();
    System.out.println(book.getName());
}

for문을 사용했을 때입니다.

for(int i = 0; i < bookShelf.getLength(); i++) {
    System.out.println(bookShelf.getBook(i).getName());
}

결과값은 같아보이지만 위에 적은 하나씩 꺼내서 처리하는 과정을 구현과 분리에 집중해보시기 발랍니다. for문을 사용할 떄와 달리 Iterator 패턴을 사용할 때는 어디까지나 Iterator의 메서드를 사용할 뿐 BookShelf의 구현에서 사용되고 있는 메서드는 호출되지 않고 있습니다.

즉, Iterator 방식은 BookShelf의 구현에 의존하지 않는다는 점입니다.

예를 들어 bookShelf의 메서드 명인 getBook의 이름이 바뀌어도 Iterator는 상관없이 it.next()를 사용하여 다음을 받아오게 됩니다. 즉, BookShelf에 무언가 수정사항이 생기더라도 BookShelft가 올바른 Iterator를 반환하기만 한다면 while문이 사용되는 Main은 수정할 필요가 없는 것입니다. 하나의 클래스를 수정하더라도 다른 클래스의 큰 영향없이 작은 수정만으로도 끝낼 수 있다는 것입니다.

참고자료

• CS 지식의 정석(인프런)
• https://zion830.tistory.com/33

팩토리 패턴이란?

팩토리 패턴(factory pattern)은 객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴이자 상속 관계에 있는 두 클래스에서 상위 클래스가 중요한 뼈대를 결정하고, 하위 클래스에서 객체 생성에 관한 구체적인 내용을 결정하는 패턴입니다. - '면접을 위한 CS 전공지식 노트

상위 클래스는 오로지 뼈대만! 생성과 같은 구체적인 것은 하위 클래스만!

'커피 팩토리'라는 상위 클래스로 뼈대를 만들었습니다. 이제 타입과 price를 받아서 하위 클래스를 호출하여 결정합니다. '라떼'와 '아메리카노'가 상속받아 실제 구현(가격 지정)을 상세하게 적었습니다.

package Chapter1.No1_DesignPattern.factory;

// 상위 클래스를 추상화로 선언
abstract class Coffee {
    public abstract int getPrice();

    @Override
    public String toString() {
        return "Hi this coffee is " + this.getPrice();
    }
}

// 커피 팩토리
class CoffeeFactory {
    public static Coffee getCoffee(String type, int price) {
        if("Latte".equalsIgnoreCase(type)) return new Latte(price);
        else if("Americano".equalsIgnoreCase(type)) return new Americano(price);
        else {
            return new DefaultCoffee();
        }
    }
}
// Coffee를 상속받는다.
class DefaultCoffee extends Coffee {
    private int price;

    // 실제 구현 부분을 명시하였다.
    public DefaultCoffee() {
        this.price = -1;
    }

    @Override
    public int getPrice() {
        return this.price;
    }
}
//Coffee를 상속받는다.
class Latte extends Coffee {
    private int price;

    // 실제 구현 부분을 명시하였다.
    public Latte(int price) {
        this.price = price;
    }
    @Override
    public int getPrice() {
        return this.price;
    }
}
//Coffee를 상속받는다.
class Americano extends Coffee {
    private int price;

    // 실제 구현 부분을 명시하였다.
    public Americano(int price) {
        this.price = price;
    }

    @Override
    public int getPrice() {
        return this.price;
    }
}
public class FactoryCoffee {
    public static void main(String[] args) {
        Coffee latte = CoffeeFactory.getCoffee("Latte", 4000);
        Coffee ame = CoffeeFactory.getCoffee("Americano", 3000);
        System.out.println("Factory latte ::" + latte);
        System.out.println("Factory ame ::" + ame);
    }
}

중요한 것은 상위클래스가 중요한 뼈대를 결정, 하위 클랫에서 객체 생성에 관한 구체적인 내용을 결정한다.

상위 클래스와 하위 클래스가 분리되기 때문에 느슨한 결합을 가지며 상위 클래스에서는 인스턴스 생성 방식에 대해 전혀 알 필요가 없기 때문에 더 많은 유연성을 갖게 됩니다. 그리고 객체 생성 로직이 따로 떼어져 있기 때문에 코드를 리팩터링하더라도 한 곳만 고칠 수 있게 되니 유지 보수성이 증가됩니다.

ENUM을 이용한 팩토리 패턴!

https://inpa.tistory.com/entry/GOF-%F0%9F%92%A0-Enum-Factory-Method-%EB%B3%80%ED%98%95-%ED%8C%A8%ED%84%B4 를 참고하세요.

Enum Factory Method 변형 패턴은 GOF의 Factory Method 패턴의 단점을 보완하기 위한 패턴입니다. Factory Methothod 패턴의 가장 큰 단점은 제품 객체의 갯수마다 공장 서브 클래스를 모두 구현해야 된다는 점입니다. 즉, 제품 객체가 50개면 공장 객체도 50개를 구현해야 된다는 말입니다.

문제

이클립스를 실행하다 보면 위와 같은 사진이 뜨면서 계속 화면을 가리는 상황이 발생합니다.

이를 해결하는 방법은 뉴스풀링을 끄면 문제가 해결이 됩니다. 근데 WorkSpace를 새로 할 때마다 이러한 문제를 계속 겪어야 하는데요. 이런 문제가 왜 생겼는지 그리고 이게 무엇인지 알아보죠!

문제의 원인

구글링을 하면 설정을 통해서 이 문제를 해결하는 방법들이 나와있지만 왜 이 문제가 발생했는지는 한글 문서들에서는 나오지 않았는데요.

stack overflow에서 힌트를 얻을 수 있었습니다.

자바 11에서는 COBRA 모듈을 제거되었기 때문에 문제가 발생하였습니다.번들을 추가하면 문제가 해결될겁니다. (아래 댓글들에 의하면 추가해도 같은 문제가 발생한다고 합니다.)

위에 게시글에는 버그 리포트를 찾을 수 있었습니다.

버그 리포트에 따르면

Java11에서는 javax.xml.bind를 사용하지 않아도 되기에 삭제 조치를 하였는데 eclipse 2018의 경우 pooling news feed를 하는데 있어서 javax.xml.bind를 참조하고 있었습니다. 그렇기 때문에 new feed를 풀링을 할때 원하는 파일이 없어서 풀링에 실패를 하고 에러를 발생한 것이었습니다.

버그 리포트들을 보면 JAVA10에서 JAVA11로 넘어가면서 에러가 발생하기 시작했다는 것을 알 수 있었습니다. 또한 일부 인원들은 JAVA10으로 롤백을 해도 문제가 발생하였기에 JAVA8로 롤백을 한 방식으로 문제를 해결했습니다.

그리고 이 문제는 Eclipse 2019-09버전으로 업그레이드를 하면서 문제가 해결이 된다고 합니다.

요약

JAVA11로 넘어가면서 불필요한 파일을 삭제를 하였습니다. 하지만 이클립스 2018은 이 파일을 아직 사용하고 있었기에 없을 경우 에러를 발생하였습니다. 에러를 발생하는 이유는 news feed pooling이었기에 사용자들은 news feed pooling을 멈춤으로서 에러 발생을 막은 것입니다.

하지만 이는 2018년 이클립스와 JAVA11 환경에서 발생하는 문제입니다.

그렇기에 2019-09 이상의 이클립스와 JAVA11 사용으로 문제를 해결할 수 있습니다!

해결 방법

1. JAVA8 + eclipse 2018 버전을 사용
2. JAVA11 + elcipse 2019 이상 버전을 사용
3. 뉴스 피드 기능을 끄기

개발 환경을 갑자기 바꿀수는 없기에 3번을 하고 이후에는 2번 방법을 통해 문제를 없애도록 할 예정입니다.

news feed를 끄는 방법은 다음 포스틀 참고 하면 됩니다.https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=tnsqo1126&logNo=221410853849

새로운 워크스페이스에서 Ctrl + D 단축키가 먹히지 않는다

새로운 이클립스 WorkSpace를 새로 열면 Welcome 화면이 나옵니다.

이렇게 새로운 WorkSpace에서 코딩을 하면서 Ctrl + D가 안 먹히는 문제점이 생겼습니다.

해결

해결 방법은 다음 포스트를 보고 해결을 하였는데요. https://ddururiiiiiii.tistory.com/21

해결방법은 Welcome 화면 오른쪽 하단 Always show Welcome at start up을 해제하고 다시 실행하면 됩니다.

풀이

아이디어

이 문제를 어떤식으로 풀어야 될지 감도 안잡히는 상태에서 이 문제가 브루트포스에 비트마스킹으로 풀어야 된다는 것을 보고 도저히 생각이 나지 않아 다음 블로그 포스트를 참고하였습니다.

https://code-lab1.tistory.com/101

블로그에서 자세히 설명이 되어 있는데 단순히 이 mat[i][j]가 0이면 세로고 1이면 가로야! 라고 표시를 한겁니다.

문제의 예제를 가져와서 설명해드리겠습니다.

다음과 같이 표현된 사각형을 이제 1110 0010 0000 1100 으로 표현을 할 수 있는 겁니다. 즉 N * M의 비트수만큼의 비트마스킹을 통해 현재 직사각형의 상태를 볼 수 있고 이를 계산하면 되는 것입니다.

1. 0부터 1 << (N * M) 만큼의 범위의 직사각형 표현 방식을 브루트포스하게 검사합니다.
2. 검사하여 나온 최댓값을 저장하고 출력합니다. 이러한 저장된 값들을 비트마스킹으로 문제를 풀면 됩니다.

상세 구현

1. 0부터 1 << (N * M) 만큼의 범위의 직사각형 표현 방식을 브루트포스하게 검사합니다.

        for(int i=0; i< (1<<(N*M)); i++) {
            check(i);
        }

다음을 통해 0부터 1111~1111까지의 모든 경우를 탐색하게 됩니다.

2. 검사하여 나온 최댓값을 저장하고 출력합니다. 이제 각 값들을 구해야 합니다. 이를 구하기 위해 2중 포문으로 검색하여 가로 직사각형/ 세로 직사각형을 구해줘야 합니다.

    private static void check(int num) {
        int sum = 0;
        // 가로 찾기
        for(int i=0; i<N; i++) {
            int cur = 0;
            for(int j=0; j<M; j++) {
                int k = i * M + j;
                if((num & (1<<k)) == 0) {
                    cur *= 10;
                    cur += mat[i][j];
                }else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        // 세로 찾기
        for(int j=0; j<M; j++) {
            int cur = 0;
            for(int i=0; i<N; i++) {
                int k = i*M + j;
                if((num & (1<<k)) != 0) {
                    cur *= 10;
                    cur += mat[i][j];
                }else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        max = Math.max(max, sum);
    }

이를 통해 총 가로 직사각형들과 세로 직사각형들의 합을 구할 수 있습니다.

코드

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

public class No14391 {
    static int N, M, max;
    static int[][] mat;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void input() 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());

        mat = new int[N][M];

        for(int i=0; i<N; i++) {
            String line = br.readLine();
            for(int j=0; j<M; j++) {
                mat[i][j] = line.charAt(j)-'0';
            }
        }
        br.close();
    }
    private static void pro() {
        max = 0;
        for(int i=0; i< (1<<(N*M)); i++) {
            check(i);
        }
        System.out.println(max);
    }
    private static void check(int num) {
        int sum = 0;
        // 가로 찾기
        for(int i=0; i<N; i++) {
            int cur = 0;
            for(int j=0; j<M; j++) {
                int k = i * M + j;
                if((num & (1<<k)) == 0) {
                    cur *= 10;
                    cur += mat[i][j];
                }else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        // 세로 찾기
        for(int j=0; j<M; j++) {
            int cur = 0;
            for(int i=0; i<N; i++) {
                int k = i*M + j;
                if((num & (1<<k)) != 0) {
                    cur *= 10;
                    cur += mat[i][j];
                }else {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        max = Math.max(max, sum);
    }
}

풀이

아이디어

단순하게 생각하면 스타트에 선택된 사람들과 선택되지 않은 사람들을 따로 분류해서 계산하면 되는 문제이다.

구현의 단계를 쉽게 나눠보자

1. DFS로 조합을 만들어서 스타트팀과 스타트팀에 속하지 않은 팀을 구한다.

2. 각 팀(스타트 팀, 링크 팀)의 점수를 계산한다.

3. 최소의 값을 찾아서 저장, 출력한다.

상세구현

1. DFS로 조합 구현

DFS로 조합을 구현하는 방법은 많이 경험할 수 있습니다! 이 문제의 경우에는 N과 M(6)과 같은 경우입니다. https://www.acmicpc.net/problem/15655 조합문제이며 자신을 포함하지 않아야 하며 중복 문제를 해결하기 위해 오름차순으로 해결해야 합니다.

선택 여부는 boolean 배열을 이용하여 방문 여부를 기록하는 것이 대부분이지만 이 문제의 경우 비트마스킹을 이용하여 현재 방문한 자릿수를 저장하였습니다.

        dfs(0, 0);
//---------중략------------//
    private static void dfs(int start, int bit) {
        // 현재 선택된 애들이 기록된 bit를 가지고 
        // Start와 Link팀의 점수를 계산
        check(bit);

        for(int i=start; i<N; i++) {
            bit += (1<<i);
            dfs(i+1, bit);
            bit -= (1<<i);
        }
    }

2. 이제 bit를 가지고 각 팀의 점수를 계산해 봅시다.

전달된 bit를 한번 출력해서 내용을 보겠습니다.

11이란 bit가 왔는데요. 이 비트는 무엇을 의미할까요? 이게 왜 방문 여부를 기록해주고 있을까요?

이는 11을 2진수로 표현하면 쉽게 보입니다. 11은 이진수로 1011인데 이걸 보면 아! 하고 생각이 드실겁니다. 1이라고 표현된 자리가 Start팀에 속해 있는거죠!

0, 1, 3이 Start 팀 2가 Link 팀

이런 식으로 기록이 된 숫자들을 2중 for문을 통해서 같은 팀에 포함된 선수인 경우를 찾아 값을 더해주면 됩니다.

        int start = 0, link = 0;

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(((1 <<i) & bit) > 0 && ((1<<j) & bit) > 0) {
                    start += mat[i][j];
                }else if(((1<<i) & bit) <= 0 && ((1<<j) & bit) <= 0) {
                    link += mat[i][j];
                }
            }
        }

3. 최소의 값을 저장

        min = Math.min(min, Math.abs(start - link));

   이제 이 값을 마지막에 출력하면 문제는 해결이 됩니다.

코드

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

public class No15661 {
    static int N, min;
    static int[][] mat;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        mat = new int [N][N];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                mat[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
    }
    private static void pro() {
        min = Integer.MAX_VALUE;
        dfs(0, 0);
        System.out.println(min);
    }
    private static void dfs(int start, int bit) {
        // 현재 선택된 애들이 기록된 bit를 가지고 
        // Start와 Link팀의 점수를 계산
        check(bit);

        for(int i=start; i<N; i++) {
            bit += (1<<i);
            dfs(i+1, bit);
            bit -= (1<<i);
        }
    }
    private static void check(int bit) {
        int start = 0, link = 0;

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(((1 <<i) & bit) > 0 && ((1<<j) & bit) > 0) {
                    start += mat[i][j];
                }else if(((1<<i) & bit) <= 0 && ((1<<j) & bit) <= 0) {
                    link += mat[i][j];
                }
            }
        }
        min = Math.min(min, Math.abs(start - link));
    }
}