몽키D버그’s 개발일지

개요

가장 긴 바이토닉 부분 수열을 찾는 문제

바이토닉 부분 수열

아이디어

알고리즘 : Dynamic Programming (DP)

풀이 후 다른 블로그를 참고해보니 `LIS(증가하는 부분수열의 크기) + LDS(감소하는 부분수열의 크기)`를 구하여서

"합산한 값의 최댓값에 -1" 방법으로 구하는 것을 확인했습니다.

(* -1을 하는 이유는 LIS와 LDS를 합치면 같은 원소가 중복해서 합산되기 때문.)

풀이 당시 비슷하지만 다른 접근 방식으로 문제를 풀어서 기록을 남기게 되었습니다.

arr[N] = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 기준으로 풀이하겠습니다.

dp[2][N]을 선언했습니다.

dp[0][i]에는 해당 i번째에 오름차순 기준으로 최대 길이가 저장되게 됩니다.

dp[1][i]에는 해당 i번째에 내림차순 기준으로 최대 길이가 저장되게 됩니다.

1. dp[2][N]을 1로 초기화 합니다.

해당 위치는 모두 "오름차순의 시작지점" 또는 "내림차순의 시작지점"이 될 수 있기 때문입니다.

2. i=1번째 인덱스부터 순회하며, j=i-1부터 0번째까지 역순으로 탐색하며 최대길이를 업데이트 합니다.

i = 1 -> arr[1] = 5
j = 0 -> arr[0] = 1

arr[i]=5 > arr[j]=1 이라면 오름차순이 이어지게 된다.

if(arr[i] > arr[j]){
    // 오름차순 인지, 오름차순 시작 지점(or 최대)인지
    dp[0][i] = Math.max(dp[0][j] + 1, dp[0][i]);
}

업데이트 과정은 다음과 같다.

dp[0][0] + 1 = 1 + 1 = 2

dp[0][1] = 1

=> dp[0][1] = max(2, 1)

i = 2 -> arr[2] = 2
j = 1 -> arr[1] = 5

arr[i]=2 < arr[j]=5 라면 내림차순으로 변경되는 지점이다.

내림차순이 이어지거나 시작되는 지점이기도 하다.

if(arr[i] < arr[j]){
    // 최대 인지, 내림차순 이어지는 지점 인지, 내림차순으로 변경된지점인지
    dp[1][i] = Math.max(dp[1][i], Math.max(dp[1][j] + 1, dp[0][j] + 1));
}

업데이트 과정은 다음과 같다.

내림차순으로 변경되는 지점 : dp[0][1] + 1 = 2 + 1 = 3

내림차순이 이어지거나 시작되는 지점 : dp[1][1] + 1 = 1 + 1 = 2

dp[1][2] = 1

=> dp[1][2] = max(1, max(2, 3))

i = 2 -> arr[2] = 2
j = 0 -> arr[0] = 1

arr[i]=2 > arr[j]=1 이라면 오름차순이 이어지게 된다. ( 맨 처음에 수행한 과정과 동일하다.)

if(arr[i] > arr[j]){
    // 오름차순 인지, 오름차순 시작 지점(or 최대)인지
    dp[0][i] = Math.max(dp[0][j] + 1, dp[0][i]);
}

업데이트 과정은 다음과 같다.

dp[0][0] + 1 = 1 + 1 = 2

dp[0][2] = 1

=> dp[0][2] = max(2, 1)

3. 2번의 과정을 반복하면 됩니다.

i = 3 -> arr[3] = 1
j = 2 -> arr[2] = 2

i = 4 -> arr[4] = 4

i = 5 -> arr[5] = 3

i = 6 -> arr[6] = 4

i = 7 -> arr[7] = 5

i = 8 -> arr[8] = 2

i = 9 -> arr[9] = 1

4.dp[2][N]에서 최대값을 찾는다.

dp[2][N] 배열에서 최댓값은 7이다.

코드

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

public class Main {
    static int[] arr;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[2][N]; // row 0 : 오름차순, row 1 : 내림차순

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

        for(int i=1; i<N; i++){
            for(int j=i-1; j>=0; j--){
                if(arr[i] > arr[j]){
                    // 오름차순 인지, 오름차순 시작 지점(or 최대)인지
                    dp[0][i] = Math.max(dp[0][j] + 1, dp[0][i]);
                }
                else if(arr[i] < arr[j]){
                    // 그대로 인지, 내림차순 이어지는 지점 인지, 내림차순으로 변경된지점인지
                    dp[1][i] = Math.max(dp[1][i], Math.max(dp[1][j] + 1, dp[0][j] + 1));
                }
            }
        }

        int ans = 0;
        for(int i=0; i<2; i++){
            for(int j=0; j<N; j++){
                ans = Math.max(ans, dp[i][j]);
            }
        }

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }

}

문제출처

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

Gitmoji 공식문서와 Angular.js의 Git message Type을 바탕으로 GPT를 활용해서 만든
나만의 Git convention Docs

Gitmoji convention

Git commit message Type convention

출처)

상황

Docker Container를 실행시키기 위해 Docker Desktop으로 관리 중

현재 local PC 사양: OS(Windows 11),  RAM(16GB)

Docker Desktop Memory Resources : 8GB

컴퓨터가 자꾸 멈칫 멈칫 렉이 걸림 -> 개발 능률 떨어짐

작업관리자를  확인해보니 RAM 점유율 92% 달성

해결 방법

1. 컴퓨터를 바꾼다 -> 돈이 많이 듬. 배송 소요시간 있음

2. RAM을 추가 구입한다. -> 현재 PC 6년됨. 6년전 RAM 구매 투자 아까움. 추후 PC 변경 고려 중. 배송 소요시간 있음

3. Docker Desktop Memory Resources를 변경 -> 무료임. 소요시간이 적음 => 채택

현재 Docker 컨테이너 Compose 파일을 실행시 약 2.xxGB 소모 확인

Docker Desktop Memory Resources를 4GB로 줄이기로 결정

.wslconfig 파일 생성

C:\Users\<UserName>\.wslconfig

* MAC의 경우 Docker Desktop에서 'Settings > Resources'로 들어가면 슬라이드 bar로 조절 가능하다고 들었음.

* Windows 경우에 같은 경로로 들어가도 Memory를 조절할 슬라이드 bar가 없음 wslconfig 파일을 생성해야함.

* .wslconfig 파일

# Settings apply across all Linux distros running on WSL 2
[wsl2]

# Limits VM memory to use no more than 4 GB, this can be set as whole numbers using GB or MB
memory=4GB

wsl 재부팅

windows powershell -> 관리자 권한으로 실행

wsl --list --running

wsl --shutdown

Docker Desktop을 사용 중이라면

Docker Desktop 실행하려고 확인하면, '서비스'도 함께 종료 되어서 실행이 안됨.

windows 시작 버튼 > '서비스' 검색 -> 'Docker Desktop Service' 우클릭 후 수동으로 '시작'

Docker Desktop에서 Memory Resources 변경 확인

* 필자는 Docker Desktop에서  'Resource usage' 플러그인 설치해서 확인 함.

참고)