[TIL] 2025.05.16 (금)

알고리즘 스터디

https://www.acmicpc.net/problem/20166

오늘은 BFS 문제

문제 푸는 것 자체는 그렇게 어렵지 않지만 최적화는 좀 더 고려해야하는 문제였다.

 

최적화를 도전하며 abcd 가 있을 때 ab가 4개 있고 cd가 3개 있다고 해서 곱하면 결과가 되는 것이 아니라는 점을 깨닫지 못했다..

그래서 결과는 더 크게 나왔다.

 

각 자리에서 어디까지의 결과가 몇번 나왔는지가 필요한 듯 하다.

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

public class Main {
  public static final int[] dx = {1,0,-1,0,-1,-1,1,1};
  public static final int[] dy = {0,1,0,-1,-1,1,1,-1};
  public static int M, N, K;
  public static char[][] map;
  public static int count = 0;
  public static StringBuilder sb = new StringBuilder();
  public static Map<String, Integer> hash = new HashMap<>();

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    input(br);
    for(int i=0 ; i<K ; i++){
      pro(br);
    }
    System.out.println(sb);
  }

//  static class Tree{
//    public char cur;
//    public int count;
//    public Map<Character, Tree> nexts;
//    public Tree(char cur){}
//
//  }

  static class Node {
    public int x, y, len;
    public String text;
    public Node(int x, int y, int len, String text) {
      this.x = x;
      this.y = y;
      this.len = len;
      this.text = text;
    }
    public Node(int x, int y, int len) {
      this.x = x;
      this.y = y;
      this.len = len;
    }
  }

  static void pro(BufferedReader br) throws Exception {
    String s = br.readLine();
    if(hash.containsKey(s)){
      sb.append(hash.get(s)).append("\n");
      return;
    }
    LinkedList<Node> q = new LinkedList<>();
    for(int i =0 ; i< N; i++){
      for(int j=0 ; j< M; j++){
        if(map[i][j] == s.charAt(0)) {
          q.add(new Node(i,j,0));
        }
      }
    }
    int len = s.length();
    int count = 0;
    while(!q.isEmpty()){
      Node cur = q.poll();
      int curX = cur.x;
      int curY = cur.y;
      int curL = cur.len;
      if(curL == len-1) {
        count++;
        continue;
      }
      for(int i=0 ; i<dx.length ; i++){
        int nx = (curX + dx[i] + N) % N;
        int ny = (curY + dy[i] + M) % M;
        int nl = curL + 1;

        if(map[nx][ny] != s.charAt(nl)) continue;
        q.add(new Node(nx,ny,nl));
      }
    }
    sb.append(count).append("\n");
    hash.put(s, count);
  }

  static void input(BufferedReader br) throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    map = new char[N][M];

    for(int i = 0; i < N; i++){
      String s = br.readLine();
      for(int j = 0; j < M; j++) {
        map[i][j] = s.charAt(j);
      }
    }
  }
}

 

발표 스터디

https://github.com/HI-dle/interview-study

GitHub - HI-dle/interview-study

이번글은 pub/sub을 주제로 했고 다음주에 redisson lock에 대해 알아보려 한다. redisson lock에서 pub/sub을 사용하기 때문에 이번주는 pub/sub을 주제로 하였다.

 

비관적락 vs 낙관적락

interview-study/강혜주/20250516_비관적락 vs 낙관적락.md at main · HI-dle/interview-study

로깅을 해서 쿼리문을 확인한 부분이 기억에 남는다. PostgreSQL JPA 구현체가 PESSIMISTIC_WRITE를 FOR NO KEY UPDATE로 변환한다는 점이다. 라는 부분이 흥미로웠다.

DDD 4계층 구조와 역방향 의존성

interview-study/한지훈/20250516_DDD와 4계층 구조_의존성 역전 제거.md at main · HI-dle/interview-study

같이 팀 프로젝트를 했던 구조를 한번 더 그림으로 보니 복습되고 좋았다.

ddd strategic and tactical 개념도 한번 읊어 주셨는데 다음에 정리하면서 더 찾아보면 좋을 것 같다.

Redis Persistence

interview-study/ 황하온/20250516_redis_persistence.md at main · HI-dle/interview-study

redis를 영속화 할 수 있는 방법 AOF와 RDB 에 대해서 개념을 다시 복습할 수 있었다. redis.. 설정이 참 많다..

Observability 적용과정

interview-study/최진영/20250516_OpenTelemetry_적용_과정.md at main · HI-dle/interview-study

적용하면서 여러 문서를 찾아가며 최신 트랜드를 쫓아가려고 노력한 점이 보여서 대단했다.