240407

240407 회고 💬

봄꽃들이 만개하는 4월이다. 뭐 같이 보러갈 사람도 없고 출퇴근 길에 잠깐 잠깐 보는게 전부인 개발자 1인이다. 4월 첫 째 주를 되돌아본다.

Keep 👍

• 알고리즘 풀이를 진행했다. 이번 주 드디어 골드 3을 탈출했다. 주제 정하고 어려운 문제 풀기도 좋지만 실버 수준 문제를 순서대로 해결하는게 실력향상에 좋지 않을까 해서 브론즈, 실버 문제들을 오래 풀었다. 이번 주에는 백트래킹을 주제로 잡았다. 순열, 조합 문제들을 풀다가 골드2를 달성했다. 문제 풀이 개수도 530개를 넘겼다.
  - 로마 숫자 만들기 문제를 풀었다. 조합 개념을 알고있다면 쉽게 풀 수 있는 문제다. HashSet으로 중복값을 제거했다. Set을 사용하지 않고 배열을 사용했다면 메모리 사용량을 줄일 수 있지 않을까 생각이 든다.
  - 근손실 또다른 백트래킹 문제다. 3대 500을 치는 대학원생은 매일 k 키로그람씩 들 수 있는 무게가 줄어든다. 하지만 정해진 운동을 한다면 그 운동에 할당된 무게만큼 들 수 있는 무게가 늘어난다. 따라서 어떤 순서대로 운동을 해야 매일 500 이상의 실력을 유지할 수 있는지 알아내는 문제이다. 포인트는 순열을 만들 때 마다 500 수치를 초기화해줘야 한다. 멤버 변수로 지정했더니 값이 초기화가 안 돼서 한참 고민했다.
  - 부분수열의 합 역시나 백트래킹 문제다. 공집합을 제외한 부분집합을 구하고 해당 부분집합으로 만들 수 없는 가장 작은 수를 출력하면 된다. 순열, 조합 문제를 충분히 풀어봤다면 쉽게 풀 수 있다. (제출 4번 한건 안 비밀...)
  - 피보나치 함수 문제를 풀었다. 유명한 DP 문제다. 이 문제에서는 fibo(n) 의 숫자를 묻지 않는다. fibo(n) 함수가 fibo(0) 함수와 fibo(1) 함수를 몇 번 호출하는지 묻는 문제다. 살짝 꼬아 만든 문제라고 이해하면 된다. 조금만 고민을 하면 쉽게 풀 수 있다. 기존의 피보나치 문제를 어떻게 풀었는지 곰곰이 생각해 보면 쉽게 풀이가 떠오른다.
• 서블릿 공부를 계속하고 있다. 이번 주에는 멱등성, Response 객체를 공부했다.
  - 몇번을 요청하더라도 아무 부작용 없이 똑같은 결과를 출력하는 성질을 멱등성이라고 한다. 대표적으로 GET 메소드를 말할 수 있다.
  - 응답 헤더에 값을 추가하는 메소드는 대표적으로 2가지이다. setHeader()와 addHeader()가 있다. setHeader()는 이미 있는 헤더의 값을 바꿔치기 하거나 헤더가 없다면 추가한다. addHeader()는 이미 있는 헤더의 값에 입력받은 인자를 추가하거나 헤더가 없다면 추가한다.
• 아침 일찍 출근해서 개인 공부하는 시간을 가지려고 노력하고 있다. 일찍 출근해서 알고리즘 문제 1개 해결이 목표다. 요즘은 피곤해서 일주일에 1번정도 성공한다.
• 출퇴근 공부로 자바 개념 복습을 하고 있다. 이번 주에는 Object 클래스, 불변객체, String, StringBuilder를 공부했다.

Extras 😀

로마 숫자 만들기

import java.io.*;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Solution s = new Solution();
            System.out.println(s.solution(getInput(br)));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int getInput(BufferedReader br) throws IOException {
        return Integer.parseInt(br.readLine());
    }
}


class Solution {

    public int solution(int num) {
        CombinationResolver cr = new CombinationResolver(num);
        return cr.getResult();
    }

    private class CombinationResolver {

        int select;
        int[] combinated;
        int[] group = {1, 5, 10, 50};
        Set<Integer> result = new HashSet<>();

        public CombinationResolver(int num) {
            this.select = num;
            this.combinated = new int[num];
        }

        public int getResult() {
            combinate(0, 0);
            return this.result.size();
        }

        private void combinate(int cnt, int start) {
            if (cnt == this.select) {
                saveCombinated();
                return;
            }

            for (int i = start; i < this.group.length; i++) {
                this.combinated[cnt] = this.group[i];
                combinate(cnt + 1, i);
            }
        }

        private void saveCombinated() {
            int saveNum = 0;
            for (int i : this.combinated) {
                saveNum += i;
            }
            this.result.add(saveNum);
        }
    }

}

근손실

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

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Input ip = getInput(br);
            Solution s = new Solution();
            System.out.println(s.solution(ip.gain, ip.weightLoss));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static Input getInput(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int len = Integer.parseInt(st.nextToken());
        int weightloss = Integer.parseInt(st.nextToken());

        int[] gain = new int[len];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < gain.length; i++) {
            gain[i] = Integer.parseInt(st.nextToken());
        }
        return new Input(gain, weightloss);
    }

    private static class Input {

        int[] gain;
        int weightLoss;

        public Input(int[] gain, int weightLoss) {
            this.gain = gain;
            this.weightLoss = weightLoss;
        }
    }
}

class Solution {

    public int solution(int[] gain, int weightloss) {
        PermutationResolver pr = new PermutationResolver(gain, weightloss);
        return pr.getResult();
    }

    private class PermutationResolver {

        int[] group;
        int weightloss;
        int[] permutated;
        boolean[] isUsed;
        int result = 0;

        public PermutationResolver(int[] group, int weightloss) {
            this.group = group;
            this.weightloss = weightloss;
            this.permutated = new int[this.group.length];
            this.isUsed = new boolean[this.group.length];
        }

        public int getResult() {
            permutate(0);
            return this.result;
        }

        private void permutate(int cnt) {
            if (cnt == this.group.length) {
                savePermutated();
                return;
            }

            for (int i = 0; i < this.group.length; i++) {
                if(this.isUsed[i]) continue;

                this.isUsed[i] = true;
                this.permutated[cnt] = this.group[i];
                permutate(cnt + 1);
                this.isUsed[i] = false;
            }
        }

        private void savePermutated() {
            int weight = 500;
            boolean isGood = true;
            for (int i : this.permutated) {
                weight += i;
                weight -= this.weightloss;
                if (weight < 500) {
                    isGood = false;
                    break;
                }
            }
            if(isGood) this.result++;
        }
    }
}

부분수열의 합

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

public class Main {

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Solution s = new Solution();
            System.out.println(s.solution(getInput(br)));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int[] getInput(BufferedReader br) throws IOException {
        int len = Integer.parseInt(br.readLine());

        int[] arr = new int[len];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        return arr;
    }
}

class Solution {

    public int solution(int[] arr) {
        BacktrackResolver br = new BacktrackResolver(arr, getSumOfArr(arr));
        return br.getResult();
    }

    private int getSumOfArr(int[] arr) {
        int result = 0;
        for (int i : arr) {
            result += i;
        }
        return result;
    }

    private class BacktrackResolver{
        int[] arr;
        int[] subset;

        public BacktrackResolver(int[] arr, int sumOfArr) {
            Arrays.sort(arr);
            this.arr = arr;
            this.subset = new int[sumOfArr + 2];
        }

        public int getResult() {
            backtrack(0, 0);
            for (int i = 1; i < this.subset.length; i++) {
                if(this.subset[i] == 0) return i;
            }
            return -1;
        }

        private void backtrack(int cnt, int sum) {
            if (cnt == this.arr.length) {
                saveSum(sum);
                return;
            }

            backtrack(cnt + 1, sum);
            backtrack(cnt + 1, sum + this.arr[cnt]);
        }

        private void saveSum(int sum) {
            this.subset[sum] = 1;
        }
    }
}