[Week33] 스터디 회고

DP 가 두 문제 출제 되었는데, 한 문제는 나에게 정말 어려웠다...

매 주 DP 문제가 한 문제는 출제 되었으면 연습에 정말 좋을 것 같은데, 아직도 못 푸는 문제가 많으니 할게 너무 많구나 🤣

 

스터디원들이 바빠져서 그런지 조금 지친 모습이 보이는 것 같다. (나 포함)

새롭게 또 충원 해야 하는지 고민이다.

그리고 어떻게 하면 코드 리뷰가 활발한 스터디를 만들 수 있을까...흠

---

[ 📌 내 문제 풀이 with Java ]

👉 사전

 

나는 개인적으로 점화식 도출 까지는 어렵지 않았는데 풀지 못했다. -> ?????

findStr() 메소드의 역할을 만들어내지 못해서 dp 배열의 값만 채워넣은 셈이다.

 

결국 다른 사람의 풀이를 참조해서 문제를 풀었다.

ex) N, M 이 2 2 라는 입력이 주워졌을 때

aazz
azaz
azza
zaaz
zaza
zzaa

위의 조합이 가능하고, a 로 시작 가능한 조합 3개, z 로 시작 가능한 조합이 3개 입니다.

ex) N, M 이 3 2 라는 입력이 주워졌을 때

aaazz
aazaz
aazza
azaza
azzaa
azaaz
zaaza
zaaaz
zazaa
zzaaa

- a 시작: 3 개
- aa 시작: 2개
- aaa 시작: 1개
- z 시작: 3개
- zz 시작: 1개

이렇게 누적된 값을 이용할 수 있기 때문에  aa 로 시작 하는 값은 a 로 시작 하는 값이 사전적으로 앞에 있기 때문에 기본적으로 3개의 조합은 aa 시작 보다 앞에 있습니다.

다른 예시로 z 로 시작 한다면 맨 앞 글자 a 로 시작하는 값들 6개가 기본적으로 사전적으로 앞에 있고 이는 코드 상에서는 아래 코드와 같이 a 로 시작하는 값 고려 해야합니다.

findStr(a, z - 1, k - startA);  // z 로 시작, k 에서 a 로 시작할 수 있는 경우 제거

 

a 로 시작이 가능한지 여부에 따라서 a, z 의 개수를 하나 줄여주고, k 의 값을 조정 해주는 것이 나한태는 중요한 '키 포인트' 였다.

 

/**
 * Author    : Lee In Bok
 * Date      : 2025.02.01(Sat)
 * Runtime   : 104 ms
 * Memory    : 14400 KB
 * Algorithm : Dynamic Programming
 */

package com.year2025.Week33;

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

public class G2_1256 {

    public static int[][] dp;
    public 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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int max = N + M + 1;

        dp = new int[max][max];
        dp(N, M);

        if(dp[N][M] < K) {
            System.out.println("-1");
        } else {
            findStr(N, M, K);
            System.out.println(sb.toString());
        }
    }

    /**
     * dp[3][3] = dp[2][3] + dp[3][2]
     * -> dp[2][3] + a 로 시작하는 문자열 + 남은 문자로 가능한 조합
     * -> dp[3][2] + z 로 시작하는 문자열 + 남은 문자로 가능한 조합
     */
    public static int dp(int a, int z) {
        if(a == 0 || z == 0) return 1;
        if(dp[a][z] != 0) return dp[a][z];

        return dp[a][z] = Math.min(dp(a - 1, z) + dp(a, z - 1), 1_000_000_001);
    }

    public static void findStr(int a, int z, int k) {
        // a 는 소진되었기 때문에 남은 공간 z 로 채우면 됨
        if(a == 0) {
            for(int i = 0; i < z; i++) {
                sb.append("z");
            }
            return;
        }

        if(z == 0) {
            for(int i = 0; i < a; i++) {
                sb.append("a");
            }
            return;
        }

        int startA = dp(a - 1, z);  // a 로 시작 + 남은 문자 조합

        if(startA < k) {  // a 로 시작 불가능
            sb.append("z");
            findStr(a, z - 1, k - startA);  // z 로 시작, k 에서 a 로 시작할 수 있는 경우 제거
        } else {
            sb.append("a");
            findStr(a - 1, z, k);  // a 로 시작 가능하면 또 a 로 시작 (오름차순 이라서 a 는 버릴 필요 없음)
        }
    }
}

---

👉 정수 삼각형

 

나는 Top-Down 식으로 문제를 접근해서 풀었기 때문에 다른 사람들의 풀이 보다 보기 좋지 않다..

문제를 설명할 때 Top-Down 방향으로 설명했기 때문에 나도 하향식으로 문제를 풀어 나갔는데, 문제를 다 풀고 다른 사람들의 풀이를 보니까 Bottom-Up 방식으로 문제를 접근하면 이중 for 문으로 해결이 가능했다.

 

문제를 풀 때 유연하고 다각화된 시각으로 바라보는건 항상 어렵다..

/**
 * Author    : Lee In Bok
 * Date      : 2025.02.02(Sun)
 * Runtime   : 11.65 ms
 * Memory    : 65.3 MB
 * Algorithm : Dynamic Programming
 */

package com.year2025.Week33;

public class LV3_43105 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(
                sol.solution(new int[][]{
                        {7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}
                })
        );
    }

    static class Solution {
        public int solution(int[][] triangle) {
            if(triangle.length == 1) {
                return triangle[0][0];
            }

            triangle[1][0] += triangle[0][0];
            triangle[1][1] += triangle[0][0];
            int max = Math.max(triangle[1][0], triangle[1][1]);

            for(int row = 2; row < triangle.length; row++) {
                for(int col = 0; col < triangle[row].length; col++) {
                    if(col == 0) {
                        triangle[row][0] += triangle[row - 1][0];
                        max = Math.max(max, triangle[row][0]);
                        continue;
                    }

                    if(col == triangle[row].length - 1) {
                        triangle[row][col] += triangle[row - 1][col - 1];
                        max = Math.max(max, triangle[row][col]);
                        continue;
                    }

                    triangle[row][col] += Math.max(triangle[row - 1][col - 1], triangle[row - 1][col]);
                    max = Math.max(max, triangle[row][col]);
                }
            }

            for (int[] ints : triangle) {
                for (int anInt : ints) {
                    System.out.print(anInt + " ");
                }
                System.out.println();
            }

            return max;
        }
    }
}

---

👉 세 용액

 

문제 풀이는 투 포인터 개념으로 풀었다.

처음에는 이분 탐색 문제인줄 알고 이분 탐색으로 풀었었는데, 한참 잘 못 생각 했었다.

어차피 비슷(?) 하니까 ㅎ..

/**
 * Author    : Lee In Bok
 * Date      : 2025.02.08(Sat)
 * Runtime   : 204 ms
 * Memory    : 17216 KB
 * Algorithm : Two Pointer(?)
 */

package com.year2025.Week33;

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

public class G3_2473 {

    public static long[] ans = new long[3];
    public static long[] liquid;
    public static long min = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        liquid = Arrays.stream(br.readLine().split(" "))
                       .mapToLong(Long::parseLong)
                       .sorted()
                       .toArray();
        int end = liquid.length - 1;

        for(int i = 0; i < liquid.length - 2; i++) {
            findMin(i, end);
        }

        Arrays.stream(ans).forEach(e -> System.out.print(e + " "));
    }

    /**
     * 고정 좌표: srt
     * 가변 좌표: mid, right
     * mid 와 right 를 증가, 감소 시키며 가장 0 과 가까운 값을 도출
     */
    public static void findMin(int srt, int end) {
        int mid = srt + 1;

        while(mid < end) {
            long sum = liquid[srt] + liquid[mid] + liquid[end];
            long absSum = Math.abs(sum);

            if(absSum < min) {
                min = absSum;
                ans[0] = liquid[srt];
                ans[1] = liquid[mid];
                ans[2] = liquid[end];
            }

            if(sum > 0) {
                end--;
            } else {
                mid++;
            }
        }
    }
}

---

[📌 아쉬운 점...]

요즘.. 피곤이 몸에서 떠나지 않는다.

피곤하니까 사람이 몽롱한 것도 있는데, 무엇보다 말과 생각이 무뎌지는 것 같다.

 

알고리즘 문제를 풀 때에는 조금 더 유연하고 말랑한 생각으로 접근하고 싶은데, 어쩌면 피곤함은 내 핑계 일지도..?