2024/03/12(화)

나를 돌아보기

아.. 글쓰면서 알고리즘 하고 있었는데 다 날라갔다..

내가 공부한 내용을 거의 2시간 넘게 작성하고 있었는데.. 다시 해보자 상윤아

이또한 주님의 뜻이다..! 다시 차근차근 공부해보자 천천히 해보자.. 아 속상하다. 앞으로는 글 작성할때 임시저장을 무조건 해야겠다!

 

알고리즘

DP

 

백준 2240번(복습 완료)

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

2240번: 자두나무

 

풀이 코드

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

public class Main {
    public static int T;
    public static int W;
    public static int[] zadu;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        zadu = new int[T + 1]; // 1초부터 시작

        for (int i = 1; i <= T; i++) {
            zadu[i] = Integer.parseInt(br.readLine());
        }

        // 나무 위치 | 시간 | 움직임
        int[][][] dp = new int[3][T + 1][W + 2]; // 움직임이 없는 경우가 0 이되면 -1을 할경우 오류가 발생한다.

        for (int i = 1; i <= T; i++) { // 시간에 따른
            for (int j = 1; j <= W + 1; j++) { // 움직임
                if (zadu[i] == 1) { // 1번 나무 위치에 자두가 존재한다면
                    // 1번나무에서 가만히 있음으로 자두를 먹가나 2번나무에서 1번나무로 이동해서 자두를 먹은 갯수중 최댓값으로 갱신
                    dp[1][i][j] = Math.max(dp[1][i - 1][j] + 1, dp[2][i - 1][j - 1] + 1);
                    // 2번 나무에서 가만히 있는 경우와 1번 나무에서 2번나무로 이동한 경우 중 최댓값으로 갱신
                    dp[2][i][j] = Math.max(dp[2][i - 1][j], dp[1][i - 1][j - 1]);
                } else { // 2번나무에 자두가 존재한다면
                    if (i == 1 && j == 1) { // 맨처음 움직임 횟수가 0번인 경우, 애초에 2번 자두나무로 못 옮기는 경우
                        continue;
                    }
                    // 1번나무에서 가만히 있는 경우와 2번 나무에서 1번나무로 이동한 경우 중 최댓값으로 갱신
                    dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
                    // 2번나무에서 가만히 자두를 먹는 경우와 1번 나무에서 2번 나무로 옮겨서 자두를 먹은 갯수의 최댓값으로 갱신
                    dp[2][i][j] = Math.max(dp[2][i - 1][j] + 1, dp[1][i - 1][j - 1] + 1);
                }
            }
        }

        int result = Integer.MIN_VALUE;
        for (int i = 1; i <= W + 1; i++) {
            result = Math.max(result, Math.max(dp[1][T][i], dp[2][T][i]));
        }

        System.out.println(result);
        br.close();
    }
}

 

백준 15989번

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

15989번: 1, 2, 3 더하기 4

 

풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        // 1,2,3으로 더해지는 수
        int[][] dp = new int[10004][4];

        // 아래에 존재하는 수들은 전부 1개씩 존재한다.
        dp[1][1] = dp[2][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;

        for (int i = 4; i <= 10000; i++) {
            dp[i][1] = dp[i - 1][1]; // 각 경우에 1을 더하는 경우
            dp[i][2] = dp[i - 2][1] + dp[i - 2][2]; // 각 경우에 2를 더하는 경우
            dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
            // 3은 왜 3개인가? 3을 나타내는 경우는 3가지이다. 1+1+1, 2+1, 3
        }

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            int value = dp[n][1] + dp[n][2] + dp[n][3];

            sb.append(value);
            if (i < T - 1) {
                sb.append("\n");
            }
        }

        System.out.println(sb);
        br.close();
    }
}

 

펜윅트리

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

2042번: 구간 합 구하기

 

이 문제를 풀어보기 전에.. 얼핏봐도 떠오르지가 않는다.

우선 세그먼트 트리에 대한 다른 글을 옮겨 적으며 공부해보자..!

 

세그먼트 트리(Segment Tree)

여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법

데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조로 세그먼트 트리가 있다.

세그먼트 트리는 트리 영역에서 상당히 중요한 개념이다.

 

배열에서 특정 구간의 합을 가장 빠르게 구하는 방법은 무엇일까?
ex) 5 8 7 3 2 5 1 8 9 8 7 3

 

배열

 

12개의 데이터가 존재한다고 가정해보자..! 이때 특정 구간의 합을 어떻게 구할까?

 

방법 1. 단순 배열을 이용해 선형적으로 구하기

범위에 포함되는 값들을 배열을 일일히 순회하면서 하나씩 다 더하면 된다. 이러한 방식을 고려했을 때 앞에서 하나씩 더해가므로 데이터의 개수가 N이면 시간 복잡도는 O(N)이 나온다. 이러한 방식을 이용했을 때 구간의 합을 구하는 속도가 너무 느리기 때문에 더 좋은 알고리즘이 필요하다.

 

방법2. 트리 구조를 이용해 구하기

세그먼트 트리는 트리 구조의 특성상 합을 구할 때 시간 복잡도 O(logN)이면 된다.

방법1과 같이 단순히 더하는 방법보다 빠르게 구하기 위한 것이다. 기존의 배열을 트리 구조라고 고려해보자.

 

 

(1) 구간 합 트리 생성하기

 

인덱스는 동일하게 0부터 11까지이다. 빠르게 합을 구하기 위해서 구간 합 트리를 새롭게 생성해주어야 한다.

최상단 노드에는 전체 원소를 더한 값이 들어간다.

 

이후에 두 번째 노드와 세 번째 노드를 구한다.

두 번째 노드는 인덱스 0부터 인덱스 5까지의 원소를 더한 값을 가지고, 세 번째 노드는 인덱스 6부터 인덱스 11까지의 원소를 더한 값을 가진다.

원래 데이터의 범위를 반씩 분할하며 그 구간의 합들을 저장하도록 초기 설정을 하는 것이다.

이러한 과정을 반복하면 구간 합 트리의 전체 노드를 구할 수 있다.

 

구간 합 트리에 한해서는 인덱스 번호가 1부터 시작한다는 것이다. 그 이유는 데이터의 인덱스는 0부터이지만

구간 합 트리는 1부터 시작하면 2를 곱했을 때 왼쪽 자식 노드를 가리키므로 효과적이기 때문이다.

 

구간 합 트리는 반복적으로 구현하는 것보다 재귀적으로 구현하는게 더 간단하다.

 

// start: 시작 인덱스, end: 끝 인덱스
int init(int start, int end, int node){
	if(start == end) return tree[node] = a[start];
    	int mid = (start + end) / 2;
    	// 재귀적으로 두 부분으로 나눈 뒤에 그 합을 자기 자신으로 한다.
    	return tree[node] = init(start, mid, node*2) + init(mid + 1, end, node*2 + 1);
}

 

구간 합 트리는 다음과 같이 매 노드가 이미 구간의 합을 가지고 있는 형태가 된다고 할 수 있다.

노드의 인덱스와 구간의 합은 별개의 값이므로 헷갈리면 안된다.

 

구간 합 트리의 원소 개수는 32개라는 것을 알 수 있다. 쉽게 말해 데이터의 개수가 N개일 때 N보다 큰 가장 가까운 N의 제곱수를 구한 뒤에 그것의 2배까지 미리 배열의 크기를 미리 만들어놓아야 한다는 것이다.

 

이 경우는 데이터가 12개이므로 16*2 = 32개의 크기가 필요하다.

실제로는 데이터의 개수 N에 4를 곱한 크기만큼 미리 구간 합 트리의 공간을 할당한다.

 

(2) 구간 합을 구하는 함수 만들기

트리 구조를 가지고 있기 때문에 데이터를 탐색함에 있어서 들이는 비용은 O(logN)이다.

구간 합을 항상 O(logN)의 시간에 구할 수 있다. 예시로 4~8 범위에 대한 합을 구하려고 하는 경우, 다음과 같이 세 노드의 합만 구해주면 된다.

 

구간합 트리에서 인덱스 6(범위 6-8) 값은 24, 인덱스 11(범위 5), 인덱스 21(범위 4)

구하고자 하는 답은 3개의 노드를 더한 24+5+4 = 33이 된다. 구간의 합을 구하는 함수 또한 재귀적으로 작성하면 매우 짧게 작성할 수 있다. 구간의 합은 범위 안에 있는 경우 에 한해서만 더해주면 된다.

 

// start: 시작 인덱스, end: 끝 인덱스
// left, right: 구간 합을 구하고자 하는 범위
int sum(int start, int end, int node, int left, int right){
	// 범위 밖에 존재하는 경우
    if(left > end || right < start) return 0;
    
    // 범위 안에 있는 경우
    if(left <= start && end <= right) return tree[node];
    
    // 그렇지 않다면 두 부분으로 나누어 합을 구하기
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

 

(2) 특정 원소의 값을 수정하는 함수 만들기

특정 원소의 값을 수정하는 경우 해당 원소를 포함하고 있는 모든 구간 합 노드들을 갱신해주면 된다.

ex) 인덱스 7의 노드를 수정한다고 하면5개의 구간 합 노드를 모두 수정하면 된다.

 

재귀적으로 구현하면 어렵지 않게 작성할 수 있다. 마찬가지로 수정할 노드로는 '범위 안에 있는 경우'에 한해서만 수정해주면 된다.

 

// start: 시작 인덱스, end: 끝 인덱스
// index: 구간 합을 수정하고자 하는 노드
// dif: 수정할 값

void update(int start, int end, int node, int index, int dif){
	// 범위 밖에 있는 경우
    if(index < start || index > end) return;
    
    // 범위 안에 있으면 내려가며 다른 원소도 갱신
    tree[node] += dif;
    
    if(start == end) return;
    int mid = (start + end) / 2;
    
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}

 

세그먼트 트리르 이용하면 구간 합을 계산할 때 기존의 방법보다 획기적으로 속도가 빨라진다.

세그먼트 트리를 이용하면 구간 합을 구하거나 수정하 때
O(logN)으로 처리할 수 있다.

 

문제풀이

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

public class Main {
    static long[] arr, tree;

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

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

        arr = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        tree = new long[N * 4];

        init(1, N, 1); // tree의 노드 번호는 1번부터

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) { // 값 업데이트
                long dif = c - arr[b]; // 변화시켜야 하는수 - 원래 수
                arr[b] = c;
                update(1, N, 1, b, dif);
            } else if (a == 2) { // 구간 합
                sb.append(sum(1, N, 1, b, (int) c) + "\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    // start: 시작 인덱스, end: 끝 인덱스
    public static long init(int start, int end, int node) { // 초기화
        if (start == end) { // 리프 노드
            return tree[node] = arr[start];
        }

        int mid = (start + end) / 2;

        // 재귀적으로 두 부분으로 나눈 뒤에 그 합을 자기 자신으로 함.
        return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
    }

    // start: 시작 인덱스, end: 끝 인덱스
    // left, right: 구간 합을 구하고자 하는 범위

    public static long sum(int start, int end, int node, int left, int right) {
        if (left > end || right < start) {
            return 0;
        }

        if (left <= start && end <= right) {
            return tree[node];
        }

        int mid = (start + end) / 2;
        return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
    }

    // start: 시작 인덱스, end: 끝 인덱스
    // idx: 구간 합을 수정하고자 하는 노드
    // dif: 수정할 값

    public static void update(int start, int end, int node, int idx, long dif) {
        if (idx < start || idx > end) { // 범위 밖에 존재하는 경우
            return;
        }

        tree[node] += dif;

        if (start == end) {
            return;
        }

        int mid = (start + end) / 2;
        update(start, mid, node * 2, idx, dif);
        update(mid + 1, end, node * 2 + 1, idx, dif);
    }

}

 

코드를 분할해서 생각해보자!

public static long init(int start, int end, int node) { // 초기화
        if (start == end) { // 리프 노드
            return tree[node] = arr[start];
        }

        int mid = (start + end) / 2;

        // 재귀적으로 두 부분으로 나눈 뒤에 그 합을 자기 자신으로 함.
        return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
    }

이 부분은 세그먼트 트리를 초기화 해주는 부분이다.

재귀 함수를 사용해서 구간을 절반으로 나누어서 구간의 합을 각 노드에 저장해준다.

 

 public static long sum(int start, int end, int node, int left, int right) {
        if (left > end || right < start) {
            return 0;
        }

        if (left <= start && end <= right) {
            return tree[node];
        }

        int mid = (start + end) / 2;
        return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
    }

이 부분은 초기화된 세그먼트 트리에서 일정 구간의 합을 구해주는 부분이다.

 

3가지 범위를 기준으로 판단을 해준다.

(1) 범위를 벗어난 경우

(2) 범위에 포함된 경우

(3) 일부분만 포함된 경우

 

public static void update(int start, int end, int node, int idx, long dif) {
        if (idx < start || idx > end) { // 범위 밖에 존재하는 경우
            return;
        }

        tree[node] += dif;

        if (start == end) {
            return;
        }

        int mid = (start + end) / 2;
        update(start, mid, node * 2, idx, dif);
        update(mid + 1, end, node * 2 + 1, idx, dif);
    }

이 부분은 초기화된 세그먼트를 업데이트 해주는 부분이다.

구간의 합으로 이루어져 있기 때문에, 변경될 수와 기존의 수의 차이를 구간합에 계속 더해주어야 한다.

 

세그먼트 트리를 이용해 문제를 풀때에는

# 초기화

# 업데이트

# 구간 합

 

백준3653번 - 영화 수집

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

3653번: 영화 수집

도저히 모르겠다.. 이 문제가 어떻게 세그먼트 트리를 사용해서 풀 수 있는지 의문이다.

오늘 알고리즘은 여기까지 하고, 내일 도전해보자!

 

Spring

졸업작품 프로젝트를 위해서 JPA와 RDS를 연동하려 고한다..!

JPA를 사용하기 위해 필요한 YAML파일에 대해서 알아보자!

 

YAML

YAML은 구성 파일 작성에 자주 사용되는 데이터 직렬화 언어이자, 데이터 표현 양식의 한 종류이다.

YAML은 사용자가 보고 이해하기 쉬운 형태를 가지고 있기 때문에 최근들어 많이 활용되는 데이터 포맷이다.

 

applicatoin.yml

 

공통 어플리케이션 속성

spring

  datasource

    url : 데이터베이스의 JDBC URL

    username : 데이터베이스의 로그인 사용자 이름

    password : 데이터베이스의 로그인 비밀번호

    driver-class-name : JDBC 드라이버의 완전한 이름이다. 기본적으로 URL을 기반으로 자동 감지

 

jpa

  hibernate

    ddl-auto : DDL 모드, hibernate.hbm2ddl.auto 속성에 대한 손쉬운 방법으로 임베디드 데이터베이스를 사용하고 스키마 관리자가        감지되지 않은 경우 기본값은 "create-drop" 그렇지 않은 경우 기본값은 "none"

  properties

    hibernate: JPA 공급자에 설정할 추가 기본 속성

    format_sql

 

logging

   level: 로그 수준 엄격 매핑

   org.hibernate.SQL

   org.hibernate.type

 

AWS-RDS와 연동을 성공했다!

 

나머지 시간은 졸업작품에 집중했다..!