JOIN 문 활용

• 특정 기간동안 대여 가능한 자동차들의 대여비용 구하기

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

public class 순열 {
    static int N, M;
    static boolean[] isVisited;
    static int[] permutation;
    static StringBuilder sb = new StringBuilder();
    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());
        isVisited = new boolean[N + 1];
        permutation = new int[M];
        getPermutation(0);
        System.out.println(sb);
    }
    public static void getPermutation(int depth) {
        if (depth == M) {
            for (int i = 0; i < permutation.length; i++) {
                sb.append(permutation[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                permutation[depth] = i;
                getPermutation(depth + 1);
                isVisited[i] = false;
            }
        }
    }
}

조합

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

public class 조합 {
    static int N,M;
    static boolean[] isVisited;
    static int[] combination;
    static StringBuilder sb = new StringBuilder();
    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());

        isVisited = new boolean[N + 1];
        combination = new int[M + 1];
        getCombination(0);
        System.out.println(sb);
    }

    public static void getCombination(int depth) {
        if (depth == M) {
            for (int i = 1; i < combination.length; i++) {
                sb.append(combination[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!isVisited[i] && combination[depth] < i) {
                isVisited[i] = true;
                combination[depth + 1] = i;
                getCombination(depth + 1);
                isVisited[i] = false;
            }
        }
    }
}

중복순열

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

public class 중복순열 {
    static int N, M;
    static int[] repeatedPermutation;
    static StringBuilder sb = new StringBuilder();
    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());
        repeatedPermutation = new int[M];
        getRepeatedPermutation(0);
        System.out.println(sb);
    }
    public static void getRepeatedPermutation(int depth) {
        if (depth == M) {
            for (int i = 0; i < repeatedPermutation.length; i++) {
                sb.append(repeatedPermutation[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= N; i++) {
            repeatedPermutation[depth] = i;
            getRepeatedPermutation(depth + 1);
        }
    }

}

중복조합

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

public class 중복조합 {
    static int N, M;
    static int[] repeatedCombination;
    static StringBuilder sb = new StringBuilder();
    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());
        repeatedCombination = new int[M + 1];
        getRepeatedCombination(0);
        System.out.println(sb);
    }

    public static void getRepeatedCombination(int depth) {
        if (depth == M) {
            for (int i = 1; i < repeatedCombination.length; i++) {
                sb.append(repeatedCombination[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (repeatedCombination[depth] <= i) {
                repeatedCombination[depth + 1] = i;
                getRepeatedCombination(depth + 1);
            }
        }
    }
}

정리

기본적으로 크게 3가지가 필요하다. 순열과 조합을 돌릴 배열, (방문 여부 체크하는 배열), 결과를 반환할 배열 이때 중복순열, 중복조합은 당연하게도 방문 여부 체크하는 배열이 필요없다.

또한 다음의 2가지 기준으로 나누어 볼 수 있다 1. 순열인지 조합인지 가장 큰 차이는 조합의 경우 추가적으로 이전 값과 비교하는 로직이 필요하다는 것이다. 또한 조합의 경우 비교하는 로직이 있기 때문에 0번 index가 필요하여 1번부터 출력하는 것이 차이이다.

2. 중복이 없는지 있는지 가장 큰 차이는 방문 체크 배열의 필요 여부이다. 중복이 없다면 방문 체크 배열이 필요하지만 중복이 있다면 방문 체크 배열이 필요없다

추가) 코딩테스트에서 순열, 조합, 중복순열, 중복조합 중 1개를 구현한 뒤에 반환된 결과값이 특정 조건을 만족하는지 여부를 판단하도록 자주 출제된다. 따라서 4가지를 빠르게 구현하는 것이 중요하다.

• 정수 삼각형
• 구명보트
• 가장 큰 수
• 다리를 지나는 트럭
• 스티커 모으기
• N으로 표현
• 여행 경로

유형별 정리

1. 의사코드 구현

• 2018 KAKAO [3차]압축
• 2020 KAKAO 괄호 변환

(1) 경우에 해당하는 문제인 백준 1182번을 보도록 하자 기존에는 1개,2개, ... N 개 뽑을 때의 모든 조합에 대해서 sum 을 구하고 해당 sum 이 S 가 될 때마다 경우의 수를 증가시키려고 했다

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

public class Main {
    static int N, S;
    static int[] number;
    static int count = 0;

    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());
        S = Integer.parseInt(st.nextToken());

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

        // 조합 구해서 1,2, ... N 개 뽑을 때까지 반복
        for (int i = 1; i <= N; i++) {
            getCombination(0, i, 0, 0);
        }
        System.out.println(count);
    }

    public static void getCombination(int depth, int target,int prevOrder, int sum) {
        if (depth == target && sum == S) {
            count++;
            return;
        }

        for (int i = 0; i < N; i++) {
            if (prevOrder <= i) {
                getCombination(depth + 1, target, i + 1, sum + number[i]);
            }
        }
    }
}

하지만 백준에서 풀이시간을 확인한 결과 736ms 로 상당히 오래 걸리는 풀이임을 알게 되었고 그 이유가 combination 에서 비교하는 if 문이 존재하기 때문임을 알게 되었다. for 문안에 1줄이 추가될 때마다 매번의 depth 마다 depth*N 번의 비교가 일어나게 된다

새로운 풀이

package Baekjoon;

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

public class Main {
    static int N, S;
    static int[] number;
    static int count = 0;

    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());
        S = Integer.parseInt(st.nextToken());

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

        getCombination(0, 0);
        if(S==0) count--;
        System.out.println(count);
    }

    public static void getCombination(int depth, int sum) {
        if (depth == N) {
            if (sum == S) {
                count++;
            }
            return;
        }

        getCombination(depth + 1, sum);
        getCombination(depth + 1, sum + number[depth]);
    }
}

🎯 중복된 연산을 줄일 방법을 찾자

1차 풀이

처음 생각했던 로직은 다음과 같다 1. swan 끼리 만날 수 있는지 판단하는 bfs (map 이 바뀔 때마다 bfs 진행) 2. map 에서 얼음을 녹이는 bfs (해당 턴에서 녹은 'X' 위치를 매번 큐에 넣기)

위와 같이 진행한다면 시간초과를 만나게 된다 그 이유로는 매번 bfs 를 진행하는데 있다. 최악의 경우 약 1500*O(RC) 가 된다. (swan 이 끝과 끝에 있고 모두 얼음인 경우)

잠시 2차원 배열에서의 bfs 시간복잡도를 잡고 가도록 하자

2차원 배열에서의 bfs 시간복잡도 가로가 R, 세로가 C 라 할 때 각 점에서 연결될 수 있는 간선은 총 4개이다. (모서리는 생략해서 생각하자) 그렇다면 bfs 시간복잡도는 O(V+E) 이므로 O(RC + 4RC) 이므로 O(RC) 가 된다 (상수배 생략)

2차 풀이

따라서 매번 bfs 를 진행하는 것이 아닌 다른 방법이 필요했다. 이 때 bfs 를 매번 연산하는 것은 중복된 연산임을 파악하고 중복된 연산을 줄이고자 생각했다. 그러기 위해서는 현재에서 얼음 위치를 큐에 넣고 큐를 남기는 방식을 통해 bfs 자체는 결국 1번만 진행하는 것이 중복을 줄이는 연산임을 알게 되었다

최종 코드

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

public class Main {
    static int R, C;
    static char[][] map;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static List<int[]> swanInitPosition = new ArrayList<>();
    static Queue<Cor> waterQueue = new LinkedList<>();
    static Queue<Cor> swanQueue = new LinkedList<>();
    static boolean[][] isVisited;
    static int startX, startY, endX, endY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
        }

        // 백조 1, 2 위치 찾기 + waterQueue 에 '.' 위치 넣기
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'L') {
                    int[] p = new int[]{i, j};
                    swanInitPosition.add(p);
                    waterQueue.add(new Cor(i, j));
                } else if (map[i][j] == '.') {
                    waterQueue.add(new Cor(i, j));
                }
            }
        }

        startX = swanInitPosition.get(0)[0];
        startY = swanInitPosition.get(0)[1];
        endX = swanInitPosition.get(1)[0];
        endY = swanInitPosition.get(1)[1];

        // 최적화된 bfs 탐색 -> map 변화
        int day = 0;
        swanQueue.add(new Cor(startX, startY));
        isVisited = new boolean[R][C];
        isVisited[startX][startY] = true;

        while (!swanCanMeet()) {
            iceMelt();
            day++;
        }
        System.out.println(day);
    }

    public static boolean swanCanMeet() {
        Queue<Cor> nextSwanQueue = new LinkedList<>();
        while (!swanQueue.isEmpty()) {
            Cor swanCurrent = swanQueue.poll();
            if (swanCurrent.x == endX && swanCurrent.y == endY) return true;
            for (int d = 0; d < 4; d++) {
                int nextX = swanCurrent.x + dx[d];
                int nextY = swanCurrent.y + dy[d];
                if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C || isVisited[nextX][nextY]) continue;
                isVisited[nextX][nextY] = true;
                if (map[nextX][nextY] == 'X') {
                    nextSwanQueue.add(new Cor(nextX, nextY));
                } else {
                    swanQueue.add(new Cor(nextX, nextY));
                }
            }
        }
        swanQueue = nextSwanQueue;
        return false;
    }

    public static void iceMelt() {
        Queue<Cor> nextWaterQueue = new LinkedList<>();
        while (!waterQueue.isEmpty()) {
            Cor waterCurrent = waterQueue.poll();
            for (int d = 0; d < 4; d++) {
                int nextX = waterCurrent.x + dx[d];
                int nextY = waterCurrent.y + dy[d];
                if (nextX < 0 || nextX >= R || nextY < 0 || nextY >= C || isVisited[nextX][nextY]) continue;
                if (map[nextX][nextY] == 'X') {
                    map[nextX][nextY] = '.';
                    nextWaterQueue.add(new Cor(nextX, nextY));
                }
            }
        }
        waterQueue = nextWaterQueue;
    }
}
class Cor {
    int x;
    int y;

    public Cor(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

최적화를 할 때 핵심은 반복되는 연산을 줄일 방법을 찾는 것

1. bfs, dfs 탐색에서 가지치기
2. 여러번 탐색해야 하는 부분을 1번만 탐색하도록 줄이는 것

import java.util.*;
class Solution {
    public String solution(int n, int k, String[] cmd) {
        StringBuilder sb = new StringBuilder();

        Node current = new Node(0,null,null);
        Node root = current;
        for(int i=1; i<n; i++) {
            Node newNode = new Node(i,null,null);
            current.down = newNode;
            newNode.up = current;
            current = newNode; // 마지막이 current가 된다
        }

        current = root;
        for(int i=0; i<k; i++) {
            current = current.down;
        }

        Stack<Node> stack = new Stack<>(); // 복구를 위한 stack

        for(int i=0; i<cmd.length; i++) {
            String[] split = cmd[i].split(" ");
            String order = split[0];
            // 위로 이동
            if(order.equals("U")) {
                int X = Integer.parseInt(split[1]);
                for(int x=0; x<X; x++) {
                    current = current.up;
                }
            }
            // 아래로 이동
            else if(order.equals("D")) {
                int X = Integer.parseInt(split[1]);
                for(int x=0; x<X; x++) {
                    current = current.down;
                }
            }
            // 삭제
            else if(order.equals("C")) {
                // 맨 위인 경우
                if(current.up==null) {
                    current.down.up = null;
                }
                // 맨 아래의 경우
                else if(current.down == null) {
                    current.up.down = null;
                } else {
                    current.up.down = current.down;
                    current.down.up = current.up;
                }

                stack.push(current);
                // current 위치 변경
                if(current.down==null) current = current.up;
                else current = current.down;
            }
            // 복구
            else if(order.equals("Z")) {
                Node restored = stack.pop();
                // 맨 위의 경우
                if(restored.up == null) {
                    restored.down.up = restored;
                }
                // 맨 아래의 경우
                else if(restored.down == null) {
                    restored.up.down = restored;
                } else {
                    restored.up.down = restored;
                    restored.down.up = restored;
                }

            }
        }

        // current 위치를 맨 위로 옮김
        while(current.up!=null) {
            current = current.up;
        }

        // 모든 value 값들을 set 에 넣기
        Set<Integer> set = new HashSet<>();
        while(true) {
            set.add(current.value);
            current = current.down;
            if(current==null) break;
        }

        for(int i=0; i<n; i++) {
            if(set.contains(i)) sb.append("O");
            else sb.append("X");
        }
        return sb.toString();
    }
}
class Node {
    int value; // 0~n-1 까지의 숫자
    Node up;
    Node down;

    public Node (int value, Node up, Node down) {
        this.value = value;
        this.up = up;
        this.down = down;
    }
}

import java.util.*;
class Solution {
    static int[] inbound;
    static int[] outbound;    
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] isVisited;
    static int count;
    public int solution(int n, int[][] results) {
        // 그래프 초기화
        for(int i=0; i<n+1; i++) {
            graph.add(new ArrayList<>());
        }
        for(int[] result : results) {
            int s = result[1];
            int e = result[0];
            graph.get(s).add(e);
        }

        // 매 정점마다 dfs 
        inbound = new int[n+1];
        outbound = new int[n+1];

        for(int i=1; i<n+1; i++) {
            isVisited = new boolean[n+1];
            count = 0;
            dfs(i);
            outbound[i] = count;
        }

        int answer = 0;
        for(int i=1; i<n+1; i++) {
            if(inbound[i] + outbound[i] == n-1) answer++;
        }
        return answer;
    }

    public static void dfs(int start) {
        // 체크인
        isVisited[start] = true;
        // 연결된 곳 순회
        for(int next : graph.get(start)) {
            // 갈 수 있는가?
            if(!isVisited[next]) {
                dfs(next);
                inbound[next]++;
                count++;
            }
        }
    }
}

1차 코딩 테스트

카카오 2023 신입 개발자를 뽑길래 코딩테스트 연습도 할겸 가벼운 마음으로 지원했었다. 코딩테스트 준비를 올해 1월부터 본격적으로 해왔지만 아직 실력이 부족하다는 생각을 가지고 있었다.

이번 1차 코딩 테스트는 총 7문제를 5시간 동안 푸는 과정이었는데 나는 4문제를 풀었다. 4번 문제도 못 풀뻔 했지만 제출 2분전에 모든 TC가 통과하여 짜릿했던 걸로 기억한다.

이번 코테를 통해 느꼈던 점은 기본적인 자료구조나 알고리즘에 대해 빠르게 구현해낼 수 있도록 익숙해져있는 것이 중요한 것 같았다. 어려운 문제일수록 마치 수능 가형 30번과 같이 기본적인 논리들을 차례로 설계만 한다면 충분히 풀어낼 수 있는 것 같다.

1차 코딩 테스트 결과

감사하게도 1차를 통과하게 되어 2차 코딩테스트를 준비하게 되었다 😁

2차 코딩 테스트

사실 2차 코딩테스트도 1차 코딩테스트와 비슷하게 출제되는 줄 알았는데 전혀 아니었다.

먼저 CS 관련 객관식 문제를 12개 정도 30분 안에 풀고 그 이후에 1문제를 5시간 동안 풀게 되었다. CS 객관식 문제에서도 아직 CS 기반 지식이 부족함을 느꼈고 이후에 보는 문제는 처음 보는 형태이기도 하고 고려해야 할 상황이 너무 많아서 가장 쉬운 접근법으로 접근하다가 제대로 풀지 못했었다..

회고

단순히 코딩테스트만 준비할 게 아니라 CS공부와 더불어 프로젝트에서 진행하는 비즈니스 로직에 대한 연습과 API 작성 등 코딩테스트 이후에 진행되는 과제 전형도 신경써서 준비해야함을 깨닫게 되어서 너무 좋았다. 그리고 사실 시험이라는 압박감 때문에 재미를 덜 느꼈지 목표값에 도달하기 위한 로직을 짜는 것은 재미있는 것 같았다.

앞으로 준비해야 할 것들

1. CS 지식에 대한 기본기
2. 프로젝트의 요구사항에 맞는 비즈니스 로직의 최적화, API 작성

서류 지원

• 데브코스에 지원하게 된 동기, 백엔드 분야로 진출하고자 하는 이유, 백엔드 진로를 위해 노력해온 것 등 총 6개 질문에 대해 최대 500자를 작성하여 제출하면 되었습니다.
• 추가적으로 현재 대학생이라면 현재 남은 학점을 묻는 항목도 있었습니다. -> 온전히 데브코스에 집중할 수 있는 사람을 뽑는 것 같습니다

서류는 제대로 적기만 하면 거의 통과하는 듯 하다. 하지만 후에 면접에서 물어보기 때문에 잘 써야 되긴 한다

실력 확인 테스트

검색이 가능한 상황에서 시험을 보기 때문에 객관식 문제는 쉽게 접근할 수 있었다. 객관식 문제는 전반적으로 자바 + SQL 에서 나왔고 웹 쪽 지식을 묻는 문제도 간간히 나왔던 걸로 기억한다

코딩테스트의 경우 생각했던 것보다는 조금 어려웠는데 시간이 넉넉해서 본인은 3솔을 할 수 있었다. 문제 유형으로는 구현, 시뮬레이션(구현), dfs or bfs를 활용한 탐색 이렇게 3가지가 나왔다. (전날에 공부했던 내용을 바로 활용할 수 있는 문제가 1번에 나와서 너무 좋았다) 난이도로 보면 프로그래머스 기준 1.5레벨 정도의 문제들인 것 같았다. 코딩테스트 문제를 다 풀고 나서 시간이 남아 객관식 문제를 검토해보고(검토하는 과정에서 꽤 고쳤었다) 마감 1초 전에 제출하였다.

다행히 서류+코딩테스트 전형은 합격할 수 있었다! 🎉🎉

온라인 면접

대망의 면접,, 이렇게 공적인 상황에서 보는 면접은 처음이라서 긴장되었지만 생각보다 편안하게 대답할 수 있었다!

데브코스 면접 후기를 찾아보면 자소서 기반한 질문이 위주라고 생각해서 자소서 기반으로 예상 질문을 만들고 연습했는데 실제 면접에서는 내가 생각한 질문보다는 다른 형태의 질문이 나왔다 ㅠㅠㅠ

면접은 크게 공통 질문 + 기술 질문으로 구성되었고 특히 기술 질문은 알고 있다면 손을 들고 대답하는 형식이었다. 나는 내가 알고 있는 것은 적극적으로 답변하려고 노력했었다! (구체적인 질문 내용은 밝히기 어려운 것 같습니다 ㅠㅠ)

최종 합격

백엔드 공부를 몰입하여 할 수 있는 환경이 된 것 같아서 더 빠르고 효율적으로 성장할 수 있을 것 같다. 기본기가 탄탄한 개발자로 성장하기 위해서 노력해야 할 것 같다!

1차 풀이

-만들 수 있는 모든 조합을 모두 뽑아서 계산을 하려했는데 1번 tc에서 차례로 메모리,시간 초과가 떠서 생각해보니 의상 종류가 최대 30개 라서 만들어질 수 있는 조합의 개수가 1억개가 넘어가기에 이 풀이로는 안되는 것을 알 수 있었다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    static int[] number;
    static boolean[] isVisited;
    static int[] comb;
    static int[] counts; // 의상 종류에 따른 개수 들어있는 배열
    static Map<String, Integer> m = new HashMap<>();
    static int answer = 0;
    public int solution(String[][] clothes) {
        // map 초기화
        for (int i = 0; i < clothes.length; i++) {
            m.put(clothes[i][1], 0);
        }
        // map 생성
        for (int i = 0; i < clothes.length; i++) {
            m.put(clothes[i][1], m.get(clothes[i][1]) + 1);
        }
        // int[] 배열로 넘겨두기
        counts = new int[m.size()];
        int index=0;
        for (String key : m.keySet()) {
            counts[index++] = m.get(key);
        }

        // 조합 생성을 위한 초기화
        isVisited = new boolean[counts.length + 1];
        number = new int[counts.length + 1];
        for (int i = 0; i < number.length; i++) {
            number[i] = i;
        }
        // 1개~N개 의 조합을 생성하도록
        for (int i = 1; i <= counts.length; i++) {
            comb = new int[i + 1];
            back(1, i);
        }
        return answer;
    }

    public static void back(int depth,int target) {
        if (depth == target + 1) {
            int tempAnswer=1;
            for (int i = 1; i < comb.length; i++) {
                tempAnswer *= counts[comb[i] - 1];
            }
            answer += tempAnswer;
            return;
        }
        for (int i = 1; i < number.length; i++) {
            if (!isVisited[i] && comb[depth - 1] < number[i]) {
                comb[depth] = number[i];
                isVisited[i] = true;
                back(depth + 1, target);
                isVisited[i] = false;
            }
        }
    }
}

2차 풀이

(각 의상 종류의 개수 + 1) 을 다 곱해나가서 간단하게 풀이 할 수 있음

package Programmers.CodingTestKit.해시.위장;

// getOrDefault 라는 Map 의 메소드를 이용하면 해당 key 값의 해당하는 값을 가져오거나 default 값으로 설정한다
import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    public int solution(String[][] clothes) {
        Map<String, Integer> m = new HashMap<>();
        for (int i = 0; i < clothes.length; i++) {
            m.put(clothes[i][1], m.getOrDefault(clothes[i][1], 0)+1);
        }
        int answer = 1;
        for (String key : m.keySet()) {
            answer *= (m.get(key)+1);
        }
        return answer - 1;
    }
}

결과

1차 풀이

2차 풀이

교훈

풀이를 설계할 때 최악의 경우에 해당하는 시간복잡도를 항상 생각하면서 설계하자

2021년 카카오 공채 1번 문제

🎯 Logic

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다. 7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

위 과정에 따라서 코드를 구현하기만 하면 되는 문제이다. 다만, 굵게 강조한 동사를 모아보면 크게 3가지인데 다음과 같다.

1. 제거한다
2. 치환한다
3. 붙인다(대입한다) 나는 자바로 문제를 풀 것이므로 내가 아는 문자열 함수들 중에서 저 기능을 하는 것이 무엇인지 생각해야 했다.
4. 제거한다 -> replace, replaceAll, subString
5. 치환한다 -> replace, replaceAll, subString
6. 붙인다 -> +

위 함수를 적절히 사용하면 되는데 특히 replaceAll 함수를 사용하기 위해서는** 정규식**을 자유자재로 쓸 줄 알아야 했다

첫 번째 풀이

public String solution(String new_id) {
        // 1단계
        new_id = new_id.toLowerCase();
        // 2단계
        String s;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < new_id.length(); i++) {
            char c = new_id.charAt(i);
            if (isLowerCase(c) || isNumber(c) || c == '-' || c == '_' || c == '.') sb.append(c);
        }
        s = sb.toString();
        // 3단계
        s= s.replaceAll("[.]{2,}", ".");
        // 4단계
        if(s.charAt(0)=='.' && s.charAt(s.length()-1)=='.') {
            if(s.length()==1) s = "";
            else s = s.substring(1, s.length() - 1);
        }
        else if(s.charAt(0)=='.') s = s.substring(1, s.length());
        else if(s.charAt(s.length()-1)=='.') s = s.substring(0, s.length() - 1);
        // 5단계
        if(s.length()==0) s += "a";
        // 6단계
        if(s.length() >=16) s = s.substring(0,15);
        if(s.charAt(s.length()-1)=='.') s = s.substring(0, s.length() - 1);
        // 7단계
        char lastChar = s.charAt(s.length() - 1);
        if(s.length()<=2){
            while(s.length()<3)
                s += lastChar;
        }
        return s;
    }
    public static boolean isLowerCase(char c) {
        if(c>=97 && c<=122) return true;
        else return false;
    }

    public static boolean isNumber(char c) {
        if(c>=48 && c<=57) return true;
        else return false;
    }

(이 문제를 풀 때 3단계에서 정규식을 몰라서 상당히 해맸었다) 제거하는 과정을 subString에만 의존하다 보니 길이가 1에 대한 예외 상황도 생기고 풀고도 그다지 좋은 풀이가 아닌 것 같았다.

두 번째 풀이

public String solution(String new_id) {
        // 1단계
        String s= new_id.toLowerCase();
        // 2단계
        s = s.replaceAll("[^-_.a-z0-9]", "");
        // 3단계
        s = s.replaceAll("[.]{2,}", ".");
        // 4단계
        s = s.replaceAll("^[.]|[.]$", "");
        // 5단계
        if(s.isEmpty()) s += "a";
        // 6단계
        if(s.length() >= 16) s = s.substring(0, 15);
        s = s.replaceAll("[.]$", "");
        // 7단계
        if (s.length() <= 2) {
            while (s.length() < 3)
                s += s.charAt(s.length() - 1);
        }
        return s;
    }

보다시피 정규식이 상당히 유용하다

개인적으로 이번 문제와 같이 문제 1개에 다양한 알고리즘 및 자료구조를 활용하는 문제가 어려우면서도 좋은 문제인 것 같다. 여러번 볼 가치가 있는 문제라서 정리하려고 한다.

🎯 Logic

언뜻 보면 knapsack problem 인 것처럼 보이지만 문제를 제대로 읽게 되면 그렇지 않음을 알 수 있다. 이 문제에서의 핵심은 배낭이 K개이고 배낭마다 최대 1개의 보석을 담을 수 있고 최댓값을 구하라는 것이다. 보통 최댓값을 구하라고 할 때 흔히 생각해 볼 만한 알고리즘은 Greedy 혹은 DynamicProgramming 이다. 이 때 무게가 작은 배낭 1개마다 해당 무게보다 작거나 같은 보석들 중에 가치가 최대인 보석만을 계속 가져간다면 전체에서의 최댓값이 되지 않을까 라는 생각을 해볼 수 있다.

Greedy 알고리즘의 조건

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

또한, 매 배낭마다 각 iteration마다 보석을 넣어가며 무게가 배낭 무게 보다 큰 보석이 나오면 멈추어서 가장 큰 가치를 가지는 보석을 빼내면 되기 때문에 우선순위 큐를 사용하면 적당함을 알 수 있다

풀이

package AlgorithmStudy.자료구조.힙.P1202;

// PriorityQueue 활용문제
// Greedy + 정렬 + PriorityQueue
// 1. 배낭 무게를 정렬
// 2. 정렬된 배낭 무게 보다 같거나 작은 보석 중 최대의 가치를 가지는 보석만 선택
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,K;
    static int[][] jewelry;
    static int[] bags;
    static int answer=0;
    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());
        K = Integer.parseInt(st.nextToken());
        jewelry = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            jewelry[i][0] = Integer.parseInt(st.nextToken());
            jewelry[i][1] = Integer.parseInt(st.nextToken());
        }
        bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        // 1. 보석들에 대한 정렬
        // 2. 배낭 정렬
        Arrays.sort(jewelry, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        Arrays.sort(bags);

        // 정렬된 배낭 무게보다 작거나 같은 보석들 중 최대 가치 선택
        PriorityQueue<int[] > pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1]-o1[1];  // 가치가 클수록 우선순위 앞으로 옴
            }
        });

        int index=0;
        for (int i = 0; i < K; i++) {
            while (index<N) {
                if(bags[i] < jewelry[index][0]) break;
                pq.add(jewelry[index++]);
            }
            if(!pq.isEmpty()) answer += pq.poll()[1];
        }
        System.out.println(answer);
        LinkedList<int[]> linkedList = new LinkedList<>(new Comparator<>(){

        });
    }
}

자료구조 연습

1. ArrayList

2. LinkedList

3. Stack

• 문자열 폭발

  5. Queue

  6. PriorityQueue

• 가운데를 말해요
• 보석 도둑

  7. Set

  8. Map

알고리즘

그리디

• 컵라면
• 강의실 배정 (최소 회의실 개수와 유사)

그래프 탐색(DFS, BFS)

• 탈출
• 벽 부수고 이동하기
• 백조의 호수
• 단절점

이분탐색

• 가장 긴 증가하는 부분수열2
• 공유기 설치

재귀(query)

• 사전

정렬

• 후보 추천하기

백트래킹

• 암호 만들기

투포인터

• 두 배열의 합

동적계획법

• 퇴사
• 계단 오르기

최단거리(다익스트라, 벨만포드, 플로이드와샬)

• K번째 최단거리

정수론

• 최대공약수 하나 빼기

• 암호제작

1. Unsupervised learning
2. Mainfold learning
3. Generative model learning
4. ML density estimation 먼저 input 이 x일 때 output도 x이길 기대하기 때문에 unsupervised 방식이고 딥러닝의 흐름 중에 loss function을 Maximum likelihood 관점 즉 확률 분포라는 가정에서 바라보기 때문에 ML density estimaiton 방식이 존재한다

또한 기본적인 구조에서 encoder와 decoder 각각이 차원 축소 역할과 생성 역할을 하기 때문에 Manifold learning, Generative model learning 이기도 하다

Autoencoder가 가장 많이 사용되는 분야는 Manifold learning이다

variation Autoencoder 의 경우에 Maximum Likelihood를 활용하는 부분이 있기 때문에 딥러닝의 전반적인 학습 과정과 loss function을 바라보는 2가지 관점을 설명하려고 한다.

딥러닝의 전반적인 과정에 대해 살펴보면 결정해야 할 사항들이 몇 가지 있다. 네트워크의 구조를 설정해야 할 것이고 최종 출력과 실제 y값의 차이를 최소화 하기 위한 loss function도 정의 해야 한다. loss function으로서는 크게 1.mean squared error 2. cross entropy 2가지가 존재하며 이 2가지 밖에 존재하지 않는 이유는 loss function이 2가지 가정을 만족해야 하기 때문이다. 이 2가지 가정은 딥러닝 모델을 학습하기 위해서 핵심적인 학습 방법인 backpropagation을 성립시키기 위해서이다.

그렇다면 loss function의 최소값을 구하는 방법은 Gradient Descent 라고 하고 L(Δθ+θ) < L(θ) 일 때 마다 θ를 update 시키고 L(Δθ+θ) = L(θ) 일 때 멈추게 된다. Δθ는 learning rate를 사용하여 조금씩 값을 바꾸게 한다. (테일러 전개 상황에서 1차 미분값까지만 활용했기 때문에)

원래라면 모든 데이터에 대한 loss function 미분값을 다 더해서 parameter를 갱신해야 하지만 현실적으로 계산량이 너무 많기 때문에 위 수식 과정을 거쳐서 M개의 batch 크기만큼의 미분값의 평균을 구한 뒤에 이를 갱신에 활용한다

1번의 update를 step이라 하고 모든 data를 다 훑으면 1 epoch이라 한다 특정 layer에서 parameter를 갱신하고 다음 layer에서는 activation function의 미분값만큼 곱해지기에 paramter가 변하는 정도가 점점 작아지게 된다 -> gradient vanishing problem

Loss function에 대한 2가지 관점

Backpropagation

1. Mean Square Error

parameter 값을 갱신해 나갈 때에 activation function의 미분값들이 계속해서 곱해지기 때문에 w,b의 초기값에 영향을 많이 받게 된다.

2. Cross Entropy

출력 레이어에서의 에러값에 activation function의 미분값이 곱해지지 않아서 gradient vanishing problem 에서 좀 더 자유롭다 (학습이 좀 더 빨리 된다)

따라서 Backpropagetion 관점에서만 본다면 Cross Entropy loss function이 좀 더 유리하다고 할 수 있다

Maximum Likelihood

확률 분포는 정해지고 확률 분포를 구성하는 매개변수 값들을 적절히 변경시켜서 주어진 y값이 나올 확률이 최대가 되게끔 하는 방식(예를 들어, 가우시안 분포라고 하면 평균과 표준편차를 특정 값으로 정하면 특정 X 분포에서의 확률값들이 가장 높게 나오는 느낌 -> P(X|θ)가 최대가 되는 θ찾기)

y가 연속적인 분포라고 가정 & MLE => MSE 를 최소화 시키는 것과 동치 y가 이산적인 분포라고 가정 & MLE => CE 를 최소화 시키는 것과 동치

Reference slide - https://www.slideshare.net/NaverEngineering/ss-96581209 영상(1/3) - https://youtu.be/o_peo6U7IRM 유투브 Naver d2의 영상을 바탕으로 정리하였습니다

🎯 Logic

문제가 길지만 핵심만 파악하면 다음과 같다 매 턴마다 2가지 행동을 반복하도록 코드를 작성하면 된다 1. 해당 턴에 먹을 수 있는 물고기들의 탐색 2. 물고기 위치로 이동 및 map과 size의 변화 반영

나는 매 턴마다 먹을 수 있는 물고기들을 찾기 위해 bfs를 사용했고 해당 물고기들을 정렬(가장 위,가장 왼쪽) 하기 위해서 우선순위큐를 활용했다.

첫 번째 풀이

package AlgorithmStudy;
// 아기 상어
// 최단 경로를 구하는 문제는 bfs 사용, 
// tree 구조라고 확신 하는 경우만 dfs 사용

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

public class Main {
    static int N;
    static int[][] map;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] dp;
    static int size=2;
    static int time=0;
    static PriorityQueue<Position> pq=new PriorityQueue<>(new Comparator<Position>() {
        @Override
        public int compare(Position o1, Position o2) {
            if(o1.distance < o2.distance) return -1;
            else if (o1.distance == o2.distance) {
                if(o1.x < o2.x) return -1;
                else if (o1.x == o2.x) return Integer.compare(o1.y,o2.y);
                else return 1;
            }
            else return 1;
        }
    });
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map=new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int value=Integer.parseInt(st.nextToken());
                if (value == 9) {
                    pq.add(new Position(i,j,0));
                }
                map[i][j] = value;
            }
        }
        // 현재 위치로부터 탐색해서 먹을 수 있는 물고기 우선순위 큐에 넣기
        int eatNum=0;
        while (!pq.isEmpty() ) {
            // 1. 큐에서 꺼내기
            Position p=pq.poll();
            dp=new int[N][N];

            // 탐색
            bfs(p.x, p.y);
            if(pq.isEmpty()) break;
            else{
                Position destination=pq.poll();
                time+= destination.distance;
                pq.clear();
                // 이동 + 변화
                pq.add(destination);
                map[destination.x][destination.y]=9;
                map[p.x][p.y]=0;
                eatNum++;
                if(eatNum==size){
                    size++;
                    eatNum=0;
                }
            }
        }
        System.out.println(time);
    }
    public static void bfs(int curX,int curY) {
        Queue<Position> q = new LinkedList<>();
        q.add(new Position(curX, curY, 0));
        while (!q.isEmpty()) {
            // 1. 큐에서 꺼낸다
            Position p = q.poll();
            // 2. 목적지인가?
            if(map[p.x][p.y]<size && map[p.x][p.y]!=0) pq.add(p);
            // 3. 연결된 곳 순회
            for (int i = 0; i < 4; i++) {
                int newX = p.x + dy[i];
                int newY = p.y + dx[i];
                // 4. 갈 수 있는가?
                if ((newX >= 0 && newX < N) && (newY >= 0 && newY < N) && dp[newX][newY]==0) {
                    //  5. 간다
                        if(map[newX][newY]<=size) {
                            dp[newX][newY]=dp[p.x][p.y]+1;
                            // 6. 큐에 넣기
                            q.add(new Position(newX, newY, dp[newX][newY]));
                    }
                }
            }

        }
    }
}
class Position  {
    int x,y;
    int distance;

    public Position(int x, int y, int distance) {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
}

🎯 Logic

1. BigInteger 클래스에서 객체의 생성과 메소드 활용

   첫 번째 풀이

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

public class Main { static String A,B; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st=new StringTokenizer(br.readLine()); A=st.nextToken(); B=st.nextToken();

    BigInteger bigA=new BigInteger(A);
    BigInteger bigB=new BigInteger(B);
    System.out.println(bigA.add(bigB));


}

}

### 🎯 Logic  
1. 길이가 짧은 쪽 앞에 0을 추가해주어서 길이를 맞추기
2. 각 자리 숫자를 더하고 나머지를 출력 몫은 다음번 계산으로 넘겨주기 (마지막 몫이 0이 아니면 추가해주기)
### 두 번째 풀이

// StringBuilder 의 reverse() 함수 이용하면 쉽게 거꾸로 뒤집을 수 있다 // char -> int 형 변환 // 1. 문자 - 'a' or 'A' // 2. 숫자 - '0' import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;

public class Main { static String stringA,stringB; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st=new StringTokenizer(br.readLine()); StringBuilder sb=new StringBuilder(); StringBuilder out=new StringBuilder(); stringA=st.nextToken(); stringB=st.nextToken();

    // BigInteger 쓰지 않고 풀이하는 법
    int lenA=stringA.length();
    int lenB=stringB.length();

    // 길이가 짧은 쪽에 "0" 을 차이만큼 더해주기
    if(lenA>=lenB){
        for(int i=0; i<lenA-lenB; i++){
            sb.append("0");
        }
        stringB=sb.toString()+stringB;

    }else{
        for(int i=0; i<lenB-lenA; i++){
            sb.append("0");
        }
        stringA=sb.toString()+stringA;
    }

    // 더하는 알고리즘
    lenA=stringA.length();
    int q=0;
    for(int i=lenA-1; i>=0; i--){
        int subSum=q+(stringA.charAt(i)-'0')+(stringB.charAt(i)-'0');
        int r=subSum%10;
        q=subSum/10;
        out.append(r);
    }

    // 마지막에 몫이 있으면 추가해주기
    if(q==0) {
        System.out.println(out.reverse());
    }
    else{
        out.append(q);
        System.out.println(out.reverse());
    }

}

}

```

** 두 번째 풀이 결과 ** 자바 풀이 전체 중 7등으로 시간면에서 성능을 꽤 높였다

package AlgorithmStudy.그래프.P1260;

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

public class Main {
    static int V,E,S;
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        V=Integer.parseInt(st.nextToken());
        E=Integer.parseInt(st.nextToken());
        S=Integer.parseInt(st.nextToken());

        // 인접 리스트로 그래프 구현
        graph=new ArrayList<>(V+1);
        for (int i=0; i<V+1; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for(int i=0; i<E; i++){
            st=new StringTokenizer(br.readLine());
            int from=Integer.parseInt(st.nextToken());
            int to=Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
            graph.get(to).add(from);
        }

        // 그래프 정렬 (숫자 작은 순서로 출력 위함)
        for(int i=1; i<V+1; i++){
            ArrayList<Integer> temp=graph.get(i);
            Collections.sort(temp);
        }

        visited=new boolean[V+1];
        dfs(S);

        System.out.println();

        visited=new boolean[V+1];
        bfs(S);

    }

    static void dfs(int node){
        // 1. 체크인
        visited[node]=true;
        // 2. 목적지인가?
        System.out.print(node+" ");
        // 3. 연결된 곳을 순회
        for(int n: graph.get(node)){
            // 4. 갈 수 있는가?
            if(!visited[n])
                // 5. 간다
                dfs(n);
        }
        // 6. 체크 아웃
    }
    static void bfs(int node){
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(node);
        visited[node]=true;

        // 1. 큐에서 꺼내옴
        while(queue.size()!=0){
            int n=queue.poll();
            // 2. 목적지 인가?
            System.out.print(n+" ");
            // 3. 연결된 곳을 순회
            for(int adj: graph.get(n)){
                // 4. 갈 수 있는가?
                if(!visited[adj]){
                    // 5. 체크인
                    visited[adj]=true;
                    // 6. 큐에 넣음
                    queue.offer(adj);
                }
            }
        }

    }
}

행렬 N개를 차례로 곱할 때 곱하는 순서는 상관 없다면 시작 위치 s 부터 마지막 위치 e까지의 행렬 곱의 최솟값은 다음과 같다

DP[s][e]= min(DP[s][k]+DP[k+1][e]+A[s][0]×A[e][1]×A[k][1]) (s<=k<e 인 k의 모든 값 중에서)

특정 구간까지의 행렬 곱 최솟값이 저장되면서 최종적인 구간까지의 행렬 곱 최솟값을 구해야 하므로 동적 계획법을 사용해야 한다

처음 풀이

처음 풀이는 DP를 구할때 대각선으로 완성시켰다

import java.io.*;
import java.util.StringTokenizer;

// 동적 계획법 1 - 행렬 곱셈 순서
public class Main {
    static int N;
    static int[][] A;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N=Integer.parseInt(br.readLine());

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

        // DP 생성
        DP=new int[N+1][N+1];
        for (int i=0 ; i<N+1; i++){
            for(int j=0; j<N+1; j++){
                if(i==j) DP[i][j]=0;
                else DP[i][j]=Integer.MAX_VALUE;
            }
        }

        // 대각선으로 채워주기
        for(int j=1; j<N+1; j++){
            int e=j;
            for(int i=1; i<N+2-j; i++){
                for(int k=i; k<e; k++){
                    // 여러 개의 값들 중에서 최소값 찾기
                    // Math.min은 2개만 비교 가능
                    DP[i][e]=Math.min(DP[i][e],DP[i][k]+DP[k+1][e]+A[i][0]*A[e][1]*A[k][1]);
                }
                e++;
                if(e==N+1) break;
            }
        }

        System.out.println(DP[1][N]);
    }
}

Refactoring

행렬의 아래에서 위로 차례로 올라가면 더 쉽게 코드를 구현가능 했다

import java.io.*;
import java.util.StringTokenizer;

// 동적 계획법 1 - 행렬 곱셈 순서
public class Main {
    static int N;
    static int[][] A;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N=Integer.parseInt(br.readLine());

        A=new int[N+1][2];
        for(int i=1; i<N+1; i++){
            st=new StringTokenizer(br.readLine());
            A[i][0]=Integer.parseInt(st.nextToken()); // Matrix 에서 행
            A[i][1]=Integer.parseInt(st.nextToken()); // Matrix 에서 열
        }

        // DP 생성
        // DP[i][j] -> i 부터 j 까지 행렬 곱 중 최솟값
        DP=new int[N+1][N+1];
        // 밑에서 부터 위로 채워주기
        for(int i=N-1; i>0; i--) {
            for (int j = i + 1; j < N + 1; j++) {
                DP[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k + 1][j] + A[i][0] * A[j][1] * A[k][1]);
                }
            }
        }

        System.out.println(DP[1][N]);
    }
}

Concept of game : There are runner, chaser ,food in square stadium. runner must get food escaping chaser!

Score condition

• If runner meets food +1 point
• If runner meets chaser -1 point
• If runner go out of stadium -3point

Game condition

1. There's time left to stadium which counts the time
2. 'In game' coverts to 'Game Over' when time is over 100

Screenshot of game

Source Code

# This example is not working in Spyder directly (F5 or Run)
# Please type '!python turtle_runaway.py' on IPython console in your Spyder.

import turtle, random , time


class RunawayGame:
    def __init__(self, canvas, chaser, runner, catch_radius=10, init_dist=400):
        self.canvas = canvas
        self.runner = runner
        self.chaser = chaser
        self.catch_radius2 = catch_radius**2

        # Initialize 'runner' and 'chaser'

        self.chaser.shape('turtle')
        self.chaser.color('blue')
        self.chaser.penup()
        self.chaser.setx(-init_dist / 2)

        self.runner.shape('turtle')
        self.runner.color('red')
        self.runner.penup()
        self.runner.setx(+init_dist / 2)
        self.runner.setheading(180)



        # Instantiate an another turtle for drawing (time,score, game_status)
        self.drawer1 = turtle.RawTurtle(canvas)
        self.drawer1.hideturtle()
        self.drawer1.penup() 

        self.drawer2 = turtle.RawTurtle(canvas)
        self.drawer2.hideturtle()
        self.drawer2.penup() 

        self.drawer3 = turtle.RawTurtle(canvas)
        self.drawer3.hideturtle()
        self.drawer3.penup() 

        # create turtle's food
        self.food = turtle.RawTurtle(canvas)
        self.food.shape('circle')
        self.food.color('yellow')
        self.food.penup()
        self.food.sety(-init_dist/2)


        # creat game stadium
        self.drawer2 = turtle.RawTurtle(canvas)    
        self.drawer2.hideturtle()
        self.drawer2.speed(0)
        self.drawer2.penup()
        self.drawer2.setpos(300,-300)
        self.drawer2.pendown()
        self.drawer2.setheading(90)
        for i in range(4):
            self.drawer2.forward(600)
            self.drawer2.left(90)

    def is_catch(self):
        p = self.food.pos()
        q = self.runner.pos()
        dx, dy = p[0] - q[0], p[1] - q[1]
        return dx**2 + dy**2 < self.catch_radius2

    def is_catch_chaser(self):
        p = self.chaser.pos()
        q = self.runner.pos()
        dx, dy = p[0] - q[0], p[1] - q[1]
        return dx**2 + dy**2 < self.catch_radius2

    def start(self, ai_timer_msec=100, score=0):
        self.ai_timer_msec = ai_timer_msec
        self.score=score
        self.start_time=time.time()
        self.canvas.ontimer(self.step, self.ai_timer_msec) 

    def step(self):
        self.chaser.run_ai(self.runner) 
        self.runner.run_ai(self.chaser)

        # penalty if go out stadium
        if (self.runner.xcor()<-300 or self.runner.xcor()>300):
            self.score=self.score-3
        if (self.runner.ycor()<-300 or self.runner.ycor()>300):
            self.score=self.score-3

        # penalty if runner meet chaser
        if self.is_catch_chaser()==True:
            self.score=self.score-1

        # New food created and reward when runner meets food 
        if self.is_catch()==False:
            pass
        else:
            new_x=random.randint(-300,300)
            new_y=random.randint(-300,300)
            self.food.goto(new_x,new_y)

            self.score=self.score+1


        elapse=time.time()-self.start_time

        #draw elapsed time
        self.drawer1.undo()
        self.drawer1.penup()
        self.drawer1.setpos(-430, 200)
        self.drawer1.write(f'Time {elapse:.0f}', font={'Arial',12})  

        #draw score
        self.drawer2.undo()
        self.drawer2.penup()
        self.drawer2.setpos(-430,150)
        self.drawer2.write(f'Score {self.score}',font={'굴림',12})

        #draw game_status
        self.drawer3.undo()
        self.drawer3.penup()
        self.drawer3.setpos(-430,100)
        self.drawer3.write('In game',font={'굴림',12})

        # Game Over when time is over 100
        if elapse>100:
            self.drawer3.undo()
            self.drawer3.write("Game Over",font={'굴림',12})
            return

        self.canvas.ontimer(self.step, self.ai_timer_msec) 


class ManualMover(turtle.RawTurtle):
    def __init__(self, canvas, step_move=10, step_turn=10):
        super().__init__(canvas)
        self.step_move = step_move
        self.step_turn = step_turn

        # Register event handlers
        canvas.onkeypress(lambda: self.forward(self.step_move), 'Up')
        canvas.onkeypress(lambda: self.backward(self.step_move), 'Down')
        canvas.onkeypress(lambda: self.left(self.step_turn), 'Left')
        canvas.onkeypress(lambda: self.right(self.step_turn), 'Right')
        canvas.listen()

    def run_ai(self, opponent):
        pass


class OpponentMover(turtle.RawTurtle):
    def __init__(self, canvas, step_move=30):
        super().__init__(canvas)
        self.step_move = step_move

    def run_ai(self, opponent):
        prob = random.random()
        opp_pos=opponent.pos()
        ang=self.towards(opp_pos)
        if prob <= 0.2:
            self.setheading(ang)
            self.forward(self.step_move)


if __name__ == '__main__':

    canvas = turtle.Screen()
    canvas.title("Turtle Runaway")

    chaser = OpponentMover(canvas)
    runner = ManualMover(canvas)

    game = RunawayGame(canvas, chaser, runner)
    game.start()

    canvas.mainloop()