@Immutable
data class LoginState(
    val id: String = "",
    val password: String = "",
)

컴포즈로 개발 중인데, 이전 UiState에 해당하는 개념으로 쓰는 data class에 @Immutable 어노테이션을 붙여줘야한다는 걸 알았다. 왜 그렇게 해야될까?

@Immutable은 객체가 불변(Immutable)임을 명시하여, 내부 값이 변경될 일이 없다고 Compose에게 알려주는 역할을 한다.  하지만, @Immutable이 붙어 있다고 해서 리컴포지션을 "절대 안 하는 것"이 아니라, 객체가 변경되지 않는 경우에는 불필요한 리컴포지션을 방지할 수 있다.

@Stable은 객체가 변경될 가능성이 있지만, Compose가 내부 필드 변화까지 추적 가능하다고 판단할 때 사용한다.
즉, @Stable이 붙어 있는 객체의 프로퍼티가 바뀌면 리컴포지션이 발생하지만, 객체가 같다면 불필요한 리컴포지션을 방지할 수 있다.

좀 더 자세히 보겠다.

@Composable
fun UserProfile(user: User) {
    /* body */ 
}

컴포저블함수에 대해서, 상태가 변경될 때마다 리컴포지션을 수행하는데, 이 예제 코드에서는 user의 프로퍼티 값이 바뀌지않는 한 UserProfile이 리컴포지션 되지않는다.(보고있는 상태가 user 하나라고 했을 때)

@Composable
fun Counter() {
    var count by remember { mutableStateOf(0) }
 
    Button(onClick = { count++ }) {
        Text("Count: $count")
    }
}

컴포즈에서 UI를 구성하는 데 필요한 데이터를 상태라고 보통 얘기하는데, by remember { mutableStateOf(T) }로 선언해서 썼을 것이다. 이렇게 var 객체로 선언된 건 상태가 변할 수 있고, 만약 이게 count라고 했을 때 count 값이 증가하게 되면 이걸 보고있던 컴포저블은 리컴포지션된다.

리컴포지션은 UI 트리를 순회하면서 변경된 상태에 대해서 UI를 다시 그리기 때문에 최적화와도 밀접한 연관이 있다. 즉 아래처럼 정리할 수 있겠다.

• 상태 변화는 UI 업데이트가 필요하다는 신호를 보내며, Compose에서 자동 감지
• 리컴포지션은 실제로 상태가 변경된 Composable을 재호출하여 UI를 갱신

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

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

BFS로 처음에 접근했으나, W, H, T가 최대 10^6인걸 확인하고 완전탐색이 아닌 걸 알았다... 

푸는 동안 사고과정

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static long w, h, k, t;
    static int[] di = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dj = {0, 1, 1, 1, 0, -1, -1, -1};
    static long mod = 998244353;
    static long ans;
 
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        w = Long.parseLong(st.nextToken());
        h = Long.parseLong(st.nextToken());
        k = Long.parseLong(st.nextToken());
        t = Long.parseLong(st.nextToken());
 
        ans = 1;
        for (int i = 1; i <= k; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            // i번째 바이러스 위치
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            go(x, y);
        }
 
        System.out.println(ans);
    }
 
    public static void go(long x, long y) {
        long wCase = Math.min(w, x + t) - Math.max(1, x - t) + 1;
        long hCase = Math.min(h, y + t) - Math.max(1, y - t) + 1;
 
        ans = (ans * wCase) % mod;
        ans = (ans * hCase) % mod;
    }
}

말이 좀 어렵다.

대각선도 이동할 수 있기 때문에, t초일 때 이동할 수 있는 범위는 정사각형이 된다. 또한 각 바이러스가 독립적이기 때문에 각 바이러스의 이동 경우의 수를 다 각각 곱해버리면 된다.

이동 범위가 곧 이동 경우의 수가 되므로, 가로와 세로 이동범위를 사각형 형태로 곱해서 처리하면 된다.

가로 이동범위는 [max(1,x−T),min(W,x+T)](왼쪽끝에서 오른쪽 끝까지) 세로 이동범위는 [max(1,y−T),min(H,y+T)] (맨 위에서 맨 아래까지) 다.

이 두 이동범위를 곱하면 해당 바이러스가 독립적으로 차지할 수 있는 경우의 수를 알 수 있게 된다. 처음 문제를 읽었을 때 분포의 개념이 이거라는 게 바로 이해가 되지않아 더 어려웠다.

max, min을 사용한 이유는 W, H를 넘어가지 않도록 해야되니까 유효성 체크 개념으로 넣어뒀다.

ans에는 누적곱을 해야되는데, 문제에서 mod 값을 줬기 때문에 매번 곱할 때마다 mod를 해줘야한다.

이게 조합인 걸 떠올리지 못했을 경우에는 아예 못풀었을 것 같다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

▶ 유형

• 맨해튼 거리(Manhattan Distance)는 도시 블록을 따라 이동하는 거리를 계산하는 방식이다.
• 수학에서의 거리 공식이랑은 다른데, |x1 - x2| + |y1 - y2| 로 두 점 사이의 x좌표 차이의 절댓값과 y좌표 차이의 절댓값의 합을 맨해튼 거리라고 부른다.
• 즉 격자형 구조에서의 최단 거리를 구하면 되는 거니까 좌표평면이나 대각선을 고려하지않는 상황에서 유용한 수식이라고 생각하면 된다.
• 근데 이걸 여러 점들 사이에서 맨해튼 거리 최소 합을 구하려면 중앙값을 선택하면 된다.

▶ 전략

1차원, 2차원으로 나눠서 보겠다.

1차원에서 여러 점들로부터의 맨해튼 거리 합이 최소가 되는 지점이 중앙값인 이유를 알아보자.

수평선에 n개의 점 x₁, x₂, ..., xₙ이 있을 때, 거리 합을 생각해본다면 

• p가 어떤 점 xᵢ보다 작으면: -1 기여
• p가 어떤 점 xᵢ보다 크면: +1 기여

라고 볼 수 있다. 그래서 결국 최적값을 찾기 위해서는 기준 점을 중심으로 작은 점들의 개수, 큰 점들의 개수가 같은 지점에 놔야하는데, 이 말은 곧 중앙값이라는 얘기가된다.

다시 말하자면, 수평선에서

중앙값에서 왼쪽으로 이동할 경우 왼쪽 점들과의 거리는 줄지만, 오른쪽 점들과의 거리가 더 많이 증가하고
중앙값에서 오른쪽으로 이동: 오른쪽 점들과의 거리는 줄지만, 왼쪽 점들과의 거리가 더 많이 증가한다.

그래서 중앙값이 이 때 최적점이 되는 것이다!

그럼 2차원으로 가보자

2차원은 수평선이 단순히 2개 있다고 생각하면 된다. 곧 x축과 y축이 독립적으로 존재하고, 각각의 축을 기준으로 1차원 맨해튼 거리 최적점 찾듯 하면 된다.

즉 x좌표의 중앙값과 y좌표의 중앙값이 만나는 점이 전체 최적해라고 생각할 수 있다. 

바로 문제 풀어보자.

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

1차원 맨해튼 거리 합 최적점을 찾는 문제다.

난 처음에 이렇게 작성했다가 바로 시간초과가 났다.

public static void go() {
    int[] target = new int[n];
    for (int i = 0; i < n; i++) {
        target[i] = point[i];
    }
    Arrays.sort(target);
    int min = Integer.MAX_VALUE;
    int minT = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int center = (target[j] + point[i]) / 2;
            int dist = 0;
            for (int k = 0; k < n; k++) {
                int d = Math.abs(point[k] - center);
                dist += d;
            }
            if (min > dist) {
                min = dist;
                minT = center;
            }
            // System.out.println("dist: " + dist + " minT: " + minT + " center: " + center);
            // System.out.println();
        }
    }
}

진짜 완전탐색 방식으로 푼건데 이렇게 하면 보다시피 O(n^3)이다.

n이 20만이라 절대 이렇게 하면 안된다.

수평선 최적점을 생각하며 다시 풀면 아래와 같이 짧은 풀이가 완성된다.

public static void go() {
    Arrays.sort(point);
    System.out.println(point[(n - 1) / 2]);
}

이걸 2차원으로 들고 가면 아래 문제가 된다.

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

처음에 중앙값이 항상 최적인 이유를 모르고, 주어진 점을 활용해서 거리합을 구했다. 이렇게하면 첫번째 예시에서 0 2 4 6이 나오며 틀린 답만 내놓는다.

그래서 x 축, y 축을 분리해 각 좌표를 떼어내어 조합해야된다.

처음 작성할 때 중앙값 비교를 생각하지 못해서 계속 틀렸다.

public static void go() {
    for (int k = 1; k <= n; k++) {
        // k일때 최소거리합
        int res = Integer.MAX_VALUE;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int centerX = checker[i][0]; // 원 대상의 X
                int centerY = checker[j][1]; // 비교 대상의 Y
 
                int[] dist = new int[n];
                for (int p = 0; p < n; p++) {
                    dist[p] = Math.abs(checker[p][0] - centerX) + Math.abs(checker[p][1] - centerY);
                }
//                    System.out.println(Arrays.toString(dist));
                Arrays.sort(dist);
 
                int sum = 0;
                for (int d = 0; d < k; d++) {
                    sum += dist[d];
                }
 
                res = Math.min(res, sum);
            }
        }
        sb.append(res).append(" ");
    }
}

원대상의 X좌표, 비교 대상의 Y좌표를 기준으로 해서 맨해튼 거리를 구하며 k 만큼의 합을 계속 만들어가면 되는 문제다. 나는 난이도를 모두 가리고 풀기 때문에 이게 플레라는 걸 알고 좀 놀랐다.

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!

▶ 유형

• 모노톤 스택은 스택의 요소들이 항상 단조 증가하거나 단조 감소하도록 유지되는 특별한 형태의 자료구조다. 그래서 단조 스택이라고도 한다.
• 모노톤 스택의 가장 큰 장점은 특정한 패턴을 가진 다음/이전 원소를 찾는 문제를 선형 시간에 해결할 수 있다는 점인데, 각 원소는 최대 한 번씩만 스택에 들어가고 나오기 때문에 O(n^2)이 될 코드가 O(n)으로 유지된다., 이게 엄청 큰 장점이다.
• 배열에서 각 원소의 다음으로 큰 수 찾기, 히스토그램에서 가장 큰 직사각형 넓이 구하기, 온도가 더 높아지는 날까지 기다려야 하는 일수 계산하기 같은 유형에 적용할 수 있다.

▶ 전략

오름차순이면 들어가려는 수가 top 보다 작거나 같은 경우 pop을 반복하고 내림차순이면 들어가려는 수가 top 보다 크거나 같은 경우 pop을 반복하면 구현된다.

[2, 1, 4, 3, 5]를 예로 들어보겠다.

먼저 2가 들어온다. 그 다음 1이 들어오는데, 1은 2보다 작으므로 2를 pop하고 1을 push한다. push 전에 top과 비교하는 게 핵심이다.

4는 1보다 크므로 그대로 push하고, 3이 들어와야되는데 3은 4보다 작으니까 4을 pop 하고 3을 push한다. 이런식으로 진행이 되는데, 만약 입력 배열이 [2, 3, 5, 1] 이라면 어떻게 될까?

5까지 담았을 때 1과 비교하면 5가 pop되야한다. 여전히 top이 1보다 크므로 3도 pop, 2도 pop하면 스택이 빈 상태로 1이 push 되는 것이다.

즉 스택에 어떤 값을 넣기 전에 k 이상의 수를 모두 제거하고 k를 넣는 것이다.

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

얘를 한번 풀어보자.

for (int i = 1; i <= n; i++) {
    // 현재 막대(arr[i])보다 큰 높이의 막대들을 처리
    while (!st1.isEmpty()) {
        if (st1.peek() > arr[i]) {
            long nowVal = st1.pop();     // 현재 처리할 높이
            st2.pop();                   // 해당 높이의 위치도 함께 제거
  
            // 직사각형의 왼쪽 경계 찾기
            int leftIdx = -1;
            if (st2.isEmpty())
                leftIdx = 1;             // 스택이 비었다면 처음부터
            else
                leftIdx = st2.peek() + 1; // 이전 막대 다음 위치부터
            
            // 직사각형의 오른쪽 경계는 현재 위치 직전까지
            int rightIdx = i - 1;
            
            // 넓이 계산
            long width = rightIdx - leftIdx + 1;
            long area = width * nowVal;
            
            max = Math.max(max, area);
        } else {
            break;  // 현재 막대보다 작거나 같은 높이를 만나면 중단
        }
    }
    
    // 현재 막대의 정보를 스택에 추가
    st1.push(arr[i]);
    st2.push(i);
}

메인 로직이다.

입력 값과 top을 비교하는데, top이 더 크면 pop하고, idx를 들고있던 스택도 pop한다.(동기화)

지금 스택에 들어있는 값이 직사각형의 높이가 될 것이고, 인덱스의 차이만큼이 너비가 되는 것이다.

그래서 pop되는 시점의 바로 이전 인덱스가 top이 유지되고있는 인덱스이기 때문에 그걸 너비로 계산하면 끝난다. 물론 이 작업 후에, 아직 스택이 비어있지 않을 수 있기 때문에 스택을 비워주는 작업도 필수다. 근데 이미 탐색을 모두 한 시점이기 때문에, 오른쪽 끝을 n으로 잡고 시작한다.

// 남은 스택 정리
while (!st1.isEmpty()) {
    Long nowVal = st1.pop();
    st2.pop();
    int rightIdx = n; // 오른쪽 끝
    int leftIdx = -1;
    if (st2.isEmpty()) {
        leftIdx = 1;
    } else {
        leftIdx = st2.peek() + 1;
    }
    long width = rightIdx - leftIdx + 1;
    long area = width * nowVal;
    max = Math.max(max, area);
}

이 문제는 단조 증가로 해결했지만, 어떻게 문제에서 단조 증가, 감소를 파악할 수 있을까?

단조증가와 단조감소를 구분하는 핵심은 "요구사항"에 달려있다.
먼저 결과값의 조건을 파악해야한다. 찾는 값이 "더 큰 수"인지 "더 작은 수" 인지 구분해야된다.

• "더 큰 수"를 찾는 경우 → 단조감소 스택 유지
• "더 작은 수"를 찾는 경우 → 단조증가 스택 유지

이렇게 나눌 수 있는데,

https://www.acmicpc.net/problem/2493 
탑 문제를 보면, 이전 스택에 더 큰 수가 수신 기둥이다. 그래서 단조감소 스택을 유지하는 것이다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    public static int[] input;
    public static ArrayDeque<Integer> stack;
    public static ArrayDeque<Integer> idx; // idx
    public static int n;
    public static int[] res;
 
    public static void main(String[] args) throws Exception {
        // System.setIn(new FileInputStream("res/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        input = new int[n + 1];
        res = new int[n + 1]; // idx 번 기둥이 수신했음을 기록하려고
        // idx 계산 1부터
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        // 입력 끝
        stack = new ArrayDeque<>();
        idx = new ArrayDeque<>();
        go();
        for (int i=1; i<=n; i++){
            sb.append(res[i]).append(" ");
        }
        System.out.println(sb);
    }
 
    public static void go() {
        for (int i = 1; i <= n; i++) {
            // 단조 감소 스택으로 가면 될 것 같다.
            int now = input[i];
            while (!stack.isEmpty()) {
                if (stack.peek() < now) { // top이 더 작으면 빼야된다
                    stack.pop();
                    idx.pop();
                } else {
                    // 그게 아니라면 수신한 것
                    res[i] = idx.peek();
                    break;
                }
            }
            stack.push(now);
            idx.push(i);
        }
    }
}

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!