도커 공부를 하기 위해서 컨테이너, 이미지 설치하고 적용해보는 연습을 하고 있는 요즘입니다. 연습을 하다가 local DB도 날려보고, 많은 상황을 겪던 도중 배포해놓은 웹페이지에 (failed)net::ERR_CERT_DATE_INVALID 라는 에러가 발생하면서 데이터를 불러오지 못하고 있는 것을 확인했습니다.

해당 에러에 대해서 찾아보니 TSL/SSL 인증 기간 만료로 인해 발생하는 것이라는 글들을 보았습니다. 최근에 메일로 Certbot 관련 메일이 오긴 했는데, 그거 때문인가? 하고 서버를 확인해보았습니다.

sudo certbot certificates

프로젝트 EC2 서버에서 위와 같이 명령어를 작성하여 실행했고, 아래와 같은 결과를 얻었습니다.

놀랍게도, 현재 이 글을 작성하고 있는 시각은 2025년 1월 19일이고, 인증 만료까지 35일이나 남아있다는 것을 확인할 수 있었습니다. 도대체 어떤 문제일까요?

해결 과정 ❗️

문제를 해결하기 위해서 여러 글을 보다가 사용자의 시스템 시간과 DB 시간 또는 사용자의 인증서 시간 등이 일치않아서 생긴 문제라는 글을 보았습니다. 이 글을 보자마자 갑자기 기억 속으로 한 가지가 스쳐지나갔습니다. 그것은 바로 JpaAuditing 기능을 활용해서 Entity가 DB에 저장될 때, 생성 시간도 함께 저장하는데 이때 현재 시각이 아닌, 이상한 시간대가 저장됐던 것을 확인한 적이 있습니다. 그래서 한번 DB 시간대를 확인해보았습니다.

select now()

쿼리를 통해서 확인한 결과는 다음과 같습니다.

현재 시각은 1월 19일 23시 34분이지만, 실제 Mysql 시각은 1월 19일 14시 34분이라는 것을 확인할 수 있었습니다. 시스템 시간이 맞지 않으니 해당 에러가 났다고 판단해서 이를 다시 현재 노트북 시스템 맞춰보도록 하겠습니다.

우선, 서버 시각을 현재 한국 시각으로 맞췄습니다. 내용이 변경되었으니, 서버의 mysql을 restart 하여 변경 내용을 적용시켜보도록 하겠습니다.

시스템 시각과 동기화 된 것을 확인할 수 있었습니다. 그럼 이제 서버를 잠시 내렸다가 재배포하면 될 것으로 믿고, 재가동시켜보도록 하겠습니다.

재가동시켜보았지만,,, 생각했던 결과가 나오지 않는 것을 확인했습니다. 구글링을 하며 많은 시도를 해보았지만, 문제를 해결하지 못하여 결국 서버를 밀고... 새로운 인스턴스를 만들어 재가동시켰다 ㅠㅠㅠ 백엔드 개발자 역량을 더욱 키우기 위해 열심히 공부해야겠다는 생각이 들었다.

결론

• 1차 시도 실패
• 2차 시도 실패
• 인스턴스 삭제 후 새로운 인스턴스로 재가동 -> 성공

Reference

• https://blog.naver.com/toruin84/222538754021

문제 링크 - 백준 17253 삼삼한 수 2

해결 과정

solved.ac 마라톤 문제로 해당 문제를 접했다. 처음 문제를 보면서 느꼈던 점은 입력으로 주어진 최댓값이 너무 크다는 점이었다. 즉, N의 범위가 9,223,372,036,854,775,807보다 작거나 같은 음이 아닌 정수 N 였다. 파이썬이었다면 신경을 안 썼겠지만, Java로 문제를 풀어보는 연습을 해보니까 값의 범위가 굉장히 신경이 쓰였다. Long.MAX_VALUE 를 출력해보니 문제에서 주어진 N으로 가능한 최댓값 숫자가 나온 것을 확인했다. 또한, 3의 몇 제곱까지가 Long.MAX_VALUE 이내로 safe한지 for문을 통해서 확인해본 결과 3^39 까지 가능했다. 즉, 거듭제곱의 인덱스 범위는 0 ~ 39 까지 가능했다. 처음에는 백트래킹으로 문제를 풀이해보려고 했지만, 2^39 라는 경우의 수는 10^9을 아득히 넘어서기 때문에 불가능했다.

사고 과정 ❗️

그럼 이 문제를 어떻게 해결할 수 있을까? dp로 풀이하기에는 메모리 제한에 반드시 걸릴만큼 N의 범위가 넓었고, 그렇다고 그래프로 접근하자니 그것 또한 이상했다. 요즘에 다양한 유형의 문제들을 접하고 나니까 오히려 방법의 수가 많아져서 사고가 복잡해짐을 느꼈다.

20분 동안 고민해보다가 블로그를 참고했는데, 정말 생각지도 못한 해설이 존재했다. 3의 거듭제곱으로만 이루어진 숫자는 결국 주어진 숫자 N을 3진법으로 나타냈을 때, 각각의 진법수가 0 또는 1로 이루어져야 한다는 것이다. 즉, 만약 3진법 i번째 자리가 2라면 2*3^i 이기 때문에 3의 거듭제곱만으로 표현할 수 없다는 논리였다. 예제로 주어진 숫자 2개를 예로 들면 다음과 같다.

예제 1) N = 109 -> 삼삼한 수 O

예제 2) N = 298 -> 삼삼한 수 X

위 로직을 코드로 구현하여 제출해보니 정답 판정을 받았다! 이렇게 비트 단위로 접근하여 해결할 수 있는 풀이도 있다니... 정말 재밌는 것 같다!

코드

정답 코드

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

class Main {

    static Scanner sc = new Scanner(System.in);
    static boolean flag = true;
    static long N;

    public static void main(String[] args) {

        N = sc.nextLong();

        if (N == 0)
            flag = false;

        while (N > 0) {

            if (N % 3 == 2) {
                flag = false;
                break;
            }

            N /= 3;
        }

        System.out.println(flag ? "YES" : "NO");

    }
}

Reference

• https://2jinishappy.tistory.com/25

문제 링크 - 백준 1535 안녕

해결 과정

이 문제를 읽자마자 들었던 생각은 BackTracking(= 백트래킹) 완전탐색 방법이다.

사고 과정(1) ❗️

백트래킹으로 방향성을 잡은 이유는 조건으로 주어진 N의 범위가 1 ≤ N ≤ 20 으로 작기 때문이다. 즉, O(2^20) = 10^6 정도이기 때문에 백트래킹으로 문제를 풀어도 충분하다는 판단을 내렸다. 백트래킹 문제를 연습하기 위해서 백준 N과 M 시리즈 를 추천드립니다. 해당 문제를 풀기 위한 백트래킹 조건은 다음과 같습니다.

1. 인덱스 중복을 허용하지 않는다.
2. 인덱스의 순서가 오름차순인 것만 경우의 수로 허용한다. 즉, 숫자 1, 2, 3, 4로 이루어진 조합은 (1, 2, 3, 4) 만 허용하며, 그 외의 조합 (4, 3, 2, 1), (4, 2, 3, 1) 등은 허용하지 않는다.
3. 남은 체력이 양수(> 0)인 경우에만 유망하다고 판단하여 다음 재귀를 허용한다.

위 2가지 조건을 만족시키기 위해서 필요한 것은 visited 배열과 인덱스를 담을 리스트 가 필요하다. 이렇게 백트래킹을 정확하게 구현하면 완전탐색이기 때문에 정답을 도출할 수 있다.

사고 과정(2) ‼️

정답을 맞추고 나서 사용된 알고리즘 분류를 보니, 브루트포스 방법 외에도 DP, 배낭 문제 라는 유형이 있었다. 이 문제가 왜 DP와 배낭 문제 유형에 포함되는지 궁금했다. 우선, 배낭 문제라는 유형의 문제는 처음 접해봤기 때문에 여러 블로그를 통해서 공부했다.

배낭 문제 는 무게와 가치가 있는 여러 물건들을 무게 제한이 있는 하나의 배낭 속에 가장 높은 가치를 만들 수 있게끔 물건들을 배치하는 문제이다. 또한, 물건들을 자를 수 있는 Fractional Knapsack 문제와 물건들을 자를 수 없다고 가정하는 0-1 Knapsack 문제로 분류된다. 이번 포스팅에서 다룬 문제는 그 중에서도 0-1 Knapsack 문제였다. 점화식 내용은 명확했다.

해석해보자면, i개의 다양한 물건들이 있고, 특정 i번째 물건을 배낭의 무게 제한 때문에 넣을 수 없다면 i - 1번째 물건까지 담았을 때의 최댓값을 그대로 가져온다. 반대로 특정 i번째 물건을 무게 제한 w인 배낭에 넣을 수 있다면, (i - 1번째 보석까지 담았을 때의 최댓값)과 (i번째 물건의 가치 + w - i 무게를 담았을 때의 최대 가치)를 비교하여 큰 값을 넣어준다.

즉, i - 1번째 물건까지 넣었을 때의 상태를 계속 활용하면서 최적해를 찾아가기 때문에 DP 문제로 분류되는 것이었다.

https://www.youtube.com/watch?v=S-7YAuT9nDk

처음에 이해하기가 어려웠지만, 위 링크 영상을 보며 이해할 수 있었다. 그렇게 점화식을 적용하여 문제를 풀었더니 백트래킹으로 풀었을 때의 시간보다 더욱 짧은 시간으로 문제를 해결할 수 있었다! 해당 문제를 제대로 다룬 문제는 다음 문제를 같이 풀어보면 좋을 것 같다.

[ 백준 12865 평범한 배낭 ]

코드

정답 코드 (BackTracking)

• Java Version

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

class Main {

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;

static int N, power = 100, happiness = 0, ans = 0;
static boolean[] visited;
static ArrayList<Integer> lst = new ArrayList<>();
static int[] L;
static int[] J;

public static void main(String[] args) throws IOException {

    N = Integer.parseInt(br.readLine()); // N: 사람 수

    L = new int[N];
    J = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++)
        L[i] = Integer.parseInt(st.nextToken()); // 잃는 체력

    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < N; j++)
        J[j] = Integer.parseInt(st.nextToken()); // 얻는 기쁨

    visited = new boolean[N];
    bt(lst, 0);

    System.out.println(ans);

}

private static void bt(ArrayList<Integer> lst, int total) {

    ans = Math.max(ans, total);

    for (int i = 0; i < N; i++) {
        if (!lst.isEmpty() && lst.get(lst.size() - 1) >= i)
            continue;

        if (!visited[i] && power - L[i] > 0) {
            visited[i] = true; // 방문 처리
            lst.add(i);
            power -= L[i];
            bt(lst, total + J[i]);
            power += L[i];
            lst.remove(lst.size() - 1);
            visited[i] = false; // 복원 처리
        }
    }
}

}

- Python Version
```python
from sys import stdin

input = stdin.readline


def bt(happiness, power, lst):
    global MAX

    MAX = max(MAX, happiness)

    for i in range(n):
        # 원소가 존재하면서, 마지막 값보다 현재 i값이 더 작다면 내림차순이므로 유망하지 않음 -> continue
        if lst and lst[-1] > i:
            continue
        # 방문이 가능하고, power가 0보다 큰 경우 -> 유망하므로 backtracking 진행
        if not visited[i] and power - L[i] > 0:
            visited[i] = True  # 방문 처리
            lst.append(i)
            bt(happiness + J[i], power - L[i], lst)
            lst.pop()
            visited[i] = False  # 복원 처리

    return


n = int(input().rstrip())  # n: 사람 수
L = list(map(int, input().split()))  # L: 잃는 체력 리스트
J = list(map(int, input().split()))  # J: 기쁨 점수 리스트

power = 100
happiness = 0
MAX = 0
visited = [False for _ in range(n)]
bt(0, 100, [])

print(MAX)

정답 코드 (DP - Knapsack)

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

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int N;
    static int[] L;
    static int[] J;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

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

        L = new int[N + 1];
        J = new int[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            L[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            J[i] = Integer.parseInt(st.nextToken());

        dp = new int[N + 1][101];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j < 100; j++) {
                int weight = L[i];
                int value = J[i];
                if (j < weight)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);
            }
        }

        System.out.println(dp[N][99]);
    }
}

Reference

• https://www.youtube.com/watch?v=S-7YAuT9nDk
• https://sangminlog.tistory.com/entry/boj-1535
• https://gsmesie692.tistory.com/113?category=523232

추천 문제

• https://www.acmicpc.net/problem/12865

문제 링크 - 백준 1162 도로포장

해결 과정

처음 풀어보는 플래티넘 등급 문제이자, 정답률이 22.5%로 매우 낮은 문제이다. 문제를 읽어보면 그래프 문제라는 것을 바로 파악할 수 있는 힌트들이 많다.

1. 서울에서 포천까지 최소 시간으로 가야한다는 것
2. 두 도시(= 노드)들을 양방향으로 연결해야한다는 것

사고 과정 (1) ❗️

이 문제를 풀기 위해서 가중치가 일정하지 않다 라는 점에서 다익스트라 알고리즘을 먼저 떠올렸다. 심지어 1번 노드가 서울, N번 노드가 포천으로 출발점과 도착점이 모두 주어졌다. 다익스트라 알고리즘으로 가닥을 잡고, 도로를 K개 이하로 포장하여 최소 거리를 어떻게 구해야 할 지에 대해서 곰곰히 생각했다. 처음 떠올린 생각은 다음과 같다.

1. 다익스트라 알고리즘으로 구한 최단 거리의 경로를 역추적한다.
2. 역추적한 거리에서 시간이 오래걸리는 순서대로 k개의 도로를 포장하여 시간 가중치를 0으로 만든다.
3. 최소 시간을 출력한다.

바로 코드를 작성해보았다. 그러나, 예제에서도 작성한 코드가 원하는 정답을 내놓지 않았다. 그 이유는 생각을 깊게 하지 않아서 생긴 문제였다. 다음 그림을 보자.

나는 다익스트로 알고리즘을 통해서 최단 거리가 보장이 되고, 그 거리 중에서 가장 큰 간선의 가중치를 0으로 만들면 역시나 최단 거리가 보장될 것이라고 생각했다. 그러나, 위 그림과 같이 간선의 가중치를 0으로 만드는 것과 최단 거리가 유지되는 것은 완전히 상관이 없는 문제였다.

사고 과정 (2) ‼️

그럼 k개 이하로 포장하여 최단 거리를 만들어야 한다는 조건을 어떻게 해석하면 좋을까? 문제를 읽어보면 반드시 k개를 사용해야 하는 것이 아니다. 그저 k개 이하로 도로를 포장하여 가중치를 0으로 만들었을 때, 최단 거리를 찾는 것이다. 20분 정도 생각해보았지만, 마땅한 해답을 찾지 못하여 정답이 서술된 블로그를 보고 공부했다. 풀이는 다익스트라 + DP 이였고, 마치 0-1 BFS 와 비슷한 로직의 풀이인 것 같기도 하고, [ 벽 부수고 이동하기 ]와 같이 차원을 하나 더 만들어 도로를 몇 개 포장했는지 저장하면서 풀이하는 것과도 닮아있었다.

위 그림과 같이 다익스트라를 응용하여 문제를 풀이해보자.

1. 다익스트라 알고리즘을 작성한다.

2. 각 도시마다 주어진 포장할 수 있는 도로의 개수 k개 만큼의 공간을 만든다.

3. 우선순위 큐에는 (시작 정점, 0, 포장한 도로의 개수) 를 넣어준다. 3-1. 초기값은 (1, 0, 0) 이 된다.

4. 포장할 수 도로의 개수가 남아있다 해도, 포장하지 않고 넘어갈 수 있다. 즉, 포장하지 않은 경우와 포장할 수 있다면 도로를 포장한 경우 모두 진행한다.

5. 이 과정을 우선순위 큐가 빈 상태가 될 때까지 진행한다.

6. cost[n][k] 값은 n도시까지 k개의 도로를 포장하여 얻을 수 있는 최단 거리이다. 즉, 다익스트라 알고리즘을 모두 완료한 상태에서 cost[n][0] ~ cost[n][k] 까지의 값 중에서 가장 작은 값이 이 문제가 원하는 정답이 된다.

이렇게 코드를 작성하니 문제를 해결할 수 있었다. 시간이 지난 뒤에 다시 풀어보도록 하자!

코드

정답 코드

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def dijkstra(s, e):
    INF = float('inf')
    cost = [[INF for _ in range(k + 1)] for _ in range(n + 1)]
    cost[s][0] = 0

    pq = [(0, s, 0)]

    while pq:
        min_dist, cur_v, cnt = heappop(pq)
        if min_dist != cost[cur_v][cnt]:
            continue

        for nxt_v, nxt_dist in vertex[cur_v].items():
            # 포장할 수 있는 횟수가 남은 경우 -> 이동 비용 0으로 이동
            if cnt < k:
                # 거리를 갱신할 수 있는 경우 -> 갱신 및 heappush
                if cost[nxt_v][cnt + 1] > min_dist:
                    cost[nxt_v][cnt + 1] = min_dist  # 이동 비용: 0
                    heappush(pq, (min_dist, nxt_v, cnt + 1))

            # 포장하지 않는 경우 -> 거리를 갱신할 수 있으면 갱신 및 heappush
            new_dist = min_dist + nxt_dist
            if new_dist < cost[nxt_v][cnt]:
                cost[nxt_v][cnt] = new_dist
                heappush(pq, (new_dist, nxt_v, cnt))

    return min(cost[e][1:])


n, m, k = map(int, input().split())  # n: 도시의 수, m: 도로의 수, k: 포장할 도로의 수
vertex = [{} for _ in range(n + 1)]

# 서울: 1, 포천: n
for _ in range(m):
    v1, v2, t = map(int, input().split())
    if v2 not in vertex[v1]:
        vertex[v1][v2] = t
        vertex[v2][v1] = t
    # 노드 사이에 여러 개의 도로가 입력된다면 -> 더 적은 시간을 가진 도로로 갱신
    else:
        vertex[v1][v2] = min(vertex[v1][v2], t)
        vertex[v2][v1] = min(vertex[v2][v1], t)

dist = dijkstra(1, n)
print(dist)

Reference

• https://excited-hyun.tistory.com/157
• https://www.acmicpc.net/board/view/80120

문제 링크 - 백준 1182 부분수열의 합

해결 과정

처음 문제를 읽었을 때, 너무 간단하다고 생각해서 문제를 풀이했고, 결국 틀렸다.

사고 과정 (1) ❗️

그 이유는 부분수열의 뜻을 제대로 이해하지 못하고 있었기 때문이다. 나는 연속 부분수열로 이해하고 문제를 2중 for문을 사용한 브루트 포스 기법으로 풀이했기 때문에 빠르게 오답판정을 받았다. 개념을 정리해보자.

1. 부분수열: 인덱스의 순서가 중복되는 것 없이 불연속이 가능한 오름차순을 가지는 수열
2. 연속 부분수열: 인덱스의 순서가 중복되는 것 없이 연속적으로 오름차순을 가지는 수열

즉, 예를 들어 {1, 2, 3, 4} 라는 수열이 있을 때,

1. 부분수열: {1, 3}, {1, 4}, {1, 2, 4} 등이 부분수열이다.
2. 연속 부분수열: {1, 2, 3}, {3, 4} 등이 연속 부분수열이다.

사고 과정 (2) ‼️

문제를 정확히 이해하고 나서는 다시 어떻게 문제를 해결할 지 생각해보았다.

1. N의 범위가 1 ≤ N ≤ 20 으로 크기가 매우 작다.

2. 주어진 수열에서 음수가 존재하므로, 결국 끝까지 탐색을 시도해봐야 한다. 2-1. 즉, 부분 수열에 대해서 {1, 2, 4}의 합이 7로 만족한다고 해서 끝나는 것이 아니라, {1, 2, 4, -1, 1} 과 같은 경우도 있기 때문에 끝까지 순회를 해봐야한다.

3. N개의 원소들 중에서 최소 1개부터 최대 N개를 뽑아 만들 수 있는 조합(순서 상관 x)이므로 백트래킹 기법을 통해 경우의 수를 모두 찾는다.

4. 인덱스가 {1, 2, 3}, {2, 1, 3}, {3, 1, 2} 등 모두 같은 경우이므로, 시간복잡도를 줄이기 위해서 인덱스가 오름차순으로 결정된 것만 선택하도록 하자. 또한, {1, 1, 1,,} 과 같은 경우를 없애기 위해 방문 처리 배열 또는 리스트를 만들어서 중복되는 경우를 제외하자. (연습 - [ 백준 N과 M(2) 참고 ])

이와 같은 이유로 백트랙킹으로 문제를 재시도했다. 조합을 구하는 과정에서 인덱스 오름차순 처리, 중복 인덱스 제외와 같은 경우는 위에 적은 것과 같이 백준 N과 M(2) 문제를 풀어보면 익힐 수 있다. 비록 실버 3의 문제였지만, 여러가지 기법들을 연습해볼 수 있어 좋았다. 또한, 부분수열과 연속 부분수열의 개념을 정립할 수 있어서 괜찮은 문제인 것 같다!

TMI지만, 싸피에 입과하여 자바 코드로도 문제를 풀어봐야해서 파이썬과 자바 두 언어를 통해서 풀이했고, 코드를 모두 올려보았다. :)

코드

오답 코드 (문제 이해 x)

from sys import stdin

input = stdin.readline

n, s = map(int, input().split())
n_lst = list(map(int, input().split()))

cnt = 0
for i in range(n):
    SUM = 0
    for j in range(i, n):
        SUM += n_lst[j]
        if SUM == s:
            cnt += 1

print(cnt)

정답 코드 (Python)

from sys import stdin

input = stdin.readline


def bt(lst, total):
    global cnt

    # 크기가 양수이면서, 더한 값이 s가 되는 경우 -> cnt++
    if lst and total == s:
        cnt += 1

    for i in range(n):
        # 원소가 있고, 인덱스가 내림차순인 경우 -> 유망하지 않으므로 continue
        if lst and lst[-1] >= i:
            continue

        if not visited[i]:
            visited[i] = True  # 방문 처리
            lst.append(i)
            bt(lst, total + n_lst[i])
            lst.pop()
            visited[i] = False  # 복원 처리


n, s = map(int, input().split())
n_lst = list(map(int, input().split()))

cnt = 0
visited = [False for _ in range(n)]
bt([], 0)

print(cnt)

정답 코드 (Java)

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, s, cnt = 0, total = 0;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer> lst = new ArrayList<>();

    public static void main(String[] args) throws IOException {

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

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

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

        bt(lst, total);
        System.out.println(cnt);
    }

    private static void bt(ArrayList<Integer> lst, int total) {

        // 크기가 양수이면서, 부분 수열의 합이 s인 경우 -> cnt++a
        if (!lst.isEmpty() && total == s)
            cnt++;

        for (int i = 0; i < n; i++) {
            if (!lst.isEmpty() && lst.get(lst.size() - 1) >= i)
                continue;

            if (!visited[i]) {
                visited[i] = true; // 방문 처리
                lst.add(i);
                bt(lst, total + arr[i]);
                lst.remove(lst.size() - 1);
                visited[i] = false; // 복원 처리
            }
        }
    }
}

Reference

• https://www.acmicpc.net/problem/15650

동시성 이슈는 정말 많은 곳에서 발생한다. 보통 한정된 자원에 대해서 여러 유저들이 동시에 접근하는 상황에서 반드시 발생하는 이슈라고 생각한다. 그 예는 다음과 같다.

1. 영화, 뮤지컬, 콘서트 좌석 예약을 하는 경우
2. 음식집 예약을 하는 경우
3. 쇼핑몰에서 재고가 남아있는 의류를 주문하는 경우

이 외에도 많은 상황들이 존재한다. 이런 상황에서 백엔드 개발자들은 데이터의 정합성을 유지하면서 유저의 요청을 문제없이 해결해야한다. 그럼 그 방법에는 어떤 것들이 있을까 ?

동시성 해결 방안

카운트 감소 방법

가장 일반적으로 간단하게 생각하는 방법은 아마 일정 개수를 설정한 다음에, 요청이 들어올 때마다 개수를 요청한 개수만큼 줄이는 방법이 있을 것이다. 다음 코드를 보자.

코드

@Service
@RequiredArgsConstructor
public class StockService {

    private final StockRepository stockRepository;

    @Transactional
    public void decrease(Long id, Long quantity) {
        // Stock 조회
        Stock stock = stockRepository.findById(id).orElseThrow();

        // 재고 감소
        stock.decrease(quantity);

        // 재고 저장
        stockRepository.save(stock);
    }
}

이 코드는 매개로 받은 id에 해당하는 Entity를 조회하고, 해당 Stock Entity에 매개로 받은 quantity 개수만큼 감소를 시킨 후에 다시 DB에 저장하는 로직이다. 정말 간단한 로직이다. 이 코드가 정합성을 유지할 수 있는지 테스트를 해보자.

@Test
public void 재고감소() {
    stockService.decrease(1L, 1L);
    Stock stock = stockRepository.findById(1L).orElseThrow();

    assertEquals(99, stock.getQuantity());
}

이 테스트 코드는 당연하게도 통과한다. 그렇다면, 이 코드로 동시성 문제를 완벽하게 해결할 수 있을까?

문제점

이 코드 가지고는 동시성 문제를 해결할 수 없다. 이 코드의 문제점은 멀티 스레드 환경에서 발생한다. java ExecutorService 라이브러리를 활용하여 100개의 재고에 대해서 동시에 100개의 스레드가 재고 1개씩 감소시키는 코드를 작성해보자. 이론적으로는 각 스레드가 1씩 감소하므로 최종 결과는 0이 될 것이다.

@Test
@DisplayName("동시에 100개의 요청 - 멀티스레드 버전")
public void multiThread() throws InterruptedException {
    int threadCount = 100;

    ExecutorService executorService = Executors.newFixedThreadPool(32);
    CountDownLatch latch = new CountDownLatch(threadCount);

    for (int i = 0; i < threadCount; i++) {
        executorService.submit(() -> {
            try {
                stockService.decrease(1L, 1L);
            } finally {
                latch.countDown();
            }
        });
    }

    latch.await();

    Stock stock = stockRepository.findById(1L).orElseThrow();
    // 100 - (1 * 100) = 0
    assertEquals(0, stock.getQuantity());
}

이 코드에 대한 테스트 결과는 다음과 같다.

예상한 결과는 0개인데, 실제로는 88개가 남아있다. 왜 이런 현상이 나타날까? 그것은 바로 멀티스레드 환경에서 발생하는 레이스 컨디션 현상 때문이다. 레이스 컨디션이란 멀티스레드 환경에서 공유 자원에 동시에 여러 스레드가 접근하여 실행 순서를 예측할 수 없는 상황을 말한다.

위 사진과 같이 Lock을 걸지 않는 한, 멀티스레드 환경에서는 동시에 남아있는 quantity값이 5인 상황이 여러 스레드 환경에 적용이 될 수 있다. 즉, 그렇다면 여러 스레드가 동시에 접근 하더라도 재고를 감소하는 메소드에 하나의 스레드만 접근할 수 있도록 전략을 바꿔보자.

Java synchronized 사용

java에서 synchronized 키워드를 메소드에 붙여주면 해당 메소드가 어떤 스레드에서 사용중이면 다른 스레드에서는 접근할 수 없게 만들어준다. 따로 구현할 것 없이 해당 키워드를 메서드 반환형 타입 왼쪽에 작성해주자.

코드

// @Transactional
public synchronized void decrease(Long id, Long quantity) {
    // Stock 조회
    Stock stock = stockRepository.findById(id).orElseThrow();

    // 재고 감소
    stock.decrease(quantity);

    // 재고 저장
    stockRepository.save(stock);
}

이렇게 수정한 다음에 Test 코드를 다시 실행해보니, 결과는 다음과 같다. (단, @Transactional 어노테이션은 주석처리해주자. synchorized 키워드를 붙인다고 해도, Transactional 어노테이션의 동작 방식으로 인하여 정상적으로 작동하지 않을 수 있다.)

테스트를 통과하는 것을 알 수 있다. 그러면, 정말 이것으로 동시성 이슈를 모두 해결할 수 있을까?

문제점

이 방법 역시 허점이 많다. 현재까지는 단일 서버의 멀티스레드 환경을 가정하고, 해결책을 찾아본 것이다. 요즘엔 대부분 분산 서버를 사용한다. synchronized 는 단일 서버 내에서만 적용되고, 다른 서버의 스레드에는 관여를 하지 못한다. 즉, 각기 다른 서버에서 스레드가 동시에 접근하는 상황에서는 처음과 같이 동시성 문제를 해결할 수 없게 된다. 그럼 분산 서버까지 확장해서 해결책을 생각해보자.

DB 단 Lock

Pessimistic Lock

Optimistic Lock

Named Lock

Redis 분산 락

문제 링크 - 백준 15990 1, 2, 3 더하기 5

해결 과정

이 문제는 시리즈가 있는 문제이다. 1, 2, 3 더하기 시리즈 중에서도 5번째 문제로 기본 타입의 문제에서 크리티컬한 조건들이 추가된 문제이다. 숫자 1, 2, 3을 사용해서 특정 숫자를 표현해야 하는데 다음과 같은 조건이 붙었다.

1. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
2. 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
3. 방법의 수를 1_000_000_009로 나눈 나머지를 출력한다.

사고 과정 (1) ❗️

이 문제를 풀기 위해서 먼저 떠오른 생각은 Back Tracking(백 트래킹) 알고리즘이다. 그 이유는 바로 이전 값에 어떤 값을 더했는지 파악할 수 있어 같은 수를 2번 이상 연속해서 사용하면 안 된다. 라는 조건을 충족할 수 있을 거라고 생각했다. 그러나, n의 범위가 1 ≤ n ≤ 100_000 이기 때문에 절대 재귀로 작동하는 백트래킹으로 문제를 통과할 수 없다. 특정 조건과 합을 나타내야하는 조건 때문에 시간복잡도 측정이 어렵긴 하지만, 2^30 만 생각해도 자그마치 2^30 = 1_073_741_824 10억이 넘어 시간 초과가 난다. 그래서 다른 방법을 찾아야한다.

사고 과정 (2) ‼️

그래서 생각난 방법이 이전에 어떤 값을 더했는지 알아야 연속해서 2번 같은 수를 사용하지 않을 수 있는데, 이걸 어떻게 해결하면 좋을 지 곰곰히 생각했다. 이전 값에 따라 현재의 경우의 수가 달라진다. 라는 점에서 dp 2차원 리스트를 생각해냈다. 점화식은 다음과 같다 .

dp[i][j] = 숫자 i를 만들기 위한 방법 중 마지막 더한 숫자가 j인 경우의 수 
dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD  
dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD
dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD 

이 점화식을 보자. 문제에서 주어진 예제 4를 가지고 그림으로 나타내면 다음과 같다.

현재의 값 i 에서 3 작은 수에 대해서 3을 더해야 현재의 값 i가 되는데, 마지막 더한 숫자가 dp[i - 3][3]인 경우를 제외한 나머지 경우 즉, ... + 1 + 3 , ... + 2 + 3 과 같은 경우를 모두 더하면 dp[i][3] 즉, 마지막에 3을 더하여 현재의 i가 된 경우의 수가 되는 것이다. 이때, 문제의 조건에 따라 MOD값 = 1_000_000_009로 나눈 나머지를 저장한다. 나머지를 저장했다고 해도 모든 경우의 수를 다 더한 경우 다시 MOD를 뛰어넘을 수 있으므로 다시 한번 MOD 값으로 나눈 나머지를 정답값으로 반환한다. 이와 같이 코드를 짜고, 제출하니 정답 판정을 받았다!

코드

정답 코드

from sys import stdin

input = stdin.readline

LEN = 100_000
MOD = 1_000_000_009
# dp[i][j] -> 숫자 i를 만들기 위한 방법 중 마지막 더한 숫자가 j인 경우의 수
dp = [[0] * 4 for _ in range(LEN + 1)]
# i == 1 인 경우
dp[1][1] = 1
# i == 2 인 경우
dp[2][2] = 1
# i == 3 인 경우
dp[3][1], dp[3][2], dp[3][3] = 1, 1, 1

for i in range(4, LEN + 1):
    dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD
    dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD
    dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD

t = int(input().rstrip())
for _ in range(t):
    n = int(input().rstrip())
    print(sum(dp[n]) % MOD)

Reference

• 내 머릿 속

문제 링크 - 백준 2211 네트워크 복구

해결 과정

이 문제는 지문의 길이가 길지만, 읽어보면 되게 간단한 문제였다. 결국 두 노드가 양방향으로 연결되어있고, 1번 노드를 시작 정점으로 설정한 후에 다음 조건을 만족하면 된다.

1. 서로 다른 두 컴퓨터 간에 통신이 가능해야한다. 즉, 1번 노드를 시작으로 모든 정점과 연결되어있어야 한다.
2. 1번 노드에서 시작하여 다른 모든 노드로 최단 거리로 연결되어있어야 한다.

사고 과정 (1) ❗️

나는 처음 이 문제를 읽자마자 가장 먼저 MST(최소 스패닝 트리) 알고리즘 이 떠올랐다. 그 이유는 일단 모든 노드가 연결되어 있어야 하고, 각 노드들끼리 최단 거리로 연결되어있어야 한다고 생각했기 때문이다. MST 알고리즘 중에서 union-find 을 적용하여 풀이하는 Kruskal 알고리즘으로 풀이를 진행했다. 예제에 대한 답이 잘 출력되는 것을 확인하고, 제출했다. 매우 빠른 속도로 틀렸다.

이유를 확인해봐도 알 수가 없었다. 완벽한 Kruskal 구현이었기 때문이다. 질문 게시판을 확인해보니 나와 같은 생각한 사람들이 많이 있었다. 이유를 확인해보니 내가 MST 개념과 최단 거리 개념을 알지 못하고 있음을 확인했다.

1. MST(최소 스패닝 트리) 알고리즘은 모든 노드가 연결되면서 그 간선의 합이 최소가 되게 하는 알고리즘이다.
2. Dijkstra(다익스트라) 알고리즘은 한 노드로부터 다른 노드까지 갈 수 있는 최단 거리를 구하는 알고리즘이다.

=> 즉, 두 알고리즘은 비슷한 뉘앙스를 가지지만, 서로 연관이 없다.

위 사진을 보면, 두 알고리즘의 차이점을 직감할 수 있을 것이다. 정리하자면 간선의 최소합 과 최단 거리 와는 별개의 영역인 것이다.

사고 과정 (2) ‼️

그래서 나는 가중치가 1이 아닌 그래프에 대한 최단 거리를 구하기 위해서 다익스트라 알고리즘을 사용하기로 마음 먹었다. 마음은 먹었지만, 구현은 또 쉽지 않았다. 골드 3 이상의 다익스트라 관련 문제들을 풀어보니 경로 역추적 과정이 들어간 경우가 빈번했다. 10분 정도 생각한 후, 다음과 같은 과정을 생각해냈다.

1. 1번 정점을 시작으로 다익스트라 알고리즘을 구현한다. (경로 역추적 과정까지 포함)
2. 이후, 1번 노드에서 시작하여 2 ~ n번 노드까지의 경로를 역추적하면서 만나는 간선들을 저장한다.
3. 이때, 간선들을 Set 에 간선 번호를 오름차순으로 정렬하여 튜플로 저장한다. 3-1. (3, 1) 과 (1, 3)은 같은 간선이지만, Set에 걸러지지 않으므로 오름차순으로 정렬하여 저장한다.
4. 모든 과정 이후에 Set에 저장된 원소의 개수와 각 튜플들을 반환한다.

이렇게 코드를 구현하고, 제출한 결과 정답 판정을 받았다!

코드

오답 코드 (Kruskal 풀이)

from sys import stdin

input = stdin.readline


def find(x):
    if uf[x] != x:
        uf[x] = find(uf[x])
    return uf[x]


def union(x, y):
    x_root, y_root = find(x), find(y)
    if x_root == y_root:
        return

    if x_root > y_root:
        x_root, y_root = y_root, x_root

    uf[y_root] = x_root


n, m = map(int, input().split())  # 1 ≤ n ≤ 1_000

edges = []
uf = [i for i in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

# 통신 시간 순서대로 오름차순 정렬
edges.sort()

cnt = 0
mst = []
total = 0
for cost, a, b in edges:
    if find(a) != find(b):
        union(a, b)
        total += cost
        cnt += 1
        mst.append((a, b))

print(cnt)
for a, b in mst:
    print(f"{a} {b}")

정답 코드 (Dijkstra 풀이)

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def save_trace(path):
    global ans

    for e in range(2, n + 1):
        trace = []
        curr = e
        while curr != -1:
            trace.append(curr)
            curr = path[curr]

        for i in range(len(trace) - 1, 0, -1):
            lst = sorted([trace[i], trace[i - 1]])
            ans.add(tuple(lst))


def dijkstra(s):
    INF = int(1e9)
    dist = [INF for _ in range(n + 1)]
    path = [-1 for _ in range(n + 1)]

    dist[s] = 0
    pq = [(0, s)]
    while pq:
        min_dist, cur_v = heappop(pq)

        if min_dist != dist[cur_v]:
            continue

        for nxt_v, nxt_dist in vertex[cur_v]:
            new_dist = min_dist + nxt_dist
            if new_dist < dist[nxt_v]:
                dist[nxt_v] = new_dist
                path[nxt_v] = cur_v
                heappush(pq, (new_dist, nxt_v))

    save_trace(path)


n, m = map(int, input().split())  # 1 ≤ n ≤ 1_000
vertex = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    vertex[a].append((b, c))
    vertex[b].append((a, c))

ans = set()
dijkstra(1)
print(len(ans))
for a, b in list(ans):
    print(f"{a} {b}")

Reference

• https://www.acmicpc.net/board/view/108483

문제 링크 - 백준 11779 최소비용 구하기 2

해결 과정

이 문제는 전형적인 다익스트라 알고리즘 문제에서 더 나아가 최단 경로를 추적하는 문제이다.

사고 과정 ❗️

우선, 기본 다익스트라 핵심 알고리즘 코드는 다음과 같다.

from heapq import heappush, heappop 

def dijkstra(s, e):
    INF = float('inf')
    dist = [INF for _ in range(n + 1)]

    dist[s] = 0
    pq = [(0, s)]
    while pq:

        min_dist, cur_v = heappop(pq)
        if min_dist != dist[cur_v]:
            continue

        if cur_v == e:
            break

        for nxt_v, nxt_dist in vertex[cur_v]:
            new_dist = min_dist + nxt_dist
            if new_dist < dist[nxt_v]:
                dist[nxt_v] = new_dist
                heappush(pq, (new_dist, nxt_v))

    return dist[e]

이 코드에서 경로를 추적하기 위한 알고리즘을 추가해주면 된다. 여러 블로그들의 도움을 받아 흐름을 이해할 수 있었다. 그 흐름은 다음과 같다.

1. 경로를 추적할 수 있는 path 리스트를 하나 만든다.
2. 최단 거리를 갱신할 때마다 다음 노드 인덱스에 현재 노드 인덱스를 저장 한다.
3. 목적지 노드의 인덱스부터 시작하여 저장된 이전 노드들을 거슬러 올라가면서 경로를 역추적한다.
4. 역추적했기 때문에, 결과로 나온 경로의 순서를 뒤집는다. 4-1. 역추적을 편리하게 하기 위해서 deque의 appendleft를 사용해도 좋을 것 같다.

이런 과정을 거쳐 최단 거리로 움직인 경로를 찾아낼 수 있다.(단, 노드의 저장 순서에 따라 여러가지 경로가 나올 수 있다.)

def get_trace(path, e):
    trace = []  # 경로 저장 리스트 
    curr = e 
    while curr != -1:
        trace.append(curr) 
        curr = path[curr]  # 경로 역추적 

    return trace[::-1]  # 역순 반환 

def dijkstra(s, e):

    path = [-1 for _ in range(n + 1)]  # 경로 저장 리스트 

    while pq:

    ...

        for nxt_v, nxt_dist in vertex[cur_v]:
            new_dist = min_dist + nxt_dist
            # 최단 거리를 갱신하는 경우 
            if new_dist < dist[nxt_v]:
                path[nxt_v] = cur_v  # 다음 노드의 현재 노드를 저장 
    ...

    return dist[e], get_trace(path, e)  # 목적지까지 최단 거리와 경로 반환 

기존 다익스트라 알고리즘에서 추가된 부분만을 강조하여 작성해보았다. 비록 코드 몇 줄만을 추가했지만, 이걸 생각해내는 게 쉽지 않았다. 이 방법이 응용되어 쓰일 수 있으므로 다음 노드에 현재 노드를 저장하면서 경로를 역추적하는 방법을 기억해두자.

이렇게 공부를 한 다음에 코드를 제출했는데 틀렸다. 왜인지 디버깅하면서 이유를 찾아보니 문제에서 요구하는 조건은 단방향 조건이었다. 그러나, 나는 양방향으로 v1, v2 노드에 서로의 노드를 같이 저장하여 정답을 잘못 출력한 것이었다. 이 조건을 맞추고 다시 제출하니 정답 판정을 받았다!

코드

오답 코드 (오답 요인: 양방향)

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def get_trace(path, e):
    trace = []
    curr = e
    while curr != -1:
        trace.append(curr)
        curr = path[curr]

    return trace[::-1]


def dijkstra(s, e):
    INF = float('inf')
    dist = [INF for _ in range(n + 1)]
    path = [-1 for _ in range(n + 1)]

    dist[s] = 0
    pq = [(0, s)]
    while pq:

        min_dist, cur_v = heappop(pq)
        if min_dist != dist[cur_v]:
            continue

        if cur_v == e:
            break

        for nxt_v, nxt_dist in vertex[cur_v]:
            new_dist = min_dist + nxt_dist
            if new_dist < dist[nxt_v]:
                path[nxt_v] = cur_v
                dist[nxt_v] = new_dist
                heappush(pq, (new_dist, nxt_v))

    trace = get_trace(path, e)
    return dist[e], trace


n = int(input().rstrip())
m = int(input().rstrip())

vertex = [[] for _ in range(n + 1)]
for _ in range(m):
    v1, v2, t = map(int, input().split())  # v1 <-> v2: 양방향 t
    vertex[v1].append((v2, t))
    vertex[v2].append((v1, t))

s, e = map(int, input().split())
dist, trace = dijkstra(s, e)

# 정답 출력
print(dist)
print(len(trace))
print(*trace)

정답 코드 (수정 내용: 단방향)

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def get_trace(path, e):
    trace = []
    curr = e
    while curr != -1:
        trace.append(curr)
        curr = path[curr]

    return trace[::-1]


def dijkstra(s, e):
    INF = float('inf')
    dist = [INF for _ in range(n + 1)]
    path = [-1 for _ in range(n + 1)]

    dist[s] = 0
    pq = [(0, s)]
    while pq:

        min_dist, cur_v = heappop(pq)
        if min_dist != dist[cur_v]:
            continue

        if cur_v == e:
            break

        for nxt_v, nxt_dist in vertex[cur_v]:
            new_dist = min_dist + nxt_dist
            if new_dist < dist[nxt_v]:
                path[nxt_v] = cur_v
                dist[nxt_v] = new_dist
                heappush(pq, (new_dist, nxt_v))

    trace = get_trace(path, e)
    return dist[e], trace


# 입력 부분
n = int(input().rstrip())
m = int(input().rstrip())

# 풀이 부분
vertex = [[] for _ in range(n + 1)]
for _ in range(m):
    v1, v2, t = map(int, input().split())  # v1 <-> v2: 양방향 t
    vertex[v1].append((v2, t))

s, e = map(int, input().split())
dist, trace = dijkstra(s, e)

# 정답 출력
print(dist)
print(len(trace))
print(*trace)

Reference

• https://jun9985.tistory.com/76

함께 풀면 좋은 문제들

• https://www.acmicpc.net/problem/1719
• https://www.acmicpc.net/problem/31230
• https://www.acmicpc.net/problem/5719

문제 링크 - 백준 1937 욕심쟁이 판다

해결 과정

이 문제를 읽고 나서 바로 그래프 문제라는 것을 깨달았다. 판단 근거는 다음과 같다.

1. 상, 하, 좌, 우 이동해야한다.
2. 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다는 조건 즉, 현재 노드와 다음 노드를 비교해야한다.
3. 주어진 조건으로 최대한 많은 칸을 움직여야한다.

사고 과정 (1) ❗️

그래프 문제라는 것을 깨달았고, 한 노드에서 시작하여 갈 수 있는 최대한 많은 칸을 가야하기 때문에 DFS 탐색 자료구조를 사용하기로 결심했다. DFS를 사용한 로직은 다음과 같다.

1. 최댓값을 전역으로 선언한다.
2. 모든 노드를 방문하며 DFS 탐색을 실행한다. 방향성이 정해져있기 때문에 방문 여부는 따로 체크하지 않는다.
3. 범위를 넘지않고, 현재 노드보다 다음 노드가 더 큰 경우에만 이동하도록 하고, 계속해서 전역으로 선언한 최댓값을 갱신해준다.
4. 모든 탐색을 끝난 후, 최댓값을 출력한다.

이러한 로직으로 제출한 결과, 시간초과 & 메모리 초과 판정을 받았다. 처음에는 이해가 가지 않았다. 완전 탐색을 하긴 했지만, n의 범위가 1 ≤ n ≤ 500 이었고, 경로에 대한 시간 복잡도는 대략 500 x 500 = 250,000 정도이다. 방향성이 큰 값을 향해서만 가도록 정해져있기 때문에 각 노드마다 4방향 탐색을 하더라도 충분할 것이라고 생각했는데, 내가 판단을 잘못했다.

위 그림에서 각 숫자들이 노드 번호라고 할 때, 1번 노드만 생각하자. 상, 하, 좌, 우 범위를 넘지않고, 큰 값만을 찾아가기 위해서 정말 여러 방향으로 움직이며 16을 향해 갈 것이다. 탐색을 끝내고, 2번 노드로 움직여서 다시 DFS 탐색을 하려고 한다면, 1번 노드에서 시작했던 것과 거의 비슷하게 움직일 것이다. 이 MAP이 500 x 500 이라고 생각한다면 정말 많은 탐색을 할 것으로 예상된다.

위 그림 예시를 처음 작성한 코드로 실행하고, 함수 내 동작 횟수를 다음과 같은 코드로 카운팅 해봤다.

def dfs(cur_y, cur_x, cnt):
    global MAX, total_move

    total_move += 1 # 동작 횟수 증가 
    MAX = max(MAX, cnt)
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        if 0 <= nxt_y < n and 0 <= nxt_x < n and MAP[cur_y][cur_x] < MAP[nxt_y][nxt_x]:
            dfs(nxt_y, nxt_x, cnt + 1)

그 결과 총 546번 의 탐색을 실행한 것을 확인할 수 있었다. 죽, 4 x 4 = 16 이 아니라 4 x 4 MAP임에도 불구하고 500번이 넘는 탐색을 한 것이다. 500 x 500 MAP 에서 시간초과가 나는 현상은 지극히 당연한 결과였다.

사고 과정 (2) ‼️

시간초과가 났던 원인은 방문 처리를 하지 않았기 때문이다. 즉, 선언했던 dp 2중 리스트를 전혀 사용하고 있지 않아서 생긴 문제였다. 다이나믹 프로그래밍 기법을 같이 적용하려고 하니, 감이 아예 잡히지 않아 이를 잘 풀이한 블로그를 찾아서 공부했다. 메모이제이션을 활용하여 DFS 탐색을 하면서도 현재 위치에서 최대로 뻗어나갈 수 있는 최대 노드 개수를 지속적으로 갱신해보자. 그러면 방문했던 곳을 재방문 시 해당 노드에 저장된 값을 통해 더 이상의 탐색을 하지 않아도 되므로 시간 절약을 할 수 있다.

0. 전역으로 최댓값을 1로 초기화한다.
1. 모든 노드를 탐색하지만, dp값이 -1(초기값)인 경우에만 DFS 탐색을 한다.
2. cnt 값을 1로 설정하고, dfs를 돌때마다 다음 노드의 dp값을 return 받으면서 cnt값에 더해주도록 한다. 만약 다음 노드를 어디선가 방문하여 -1값이 아니라면, 해당 노드에 저장된 값을 바로 return 받는다.
3. 재귀를 거듭하면서 저장된 dp값을 계속 return 받으면서 최초의 시작 노드에는 가장 큰 값이 저장되게 된다. 재귀 과정에서 전역으로 선언한 최댓값을 계속 갱신해준다.
4. 최댓값을 갱신한다.

DFS 탐색은 아무래도 재귀 자료구조이기 때문에 추론하기가 좀 힘든 것 같다. 따라서 정확한 동작 방식을 이해하는 것이 중요하다. 또한, DFS 탐색과 DP 알고리즘이 결합된 문제들이 기업 코테에서도 종종 등장하기 때문에 이와 같은 유형의 문제를 충분히 풀어보는 것도 중요한 것 같다.

DP 알고리즘을 적용하니, 정답 판정을 받았다!

코드

오답 코드 (시간 초과 & 메모리 초과)

from sys import stdin, setrecursionlimit

setrecursionlimit(25 * (10 ** 4))
input = stdin.readline


def dfs(cur_y, cur_x, cnt):
    global MAX

    MAX = max(MAX, cnt)
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        if 0 <= nxt_y < n and 0 <= nxt_x < n and MAP[cur_y][cur_x] < MAP[nxt_y][nxt_x]:
            dfs(nxt_y, nxt_x, cnt + 1)


n = int(input().rstrip())

MAP = [list(map(int, input().split())) for _ in range(n)]

MAX = 0
dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(n):
    for j in range(n):
        dp = [[-1 for _ in range(n)] for _ in range(n)]
        dfs(i, j, 1)

print(MAX)

정답 코드

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 8)
input = stdin.readline


def dfs(cur_y, cur_x):
    global MAX

    if dp[cur_y][cur_x] != -1:
        return dp[cur_y][cur_x]

    dp[cur_y][cur_x] = 1  # 기본 방문 체크
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        # 범위를 넘지 않고, 현재 위치의 대나무보다 다음 위치의 대나무가 더 많다면 -> 탐색
        if 0 <= nxt_y < n and 0 <= nxt_x < n and MAP[cur_y][cur_x] < MAP[nxt_y][nxt_x]:
            cnt = 1
            cnt += dfs(nxt_y, nxt_x)
            dp[cur_y][cur_x] = max(dp[cur_y][cur_x], cnt)
            MAX = max(MAX, dp[i][j])

    return dp[cur_y][cur_x]


n = int(input().rstrip())
MAP = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1 for _ in range(n)] for _ in range(n)]

MAX = 1
dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(n):
    for j in range(n):
        if dp[i][j] == -1:
            dfs(i, j)

print(MAX)

Reference

• https://m.blog.naver.com/sosow0212/223004187291
• https://minny27.tistory.com/42

문제 링크 - 백준 30969 진주로 가자! (Hard)

해결 과정

이 문제는 문제만 읽었을 때는 정말 쉬운 문제이다.

사고 과정 (1) ❗️

문제를 읽어보면 해결방법은 다음과 같다.

1. 입력을 모두 받고, 교통 요금에 해당하는 값들만 리스트에 저장한다.
2. jinju 라는 교통편을 찾았다면, 해당 요금을 변수에 따로 저장한다.
3. 모든 교통 요금을 저장한 리스트에서 jinju 교통편의 교통 요금보다 높은 값들의 개수를 센다.

처음에는 위와 같은 방식으로 문제를 풀었다. 그러나, 메모리 초과 라는 결과를 얻었다. 그래서 문제의 조건을 살펴보니 메모리 제한이 16MB 이다. 즉, int 정수 하나가 4Byte를 차지하고, 대략적으로 16MB = 16,000KB = 16,000,000B 이므로 4,000,000 개의 정수를 저장할 수 있다. 하지만, 주어지는 교통편의 개수의 최댓값은 1 ≤ N ≤ 5,000,000 이기 때문에 메모리 초과가 나는 것이었다. 따라서 해결 방법을 다시 생각해야했다. 어떻게 저장을 덜 하고, 문제를 해결할 수 있을까? 언제 jinju 라는 교통편이 나올지 모르기 때문에 입력은 우선, 모두 받아서 저장은 해야한다. (그래야 비교를 할 수 있기 때문에) 20분 동안 생각해도 방법이 생각나지 않아, 블로그를 탐색했다.

사고 과정 (2) ‼️

중요한 사고 과정을 알 수 있었다. 문제에서 주어진 jinju 교통편의 요금은 최대 1,000이다. 다른 교통편의 교통요금으로 주어질 수 있는 최댓값은 10^15이다. 즉, jinju 교통편의 요금보다 크냐 작냐를 비교 하기 위해서는 1,000보다 작냐, 크냐만 따지면 되는 것이었다. 이 문제를 해결하기 위한 방법의 핵심은 마치 계수 정렬 아이디어와 같다.

1. 우선, 1,002 개의 원소를 담을 수 있는 리스트를 선언한다.
2. 1,000 미만인 요금들은 각 인덱스에 맞는 곳에 값을 1씩 증가하고, 1,000을 초과하는 값들은 그냥 1,001 인덱스를 가진 곳에 값을 1씩 증가시키면 된다.
3. 모두 저장을 하고 나면, jinju 교통편의 교통 요금에 해당하는 값보다 뒤에 있는 값들을 모두 더한 값이 문제에서 요구하는 정답이 된다.

그저 5,000,000개의 값들을 어떻게 컨트롤할 수 있을까에 집중하고 있었지만, 문제를 해결할 수 있는 key는 교통 요금의 범위에 있었다. 이 문제를 통해서 계수 정렬의 아이디어를 다시 떠올릴 수 있었고, 그 아이디어를 응용해서 정렬이 아닌 다른 문제에 적용하여 풀 수 있다는 것에 큰 깨달음을 얻었다.

정답은 늘 짜릿하다!

코드

오답 코드 (메모리 초과)

from sys import stdin

input = stdin.readline

n = int(input().rstrip())  # n: 교통편의 개수

dic = {}
for _ in range(n):
    d, c = input().split()  # d: 도착지, c: 요금
    dic[d] = int(c)

cnt = 0
for city, cost in sorted(dic.items(), key=lambda x: x[1]):
    if city == "jinju":
        cnt += 1
        break
    cnt += 1

print(dic["jinju"])
print(n - cnt)

정답 코드

from sys import stdin

input = stdin.readline

LEN = 1_001

n = int(input().rstrip())  # n: 교통편의 개수
cost = None
lst = [0 for _ in range(LEN + 1)]
for _ in range(n):
    d, c = input().split()
    lst[min(1001, int(c))] += 1

    if d == "jinju":
        cost = int(c)

cnt = 0
for num in range(cost + 1, LEN + 1):
    cnt += lst[num]

print(cost)
print(cnt)

Reference

• https://mshun.tistory.com/77

개요 💁🏻‍♂️

JWT 토큰 방식으로 회원가입, 로그인, 로그아웃 기능을 구현했습니다. 구현한 내용 중에서 회원가입한 회원인지, 아닌지에 대해서 @RequsetHeader("Authorization") String token 코드를 통해서 Bearer 타입의 JWT 토큰을 받고, 이를 Service로 넘겨 Payload 내용을 확인하여 실제 유저인지 아닌지 체크하는 과정을 거칩니다.

    public void logout(String token) {

        if (!jwtTokenProvider.validateToken(token)) {
            throw new CustomException(Code.ACCESS_TOKEN_UNAUTHORIZED);
        }

        String nickname = jwtTokenProvider.getSubject(token);
        log.info("logout nickname check: {}", nickname);

        Member member = memberRepository.findByNickname(nickname).orElseThrow(
                () -> new CustomException(Code.NOT_EXIST_NICKNAME));

        refreshTokenRepository.delete(member.getId());
    }

위 사진과 같이 구현했을 때, 항상 의문이 들었던 점은 유저만 사용할 수 있는 모든 메소드에 해당 로직을 통해서 유저인지 확인하는 코드를 작성해야할까? 였습니다. 검색해 본 결과 해결할 수 있는 방법으로 Argument Resolver 라는 방식을 알게 되었습니다. Argument Resolver를 알아보기 전에 먼저 Binding 개념에 대해서 알아봅시다.

대표적인 Binding 방식

웹개발에서 바인딩(Binding)이란, 어떤 값들을 변수에 묶어버리는 것을 의미합니다. 대표적으로 3가지 바인딩 방식이 있습니다.

1. @RequestBody - HTTP Body를 변수에 바인딩하기 위해 사용되는 어노테이션

    @PostMapping("/restaurants")
    public CommonResponse<?> createRestaurant(@RequestBody RestaurantCreateRequest restaurantCreateRequest) {
        restaurantService.createRestaurant(new RestaurantCreateParam().of(restaurantCreateRequest));
        return CommonResponse.of(Code.OK);
    }

2. @RequestParam - Controller에서 쿼리 스트링을 변수에 바인딩하기 위해 사용되는 어노테이션

    @GetMapping("")
    public CommonResponse<?> readRestaurants(@RequestParam(value = "keyword", required = false) String keyword) {
   
        List<RestaurantItemResponse> restaurantItemResponses = restaurantService.readRestaurants(keyword);
   
        return CommonResponse.of(restaurantItemResponses);
    }

3. @PathVariable - 가변적인 경로를 변수에 바인딩하기 위해 사용되는 어노테이션

    @DeleteMapping("/{id}/restaurants")
    public CommonResponse<?> deleteRestaurant(@PathVariable Long id) {
        restaurantService.deleteRestaurant(id);
        return CommonResponse.of(Code.OK);
    }

그 외 Binding 방식

대표적인 바인딩 방식 이외에도 HTTP Header, Session, Cookie 등 직접적이지 않은 방식 혹은 외부 데이터 저장소로부터 데이터를 바인딩해야할 때가 있는데, 이때 사용되는 것이 Argument Resolver 입니다. Argument Resolver를 사용하면 Controller Method Parameter 중에서 특정 조건에 맞는 Parameter가 있다면, 요청에 들어온 값을 이용해 원하는 객체를 만들어 바인딩해줄 수 있습니다.

정리해보자면 Argument Resolver(HandlerMethodArgumentResolver)는 Spring MVC에서 Controller Method의 Parameter를 자동으로 변환하고 주입해주는 편의를 제공해줍니다. 따라서, Argument Resolver 단에서 JWT Token의 Payload를 먼저 읽어 유저의 식별자를 추출하고, 해당 유저가 존재한다면 유저 Entity를 반환하고, 아니면 예외를 처리할 수 있습니다. 이로써 불필요한 인증 과정의 중복성을 줄여 보다 더 서비스 로직을 구현하는데 집중할 수 있습니다.

• Controller 단에서 중복되는 코드들을 깔끔하게 처리할 수 있다.
• Controller로 들어오는 Parameter를 가공하거나 수정하여 제공할 수 있다.

동작 방식

동작 방식은 위 사진과 같다.

1. Client 요청
2. Dispatcher Servlet에서 해당 요청 처리
3. Client 요청에 대한 HandlerMapping 처리 3-1. RequestMapping 처리 (RequestMappingHandlerAdapter 수행) 3-2. Intercepter 처리 3-3. Argument Resolver 처리 (실행 지점) 3-4. Message Converter 처리
4. Controller Method Invoke

예제 코드

Argument Resolver에 대한 개념과 동작 방식에 대해서 알았으니, 예제 코드를 확인해보도록 하자. 우선, Argument Resolver를 Spring FW에서 구현하기 위해서는 파라미터를 통해 바인딩 될 객체를 @interface로 만들어야 합니다.

@Target(ElementType.PARAMETER)
@Retention(RetentionPolicy.RUNTIME)
public @interface UserArg {
}

그 다음, HandlerMethodArgumentResolver 인터페이스를 상속받은 Custom ArgumentResolver를 구현해줍니다.

@Slf4j
@Component
@RequiredArgsConstructor
public class UserArgumentResolver implements HandlerMethodArgumentResolver {

    private final JwtTokenInterceptor jwtTokenInterceptor;
    private final JwtTokenProvider jwtTokenProvider;
    private final MemberRepository memberRepository;

    @Override
    public boolean supportsParameter(MethodParameter parameter) {
        return parameter.hasParameterAnnotation(UserArg.class);
    }

    @Override
    public Member resolveArgument(MethodParameter parameter,
                                  ModelAndViewContainer mavContainer,
                                  NativeWebRequest webRequest,
                                  WebDataBinderFactory binderFactory) throws Exception {

        HttpServletRequest request = webRequest.getNativeRequest(HttpServletRequest.class);
        String token = jwtTokenInterceptor.resolveToken(request);
        String nickname = jwtTokenProvider.getSubject(token);

        log.info("resolver nickname: {}", nickname);
        return memberRepository.findByNickname(nickname).orElse(null);
    }
}

그 다음, 열심히 만든 Custom ArgumentResolver를 WebMvcConfigurer에 저장해줍니다.

@Configuration
@RequiredArgsConstructor
public class ResolverWebconfig implements WebMvcConfigurer {

    private final UserArgumentResolver userArgumentResolver;

    @Override
    public void addArgumentResolvers(List<HandlerMethodArgumentResolver> argumentResolvers) {
        argumentResolvers.add(userArgumentResolver);
    }
}

테스트

    @GetMapping("/api/test")
    public CommonResponse<?> test(@UserArg Member member) {
        return CommonResponse.of(member);
    }

@UserArg 어노테이션이 붙은 Parameter에 대해서 Argument Resolver가 바인딩 해주기 때문에 Controller에서는 바인딩된 객체를 그냥 사용해주면 됩니다.

위 사진과 같이 Postman 테스트 결과 정상적으로 Member Entity의 정보를 가져오는 것을 확인할 수 있습니다.

Reference

• https://maenco.tistory.com/entry/Spring-MVC-Argument-Resolver%EC%99%80-ReturnValue-Handler
• https://velog.io/@uiurihappy/Spring-Argument-Resolver-적용하여-유저-정보-불러오기
• https://kangworld.tistory.com/289
• https://blog.neonkid.xyz/238
• https://hudi.blog/spring-argument-resolver/

문제 링크 - 백준 1016 제곱 ㄴㄴ 수

해결 과정

문제가 정말 짧고 간결하지만, 쉽지 않은 문제였다. 우선, 주어진 min 제한 범위로 인하여 당황했다. 10^12 이기 때문에 O(√min) 이내로 반드시 해결해야한다.

사고 과정 (1) ❗️

처음에는 에라토스테네스의 체 알고리즘을 적용했다. 알고리즘을 적용하여 2 ~ √max 까지의 모든 소수를 구한다. √max 까지의 소수를 구하는 이유는 제곱수를 제거하기 위함이다. 즉, (√max) ** 2 = max 를 사용하는 것이다. 그래서 나는 해당 로직을 통해 구한 소수들을 이용해서 min ≤ num ≤ max 인 num에 대해서 모든 prime 들에 대해서 탐색해보고자 했다.

num값보다 작거나 같으면서, 해당 num값의 제곱수로 나누어진다면 그 개수를 증가시켰다. 그 결과는 바로 시간 초과 였고, 시간 초과가 나지 않았더라도 오답이었을 것이다. 그 이유는 다음과 같다.

2 ~ (10^12 + 10^6) 까지의 소수의 개수는 78_498개이고, min ~ max 사이의 숫자는 최대 10^6이기 때문에 시간 초과가 난 것이다. 또한, 제곱수만 생각하고, 제곱수의 배수는 생각하지 않았기 때문에 시간 초과가 나지 않았더라도 오답이다.

사고 과정 (2) ‼️

곰곰히 생각해보았지만, 별다른 아이디어가 떠오르지 않아서 여러 블로그를 찾아보았다. 너무 에라토스테네스의 체 알고리즘에 꽂혀서 시야가 좁아졌던 것 같다. 이 문제를 풀기 위해서는 min ≤ num ≤ min + 1_000_000 을 알아차리는 것이 핵심이었다. 결국 탐색 범위는 10^6 이라는 점이다. 이 탐색 범위 내에서 에라토스테네스의 체 알고리즘이 간접적으로 반영된다. 풀이 과정은 다음과 같다.

min = 30, max = 100 이라고 하자.

1. 첫 제곱수인 (2 * 2)부터 시작하자. min 값에 대해서 min // (2 * 2) 값을 구한다.
2. 정확이 나누어 떨어지지 않는다면 몫 * (2 * 2) 값이 min값보다 작아지므로, 작아지는 것을 방지하기 위해서 나누어 떨어지지 않는다면 몫에 1을 더해준다. ex) 30 // 4 = 7 -> 8
3. 그 몫(8)과 제곱수(2 * 2)에 대해서 max까지 가능한 모든 제곱 수들을 방문 처리 해주고, cnt 값을 줄인다.
4. 이와 같은 과정을 (3 * 3), (4 * 4) ,,, (i * i) <= max 까지 반복한다.
5. 반복하는 과정에서 이미 방문 처리된(중복된) 값은 신경쓰지 않는 로직을 넣어준다.
6. cnt 값을 출력한다.

이를 구현하여 제출한 결과 정답 판정을 받았다! 골드1 문제는 역시 쉽지 않았다.

코드

오답 코드 (시간 초과)

from sys import stdin
from math import isqrt

input = stdin.readline

LEN = isqrt(10 ** 12 + 10 ** 6)
sieve = [False, False] + [True] * (LEN - 1)
for i in range(2, isqrt(LEN) + 1):
    if sieve[i]:
        for j in range(i * i, LEN + 1, i):
            sieve[j] = False  # 합성수 제거

primes = [i for i in range(2, LEN + 1) if sieve[i]]

mn, mx = map(int, input().split())

cnt = 0
for num in range(mn, mx + 1):
    for prime in primes:
        if (prime ** 2) <= num and num % (prime ** 2) == 0:
            cnt += 1
            break

ans = mx - mn + 1 - cnt
print(ans)

정답 코드

from sys import stdin

input = stdin.readline

mn, mx = map(int, input().split())

LEN = 10 ** 6
sieve = [True for _ in range(LEN + 1)]

cnt = mx - mn + 1

for i in range(2, mx + 1):
    if i ** 2 > mx:
        break

    qt = mn // (i ** 2) if mn % (i ** 2) == 0 else (mn // (i ** 2)) + 1
    while qt * (i ** 2) <= mx:
        if sieve[qt * (i ** 2) - mn]:
            sieve[qt * (i ** 2) - mn] = False  # 제곱 ㅇㅇ 수
            cnt -= 1

        qt += 1

print(cnt)

Reference

• https://www.youtube.com/watch?v=l9jU0Is7kek
• https://baehoon.tistory.com/77

문제 링크 - 백준 1600 말이 되고픈 원숭이

해결 과정

문제를 읽어보면 그래프 문제라는 것이 조건들로부터 와닿는다.

1. 인접한 칸(상, 하, 좌, 우)으로 이동
2. 말은 체스의 나이트와 같은 이동방식을 가진다.(그래프 문제에서 자주 등장)

문제를 요약하자면 최대 k번까지 말처럼 움직일 수 있고, 말처럼, 원숭이처럼 움직여서 (0, 0) -> (h - 1, w - 1) 위치로 도달할 수 있는 최소한의 동작 횟수를 반환하는 문제이다.

사고 과정 (1) ❗️

처음에 나는 가중치가 없는 그래프에도 불구하고, 다익스트라 알고리즘을 선택했다. 그 이유는 방문과 관련된 이슈 때문이었다. 그냥 내가 어느 위치를 방문했는데, 그 위치에 같은 횟수로 움직였지만 원숭이처럼 움직여서 도착했을 수도 있고, 말처럼 움직여서 갔을 수도 있기 때문에 방문이라는 개념을 없애기 위해 다익스트라 알고리즘을 떠올렸다. 멋있게 한방에 코드를 작성해서 제출했지만 틀렸다. 이것은 잘못된 생각이었다. 다음과 같은 테스트 케이스를 보자.

2
8 12
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 1 1 0 0 0 0 0
0 1 1 0 1 1 1 1
0 1 1 0 1 1 1 1
0 1 1 0 0 0 0 0
0 1 1 0 1 1 1 0
0 1 1 1 1 1 1 0
1 1 0 0 0 0 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 0 0

위 테스트 케이스에 대한 나의 다익스트라 코드의 실행 결과는 다음과 같다.

왼쪽 그림처럼 움직여야 하지만, 실제로는 (9, 5) -> (11, 6) 으로 이동하지 못한다. 왜냐하면 다익스트라 알고리즘을 거리를 기준으로 최소힙으로 구현했기 때문이다. 즉, 이미 앞에서 말처럼 이동하여 빠르게 어떤 위치에 도달했다면 원숭이처럼 움직여서는 거리 갱신이 안되기 때문에 말처럼 움직일 수 있는 횟수가 있음에도 사용하지 못하는 상황이 발생되는 것이다.

사고 과정 (2) ‼️

다 풀었다고 생각했지만, 마주친 오답으로 인하여 멘붕이 왔다.이를 어떻게 해결하면 좋을지 생각하기 위해서 열심히 구현한 코드를 우선 지웠다. 백지에서부터 다시 시작했다. 10분 정도 생각하다가 이런 생각이 들었다. 어떤 위치에서는 말처럼 움직인 횟수가 0번, 1번, 2번, ,,, , k번 움직여서 도착한다. 라는 생각이 들면서 [ 벽 부수고 이동하기 ] 문제가 생각났다. 이 문제에서는 벽을 부셔서 움직인 방문과 부시지 않고 움직인 방문을 별도로 기록하도록 구현하는 문제이다. 즉, 3중 리스트 또는 배열을 사용해야한다. 이 문제를 풀었던 경험을 토대로 해당 문제에 적용해보기로 했다. 과감하게 각 위치마다 k+1 개의 칸을 만들었다. 즉, 이전 위치에서 현재 위치로 왔을 때, 말처럼 움직인 횟수가 0번부터 k번까지 다양하게 접근할 수 있도록 한다. 해당 횟수로 이동했을 때, 이미 방문한 경험이 있다면 이미 해당 횟수를 사용하여 최단 거리로 방문한 것이기에 탐색을 포기한다.

(k+1) 칸의 방문 칸을 만들었을 때, 각 칸이 뜻하는 의미는 위 사진과 같다. 이러한 개념을 도입하고, 가중치가 1임을 이용해서 BFS 알고리즘을 구현했더니

정답 판정을 받았다!

코드

오답 코드 (Dijkstra)

from sys import stdin
from heapq import heappush, heappop

input = stdin.readline


def in_range(y, x):
    return 0 <= y < h and 0 <= x < w


def dijkstra():
    INF = float('inf')
    dist = [[INF for _ in range(w)] for _ in range(h)]

    dist[0][0] = 0  # 출발 지점 초기화
    pq = [(0, 0, 0, 0)]
    dhys, dhxs = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]
    dmys, dmxs = [-1, 1, 0, 0], [0, 0, -1, 1]
    while pq:

        min_dist, cur_y, cur_x, k_cnt = heappop(pq)

        # 이미 갱신되었다면 무시
        if min_dist != dist[cur_y][cur_x]:
            continue

        if cur_y == h - 1 and cur_x == w - 1:
            return dist[cur_y][cur_x]

        if k_cnt < k:
            for dy, dx in zip(dhys, dhxs):
                nxt_y, nxt_x = cur_y + dy, cur_x + dx
                if in_range(nxt_y, nxt_x) and MAP[nxt_y][nxt_x] != 1:
                    new_dist = min_dist + 1
                    if new_dist < dist[nxt_y][nxt_x]:
                        dist[nxt_y][nxt_x] = new_dist
                        heappush(pq, (new_dist, nxt_y, nxt_x, k_cnt + 1))

        for dy, dx in zip(dmys, dmxs):
            nxt_y, nxt_x = cur_y + dy, cur_x + dx
            if in_range(nxt_y, nxt_x) and MAP[nxt_y][nxt_x] != 1:
                new_dist = min_dist + 1
                if new_dist < dist[nxt_y][nxt_x]:
                    dist[nxt_y][nxt_x] = new_dist
                    heappush(pq, (new_dist, nxt_y, nxt_x, k_cnt))

    return -1


k = int(input().rstrip())
w, h = map(int, input().split())
# 0: 평지, 1: 장애물
MAP = [list(map(int, input().split())) for _ in range(h)]

ans = dijkstra()
print(ans)

정답 코드 (BFS)

from sys import stdin
from collections import deque

input = stdin.readline


def in_range(y, x):
    return 0 <= y < h and 0 <= x < w


def bfs():
    visited = [[[False] * (k + 1) for _ in range(w)] for _ in range(h)]
    visited[0][0][0] = 0  # 출발점 방문 처리 [y][x][k]
    dq = deque([(0, 0, 0, 0)])

    while dq:
        cur_y, cur_x, dist, k_cnt = dq.popleft()

        if cur_y == h - 1 and cur_x == w - 1:
            return dist

        # 원숭이가 말처럼 이동할 수 있는 경우
        if k_cnt < k:
            for dy, dx in zip(dhys, dhxs):
                nxt_y, nxt_x = cur_y + dy, cur_x + dx
                # 방문 가능하거나, 장애물이 아닌 경우
                if in_range(nxt_y, nxt_x) and not visited[nxt_y][nxt_x][k_cnt + 1] and MAP[nxt_y][nxt_x] != 1:
                    visited[nxt_y][nxt_x][k_cnt + 1] = True  # 방문 처리
                    dq.append((nxt_y, nxt_x, dist + 1, k_cnt + 1))

        # 원숭이가 원숭이처럼 이동할 수 있는 경우
        for dy, dx in zip(dmys, dmxs):
            nxt_y, nxt_x = cur_y + dy, cur_x + dx
            # 방문 가능하거나, 장애물이 아닌 경우
            if in_range(nxt_y, nxt_x) and not visited[nxt_y][nxt_x][k_cnt] and MAP[nxt_y][nxt_x] != 1:
                visited[nxt_y][nxt_x][k_cnt] = True  # 방문 처리
                dq.append((nxt_y, nxt_x, dist + 1, k_cnt))

    return -1


k = int(input().rstrip())
w, h = map(int, input().split())
# 0: 평지, 1: 장애물
MAP = [list(map(int, input().split())) for _ in range(h)]

dhys, dhxs = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]
dmys, dmxs = [-1, 1, 0, 0], [0, 0, -1, 1]
ans = bfs()
print(ans)

Reference

• https://moonsbeen.tistory.com/181

문제 링크 - 백준 1644 소수의 연속합

해결 과정

이 문제를 해결하기 위해서 좀 긴 시간을 고민했다. 우선, 1 <= N <= 4_000_000 인 범위에서 소수만을 구하는 것은 에라토스테네스의 체 알고리즘을 통해 빠르게 구할 수 있다. 그러면 연속된 소수들의 합으로 나타낼 수 있는 경우의 수는 어떻게 구할 것인가... O(N^2)으로는 절대 해결이 안될 것이다.

사고 과정 (1) ❗️

처음에는 투 포인터 기법을 활용해서 문제를 접근했다. left, right 변수를 두어 양쪽 변수들을 조절하면서 경우의 수를 구하려고 했다.

1. left = 0, right = N 으로 둔다.
2. 0번째 소수부터 쭉 더해가면서 N보다 커지기 직전까지 구한다.
3. 같다면 -> 경우의 수를 카운트해준다. / 더 커졌다면 -> 해당 위치로 right 값을 갱신한다.
4. left 값을 오른쪽으로 한 칸 움직이면서 1번부터 다시 반복한다.

이렇게 풀이해보려고 했으나, 구현하는 부분에서 큰 어려움을 느꼈다.

사고 과정 (2) ‼️

그래서 나는 연속된 이라는 단어에 집중했다. 연속된 소수합이라는 것을 곱씹어보니 떠오르는 단어가 하나 있었다. 그것은 바로 구간합 이었다. 우선, 구간합을 다 구하기에는 4_000_000까지의 소수가 283,146 개가 있으므로 시간 복잡도가 너무 높고, 계산량이 너무 많으므로 시간초과가 날 것이다. 그래서 생각한 것은 다음과 같다.

1. 어차피 연속합을 구하는 것이기 때문에, 첫번째 소수인 2부터 계속 더해가다보면 얼마 안 있어 4_000_000보다 커질 것이다. 즉, 시간 복잡도가 절대 283,146개의 소수를 전부 확인하지 않을 것이므로 충분할 것이다.
2. 2부터 계속 더해가면서 각 dp 배열에 해당 연속합으로 나올 수 있는 경우를 1개씩 증가시켜주고, 최종적으로는 그냥 dp[n] 에 저장된 값을 출력하자.

위 사진과 같이 실제로, 최초의 소수인 2부터 계속 소수들만 더해갔을 때, 1040번째 소수인 8291까지의 연속합이 3_999_326이다. 즉, 2중 for 문을 돌려보아도 1000^2 = 10^6 격이다. 연속합의 시작 위치가 높아질수록 인덱스는 더욱 빠르게 증가하기 때문에 시간 복잡도가 더욱 줄어들 것이 확실했다. 이를 토대로 코드를 구현해보니 정답 판정을 받을 수 있었다!

코드

정답 코드

from sys import stdin
from math import isqrt

input = stdin.readline

LEN = 4_000_000
# 에라토스테네스의 체 구현
sieve = [False, False] + [True] * (LEN - 1)
for i in range(2, isqrt(LEN) + 1):
    if sieve[i]:
        for j in range(i * i, LEN + 1, i):
            sieve[j] = False  # 합성수 제거

primes = [i for i in range(2, LEN + 1) if sieve[i]]
dp = [0 for _ in range(LEN + 1)]
n = int(input().rstrip())

for i in range(len(primes)):
    SUM = 0
    for j in range(len(primes)):
        # 범위를 넘거나, 최댓값을 뛰어넘는다면 break
        if i + j >= len(primes) or SUM + primes[i + j] > LEN:
            break
        SUM += primes[i + j]
        dp[SUM] += 1

print(dp[n])

유형: 에라토스테네스의 체 + DP(구간합 개념)

Reference

• 내 머리

문제 링크 - 백준 9184 신나는 함수 실행

해결 과정

문제를 보자마자 바로 재귀 개념이 들어갈 것임을 알 수 있었다. 재귀의 구조를 파악하기 위해서 w(2, 2, 2)를 직접 종이에 적어봤다. 숫자가 낮음에도 불구하고, 재귀 깊이가 상당히 길어지고, 재귀 횟수가 상당하다는 것을 느낄 수 있었다. 이 느낌은 마치 대표적인 다이나믹 프로그래밍 문제인 피보나치 함수 를 메모이제이션 방법으로 풀이하는 것과 같은 느낌이었다.

사고 과정 (1) ❗️

메모이제이션 방식을 사용하는 것까지 느낌이 왔지만, 문제는 다이나믹 프로그래밍을 어떻게 적용시킬까 였다. 손으로 직접 써내려가는 것은 불가능했고, 머릿속으로 곰곰히 생각해봤지만 딱히 마땅한 풀이 과정이 떠오르지 않았다. 알고리즘 분류를 봐도 역시나 재귀, 다이나믹 프로그래밍 이라는 정보 말고는 얻을 수 있는 게 없었다. 결국 해설이 잘 된 블로그를 하나 찾아서 공부했다.

사고 과정 (2) ‼️

문제에서 주어진 재귀 함수가 있기 때문에 이를 그대로 사용하면서 메모이제이션 기법을 적용하면 됐다. 나는 메모이제이션 개념을 잘 알지 못하고 있었던 것 같다.

메모이 제이션이란, 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 
이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 
동적 계획법의 핵심이 되는 기술이다.

출처: https://ko.wikipedia.org/wiki/메모이제이션

이러한 메모이제이션 개념을 적용해보자. 전략은 다음과 같다.

1. 처음 방문하는 곳이면 계산을 통해 얻은 값을 메모리(배열 또는 리스트)에 저장한다.
2. 재방문을 할 경우, 해당 값을 다시 계산하는 것이 아니라 저장된 값을 불러온다.

여기서 바로 3중 dp 배열이 도입된다. 사실 1차원, 2차원 dp 배열은 자주 봤어도 3중 dp 배열은 처음 보았다. 그래서 접근을 쉽게 하지 못한 것 같기도 하다. 너무 스스로에 대한 생각을 한계로 두지 말자 문제의 조건 중에서 -50 <= a, b, c <= 50 이라고 주어져서 3중 dp 배열을 각각 50개로 둬야 한다고 생각할 수 있지만, w 함수를 잘 살펴보면 a, b, c 변수 중 하나라도 20이 넘어가면 w(20, 20, 20) 을 호출한다. 즉, 각 3중 dp 각각 최대의 길이를 20으로 설정하면 된다. (실제로는 인덱싱을 편리하게 하기 위해서 21로 설정하자.)

세번째 elif 문을 살펴보면 다음과 같다.

elif dp[a][b][c] != 0:
    return dp[a][b][c]

이 함수가 메모이제이션의 정수이다. 즉, 이미 계산한 결과가 저장되어있으면(!= 0) 계산을 더 진행하지 않고, dp[a][b][c] 값을 return 하기만 하면 된다. 4번째, 5번째 if ~ else함수 역시 메모이제이션을 활용한 함수이다.

elif a < b < c:
    dp[a][b][c] = w( ~~ )
    return dp[a][b][c]

else:
    dp[a][b][c] = w( ~~ )
    return dp[a][b][c]

이 함수들은 조건에 맞는 함수식을 수행하되, 그 수행한 결과를 바로 dp[a][b][c] 에 저장하고, 그 값을 바로 return 하면 된다. 이렇게 메모이제이션을 적용하여 코드를 작성해서 제출한 결과는!

정답 판정을 받았다!

코드

정답 코드

from sys import stdin

input = stdin.readline


def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    elif dp[a][b][c] != 0:
        return dp[a][b][c]

    elif a < b < c:
        dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return dp[a][b][c]
    else:
        dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)
        return dp[a][b][c]


dp = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break

    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

Reference

• https://st-lab.tistory.com/190

문제 링크 - 백준 9466 텀 프로젝트

해결 과정

[ 백준 10451 순열 사이클 ] 이 문제와 뭔가 비슷한 느낌이 들어서 그래프 알고리즘으로 큰 가닥을 잡았다. 이 문제에서 특이한 조건은 바로 팀을 정하는 방식이다.

1. 스스로를 선택하여 1명이서 1팀을 이루는 조건
2. 사이클이 존재(1 -> 3 -> 4 -> 1)하여 여러 명의 사람이 1팀을 이루는 조건

스스로를 선택하여 혼자 팀하는 경우는 어떻게 구현하면 되겠다는 생각이 바로 들었지만, 사이클이 존재하여 1팀을 이루는 경우에 대해서는 좀 생각하는 시간이 오래 걸렸다.

사고 과정 (1) ❗️

우선, 사이클을 판단해야 한다는 생각에 여러 그래프 알고리즘 중에서 DFS 알고리즘을 선택했다. 그 이유는 다음과 같다.

1. 이 문제는 단방향 그래프이다. 즉, 한 노드에 여러 갈래가 존재하지 않고, 하나의 노드는 하나의 노드로만 향한다.
2. 사이클이 존재한다면, 깊이 탐색하다보면 결국 자기 자신이 나타난다.

이와 같은 이유로 BFS말고, DFS 알고리즘을 사용하기로 마음 먹었다. 우선, 문제에서 주어진 입력을 받고, vertex 라는 새로운 그래프를 구현했다. 단방향 그래프이기 때문에 i -> v 로 그래프를 구현했다. 또한, 그래프 문제에서 필수 요소인 visited 리스트 즉, 방문 여부를 판단하는 리스트를 만들었다. 전체적인 구현 내용은 다음과 같다.

1. 1번 노드부터 n번 노드까지 완전 탐색을 한다.

2. 해당 노드에 방문한 적이 없다면 1) 방문 처리 이후, 자기 자신(For 출발점 비교 대상)과 자기 자신(For 노드 탐색)을 가지고 DFS 탐색을 실행한다. 2) DFS 탐색 과정은 방문할 수 있는 가능한 노드를 깊게 탐색한다. 3) 만약 자기 자신이 나타난다면 탐색한 모든 노드를 방문 처리한 상태로 냅두고, 자기 자신이 나타나지 않는다면 방문 처리한 것을 다시 복원 처리한다.

3. 모든 노드를 탐색한 이후, visited 리스트에서 아직 방문하지 않은 노드 번호가 바로 팀을 이루지 못한 인원이기 때문에 이를 카운트해서 반환한다.

결론적으로 지금까지 진행한 풀이는 80%에서 시간초과가 발생했다. 내 생각에는 학생의 수가 2 <= n <= 100_000 이기 때문에 최악의 경우 O(N^2)으로 10^10 연산이 이루어져 시간초과가 난 것으로 생각된다. 이를 어떻게 해결하면 좋을까 ?

사고 과정 (2) ‼️

이를 해결하기 위해서 많은 고민을 해보았지만, 해결하지 못하여 여러 블로그와 질문 게시판을 찾아보았다.

내가 놓친 부분은 사이클에 포함되지 않은 노드에서 시작하여 사이클이 발생한 경우를 생각하지 못한 것이다.

즉, 위 그림의 왼쪽처럼 사이클이 발생할 수도 있지만, 오른쪽 그림처럼 사이클에 포함되지 않는 1번 노드에서부터 시작해서도 사이클의 존재를 파악할 수 있던 것이다. 그렇다면 이를 어떻게 구현하면 좋을까? 이를 구현하기 위해서 유명한 백트래킹 문제인 N과 M 풀이에서 조금 따오면 가능했다.

1. 1번 노드부터 n번 노드까지 완전 탐색을 한다.

2. 해당 노드에 방문한 적이 없다면 1) 혼자 팀을 이루는 경우는 미리 방문 처리를 하며, 전체 인원 수에서 1을 뺀다. 2) 그게 아닌 경우에는 방문 처리를 해준 뒤, cycle 이라는 리스트에 자기 자신을 담아 새롭게 만들어놓은 후에 DFS 탐색을 시작한다. 3) DFS 탐색에서는 다음 방문 가능한 노드를 cycle에 계속 추가해주면서 방문 처리를 해준다. 4) 그러다가 만약에 다음 노드가 이미 방문한 적이 있는 노드이면서, 현재까지 방문한 노드를 순서대로 저장한 cycle 리스트에 다음 노드가 존재하면 전체 인원 수에서 사이클의 길이만큼 빼준다. (index() 함수를 이용하는 테크닉이 필요하다.) 5) 방문한 노드는 맞지만, cycle 리스트에 존재하지 않는 노드 즉, 다른 DFS 탐색에서 이미 방문한 노드인 경우에는 그냥 return 해준다.

3. DFS 탐색을 하면서 사이클을 이루는 사람들은 전체 인원 수에서 다 빼줬기 때문에 그냥 반환한다.

위 과정을 통해서 시간초과인 문제를 해결할 수 있었다!

코드

오답 코드 (오답 및 시간 초과)

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 5)
input = stdin.readline


def dfs(start, cur_x):
    for nxt_x in vertex[cur_x]:
        if start == nxt_x:
            return True

        if not visited[nxt_x]:
            visited[nxt_x] = True  # 방문 처리
            flag = dfs(start, nxt_x)
            if not flag:
                visited[nxt_x] = False  # 복원 처리
            else:
                return True

    return False


t = int(input().rstrip())

for _ in range(t):
    n = int(input().rstrip())
    n_lst = list(map(int, input().split()))

    vertex = [[] for _ in range(n + 1)]
    visited = [False for _ in range(n + 1)]
    for i in range(n):
        vertex[i + 1].append(n_lst[i])  # i -> v 단방향

    for i in range(1, n + 1):
        if not visited[i]:
            visited[i] = True  # 방문 처리
            flag = dfs(i, i)
            if not flag:
                visited[i] = False  # 복원 처리

    cnt = 0
    for i in range(1, n + 1):
        if not visited[i]:
            cnt += 1

    print(cnt)

정답 코드 (개선)

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 5)
input = stdin.readline


def dfs(cur_x):
    global cnt

    for nxt_x in vertex[cur_x]:
        if visited[nxt_x]:
            if nxt_x in cycle:
                cnt -= len(cycle[cycle.index(nxt_x):])
            return

        else:
            visited[nxt_x] = True  # 방문 처리
            cycle.append(nxt_x)
            dfs(nxt_x)


t = int(input().rstrip())

for _ in range(t):
    n = int(input().rstrip())
    n_lst = list(map(int, input().split()))

    cnt = n
    vertex = [[] for _ in range(n + 1)]
    visited = [False for _ in range(n + 1)]
    for i in range(n):
        # 혼자 팀을 이루는 경우 -> 미리 방문 처리
        if n_lst[i] == i + 1:
            cnt -= 1
            visited[i + 1] = True  # 방문 처리
        vertex[i + 1].append(n_lst[i])  # i -> v 단방향

    for i in range(1, n + 1):
        if not visited[i]:
            visited[i] = True  # 방문 처리
            cycle = [i]
            dfs(i)

    print(cnt)

Reference

• https://www.acmicpc.net/board/view/70227
• https://aia1235.tistory.com/47

문제 링크 - 백준 2146 다리 만들기

해결 과정

문제를 보고 가장 먼저 든 아이디어는 아무래도 각 대륙 간 가장 짧은 다리의 길이를 구하는 문제이기 때문에 그래프 최단 거리 그리고 최소 신장 트리이다.

1) 그래프 최단 거리 [ 근거 ] 그냥 "가장 짧은 다리의 길이 == 최단 거리"로 생각했고, 가중치가 따로 주어지지 않기 때문에 BFS로 문제를 풀이하면 깔끔하겠다는 생강기 들었다.

2) 최소 신장 트리(MST) [ 근거 ] 뭔가 육지라는 하나의 집합으로 하여 각 육지를 연결해야하나 ? 라는 생각이 들어서 최소 신장 트리가 떠올랐다.

결과적으로는 그저 육지 간 짧은 거리를 구하면 되겠구나 생각해서 1번 그래프 최단 거리 아이디어로 밀고 가기로 마음 먹었다.

사고 과정 (1) ❗️

최단 거리를 사용해서 풀기 위해서 어떻게 접근해야할까? 나는 이렇게 생각을 했다.

1. 각 육지를 구분해야하고, 어느 한 육지에서 시작했으면 시작했던 육지는 탐색에서 제외해야겠다.
2. 육지의 내부에서는 굳이 탐색할 필요는 없겠구나. 그러면 바다와 맞닿아있는 육지의 외곽 부분에서만 탐색을 해야겠다.

이를 구현하기 위해서 edges 라는 리스트를 만들고, 입력을 모두 받은 다음에 완전 탐색을 하면서 1인 육지에서 상, 하, 좌, 우를 탐색했을 때, 0값이 하나라도 있다면 edges 리스트에 해당 위치를 추가하였다. (N <= 100 이기 때문에 완전 탐색을 하여 외곽 부분을 담아도 상관 없겠다는 판단)

(위 그림은 edges 리스트에 담길 육지의 외곽 위치들입니다.)

여기까지 구현을 하고 난 뒤에

3. edges 리스트를 돌면서 다른 육지까지의 최단 거리를 BFS 알고리즘을 통해서 전역 최솟값을 갱신하자.
4. 육지를 구분하기 위해서 edges에서 값을 꺼낼 때마다, visited 리스트를 갱신하고, 해당 위치에서 DFS 알고리즘을 활용해서 현재 육지의 모든 위치를 방문 처리한다.
5. 결과적으로 현재 육지에 대해서는 모두 방문처리를 해줬기 때문에, 방문하지 않은 1값을 가진 다른 육지까지의 거리를 구할 수 있다.

이렇게 BFS와 DFS 알고리즘을 모두 사용하여 구현을 하고, 제출해보니 정답 판정을 받을 수 있었다. 그러나, 3740ms 를 받고 통과한 것이 맘에 들지 않았다.

사고 과정 (2) ‼️

시간이 너무 오래 걸렸지만, 통과한 것이 맘에 들지 않아 코드를 유심히 살펴보았다. 논리적으로는 문제가 없어보였지만, 불필요한 연산을 하고 있는 부분을 발견했다.

BFS 알고리즘 부분에서 전역 최솟값인 MIN값을 갱신하고 난 이후의 연산은 불필요하다는 것을 확인했다. 그 이유는 바로 BFS 특성 때문이다. BFS 알고리즘은 너비 우선 탐색으로 만약 가장 먼저 최솟값이 갱신이 되었다면, 그 뒤의 최솟값들은 갱신된 최솟값보다 같거나 큰 값이다. 따라서 한번 갱신이 되었다면, 곧바로 return 해주면 된다. 그 결과 3740ms -> 672ms 로 시간을 단축할 수 있었다!

(런타임 에러 결과는 setrecursionlimit 설정을 해주지 않아 발생했다.)

코드

정답 풀이

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 4)
input = stdin.readline


def dfs(cur_y, cur_x):
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        if 0 <= nxt_y < n and 0 <= nxt_x < n and not visited[nxt_y][nxt_x] and MAP[nxt_y][nxt_x] == 1:
            visited[nxt_y][nxt_x] = True  # 방문 처리
            dfs(nxt_y, nxt_x)


def bfs(y, x):
    global MIN

    dq = deque([(y, x, 0)])
    while dq:

        cur_y, cur_x, cnt = dq.popleft()

        for dy, dx in zip(dys, dxs):
            nxt_y, nxt_x = cur_y + dy, cur_x + dx
            if 0 <= nxt_y < n and 0 <= nxt_x < n and not visited[nxt_y][nxt_x]:
                if MAP[nxt_y][nxt_x] == 0:
                    visited[nxt_y][nxt_x] = True  # 방문 처리
                    dq.append((nxt_y, nxt_x, cnt + 1))
                # 다른 육지와 맞닿아 있는 경우
                else:
                    MIN = min(MIN, cnt)  # 최단 거리 갱신


n = int(input().rstrip())
# 0: 바다 / 1: 육지
MAP = [list(map(int, input().split())) for _ in range(n)]
edges = []
dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]

for i in range(n):
    for j in range(n):
        # 육지인 경우
        if MAP[i][j] == 1:
            flag = False
            for dy, dx in zip(dys, dxs):
                ny, nx = i + dy, j + dx
                if 0 <= ny < n and 0 <= nx < n:
                    if MAP[ny][nx] == 0:
                        flag = True

            # 육지의 가장자리인 경우
            if flag:
                edges.append((i, j))

MIN = float('inf')
for ey, ex in edges:
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[ey][ex] = True  # 방문 처리
    dfs(ey, ex)  # 같은 육지는 모두 방문 처리
    bfs(ey, ex)

print(MIN)

정답 최적화 풀이

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 4)
input = stdin.readline


def dfs(cur_y, cur_x):
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        if 0 <= nxt_y < n and 0 <= nxt_x < n and not visited[nxt_y][nxt_x] and MAP[nxt_y][nxt_x] == 1:
            visited[nxt_y][nxt_x] = True  # 방문 처리
            dfs(nxt_y, nxt_x)


def bfs(y, x):
    global MIN

    dq = deque([(y, x, 0)])
    while dq:

        cur_y, cur_x, cnt = dq.popleft()

        for dy, dx in zip(dys, dxs):
            nxt_y, nxt_x = cur_y + dy, cur_x + dx
            if 0 <= nxt_y < n and 0 <= nxt_x < n and not visited[nxt_y][nxt_x]:
                if MAP[nxt_y][nxt_x] == 0:
                    visited[nxt_y][nxt_x] = True  # 방문 처리
                    dq.append((nxt_y, nxt_x, cnt + 1))
                # 다른 육지와 맞닿아 있는 경우
                else:
                    MIN = min(MIN, cnt)  # 최단 거리 갱신
                    return 

n = int(input().rstrip())
# 0: 바다 / 1: 육지
MAP = [list(map(int, input().split())) for _ in range(n)]
edges = []
dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]

for i in range(n):
    for j in range(n):
        # 육지인 경우
        if MAP[i][j] == 1:
            flag = False
            for dy, dx in zip(dys, dxs):
                ny, nx = i + dy, j + dx
                if 0 <= ny < n and 0 <= nx < n:
                    if MAP[ny][nx] == 0:
                        flag = True

            # 육지의 가장자리인 경우
            if flag:
                edges.append((i, j))

MIN = float('inf')
for ey, ex in edges:
    visited = [[False for _ in range(n)] for _ in range(n)]
    visited[ey][ex] = True  # 방문 처리
    dfs(ey, ex)  # 같은 육지는 모두 방문 처리
    bfs(ey, ex)

print(MIN)

Reference

• 내 머리

문제 링크 - 백준 1669 제곱수의 합

해결 과정

나는 DP 유형문제를 정복하기 위해서 관련 문제집을 통해서 문제를 풀고 있었기 때문에 해당 문제가 DP 유형이라는 것을 미리 알았다. 문제도 뭔가 쉬워보여서 바로 풀이를 시작했지만, 역시나 바로 틀렸다.풀이까지의 사고 과정은 다음과 같다.

사고 과정 (1) ❗️

문제로 주어지는 N의 값은 1 <= N <= 100_000 이다. 즉, O(N^2)은 시간초과가 날 것이다. 따라서 최대한 O(N log N) 이하의 알고리즘으로 문제를 풀어야 한다. 그래서 나는 이 문제를 다음과 같은 순서로 접근했다.

1. 우선, dp 테이블을 선언하고, 1부터 100_000 까지의 제곱수의 dp값을 1로 설정했다. 이를 위해서 math 라이브러리의 isqrt 함수를 사용했다.
2. 100_000의 제곱근은 316 이다. 즉, 1부터 316까지만 돌면 된다.
3. 1부터 100_000까지 돌면서 제곱수가 나오게 되면(if dp[i] == 1) 해당 제곱수를 기준값(std = i)으로 설정한다.
4. 기준값이 아닌 경우에는 dp[i] = dp[i - std] + 1 라는 점화식으로 dp 테이블을 완성하고, dp[n] 값을 출력한다.

이 풀이는 치명적인 단점이 있다. 반드시 특정 숫자와 가장 가까우면서 가장 큰 제곱수로만 dp 값을 채운다는 것이 틀린 이유였다.

예를 들어, 41 이라는 숫자가 있다. 내가 설정한 점화식은 41 = 36 + 4 + 1 을 정답으로 내보낸다. 그러나, 사실은 41 = 25 + 16 가 정답이다.

사고 과정 (2) ‼️

그럼 이 문제를 어떻게 풀이할까... 생각하다가 100_000보다 작으면서 가장 큰 제곱수가 316의 제곱이라는 것이 눈에 보였다. 즉, 완전 탐색을 돌려도 O(316N) = O(N) 이기 때문에 통과할 것이라고 판단을 내리고 완전 탐색을 하기로 마음을 먹었다. 완전 탐색의 과정은 다음과 같다.

1) 사고 과정 (1)의 풀이 방향과 비슷하다. 2) 1부터 100_000까지 돌면서 특정 숫자보다 작은 모든 제곱수들에 대해서 dp[i] = dp[i -j * j] + 1 점화식을 적용하기로 했다. 3) 예를 들어, 현재 숫자가 41일 이라고 하자. 설정한 점화식으로 dp값이 갱신되는 과정은 다음과 같다.

        dp[41] = dp[41 - 2 * 2] + 1 = dp[37] + 1 = 3
        dp[41] = dp[41 - 3 * 3] + 1 = dp[32] + 1 = 3
        dp[41] = dp[41 - 4 * 4] + 1 = dp[25] + 1 = 2
        ...
        dp[41] = dp[41 - 6 * 6] + 1 = dp[5] + 1 = 3
        # 점화식 
        dp[i] = min(dp[i], dp[i - j * j] + 1)

이렇게 코드를 고치니, 문제를 해결할 수 있었다!

코드

오답 코드

from sys import stdin
from math import isqrt

input = stdin.readline

n = int(input().rstrip())

LEN = 100_000
# dp 초기화
dp = [0 for _ in range(LEN + 1)]
for i in range(1, isqrt(LEN) + 1):
    dp[i ** 2] = 1

std = None
for i in range(1, LEN + 1):
    if dp[i] == 1:
        std = i
        continue

    dp[i] = dp[i - std] + 1

print(dp[n])

정답 코드

from sys import stdin
from math import isqrt

input = stdin.readline

n = int(input().rstrip())

LEN = 100_000
# dp 초기화
dp = [float('inf') for _ in range(LEN + 1)]
for i in range(1, isqrt(LEN) + 1):
    dp[i ** 2] = 1

# 문제 풀이
for i in range(1, LEN + 1):
    for j in range(1, isqrt(i) + 1):
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

Reference

• 내 머리

문제

나는 해당 문제에 대해서 처음에 단순한 DFS 문제로 접근했다. 그 이유는 다음과 같다.

• N x M 의 최댓값이 500 * 500 이므로 250,000 이다.
• 항상 내리막길로 가야한다는 조건 때문에 항상 모든 장소를 탐색하지 않아도 된다. 즉, 탐색에 있어 많은 제한이 있을 것으로 판단했다.

이러한 이유로 단순 DFS 풀이와 setrecursionlimit를 10 ** 6 까지만 해제하여(최대 250,000 이므로) 재귀를 마음껏 진행할 수 있도록 하였지만, 시간초과와 마주했다. 도대체 어떻게 최적화해야 이 문제를 해결할 수 있을까 고민했다. 그래서 모든 거리 관련 알고리즘을 떠올렸다.

• BFS로 풀어야 하나? -> 이 문제는 경로의 경우의 수를 구해야하기 때문에 적절하지 않다.
• 다익스트라로 풀어야 하나? -> 최단 거리와는 상관없다. 도달하기만 하면 된다.
• Kruskal, Prim -> 최소 신장 트리와는 관련이 없다.

도저히 아이디어가 떠오르지 않아서 해당 문제와 관련된 블로그를 많이 찾아보았다. 정답은 DFS와 DP 개념을 결합하여 불필요한 탐색 수를 줄여 경우의 수를 구하는 방법이 해결법이었다. DP 개념이 그래프와도 결합될 수 있다는 점에 놀라웠다.

아이디어

DFS 와 DP 결합 아이디어는 다음과 같다.

• dp 테이블을 -1(방문하지 않은 상태)로 초기화한다.
• 일반적인 DFS를 조건에 맞추어 구현한다.
• (n - 1, m - 1) 위치에 도달하면 1을 return한다.
• 그러면 다시 역추적하면서 dp[y][x]에 return 값을 저장한다.
• 만약, 나아가다가 -1이 아닌 정점과 마주하면, 이미 그 길은 방문했다는 의미로 해당 숫자를 return한다.
• 이 과정을 모두 수행하면 (0, 0)에 (n - 1, m - 1)까지 가는 경우의 수가 저장되어있다.
• 즉, dp[y][x]는 (y, x) -> (n - 1, m - 1) 갈 수 있는 경우의 수이다.

-> 처음 DFS를 통해서 내리막길 조건을 만족하면서 목적지까지 갑니다.

-> 만족하는 조건이 없어 DFS를 복귀하고, 다시 다른 가지로 뻗어나갑니다. 뻗어나가는 도중에 이미 방문했던 정점을 만났다면, 이미 방문한 정점이 가지고 있는 숫자를 return 합니다. 그 숫자를 현재 경로까지의 방법 수를 더해줍니다.

-> 마찬가지로, 만족하는 조건이 없어 복귀하다가 다시 뻗어나갑니다. 32 -> 30 -> 25 -> 20 에서 이미 방문했던 20을 만났고, 해당 값인 1을 return 합니다. return 하면서 현재 경로까지의 방법 수를 더해주면서 dp값을 최신화합니다. 이와 같은 과정을 통해서 dp[0][0]까지 초기화가 진행되고, 이 값이 정답이 됩니다.

파이썬 코드

from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 6)
input = stdin.readline


def dfs(cur_y, cur_x):
    # 도착 지점에 도달하면 1(한 가지 경우의 수)를 리턴
    if cur_y == n - 1 and cur_x == m - 1:
        return 1

    # 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴
    if dp[cur_y][cur_x] != -1:
        return dp[cur_y][cur_x]

    ways = 0
    for dy, dx in zip(dys, dxs):
        nxt_y, nxt_x = cur_y + dy, cur_x + dx
        if 0 <= nxt_y < n and 0 <= nxt_x < m and MAP[cur_y][cur_x] > MAP[nxt_y][nxt_x]:
            ways += dfs(nxt_y, nxt_x)

    dp[cur_y][cur_x] = ways
    return dp[cur_y][cur_x]


n, m = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * m for _ in range(n)]
dys, dxs = [1, -1, 0, 0], [0, 0, 1, -1]

print(dfs(0, 0))

-> 구현 코드는 위와 같습니다. Pypy3는 메모리를 더 잡아먹기 때문에 메모리 초과 결과를 받습니다. 따라서, Python3로 제출하시면 정답 판정을 받을 수 있습니다.

Reference

• https://velog.io/@hyunsoo730/DFS-DP-문제-유형