공부

동적 계획법(Dynamic Programming, DP) - DP

DP란 무엇일까? 동적 계획법은 큰 문제를 여러 개의 작은 문제로 나누어 해결한 후, 그 결과를 저장하여 전체 문제를 효율적으로 해결하는 방법이다. 예를 들어, 큰 퍼즐을 맞출 때, 각 조각을 따로 기억해둔다면 다시 같은 조각을 찾지 않아도 된다.

DP의 핵심 개념

• 부분 문제(Overlapping Subproblems) : 큰 문제를 해결하는 과정에서 동일한 작은 문제가 여러 번 반복되는 경우가 있다.
• 최적 부분 구조(Optimal Substructure) : 문제의 최적해가 그 하위 문제들의 최적해로 구성될 수 있을 때, DP를 적용할 수 있다.

대표 문제 : 계단 오르기

 - 문제 설명 : 계단이 총 n개 있고, 한 번에 1계단 또는 2계단씩 오를 수 있을 때, 계단을 모두 오르는 방법의 수를 구하시오.

 - 예시 : n = 3일때, 가능한 경우는

1.      1,1,1
2.      1,2
3.      2,1

   총 3가지 방법

 - 문제 해결을 위한 아이디어

• 계단 오르기 문제는 작은 문제(예 : n-1 계단을 오르는 방법, n-2 계단을 오르는 방법)로 나누어 생각할 수 있다.
• 점화식 : n 번째 계단에 도달하는 방법의 수는 dp[n] = dp[n-1] + dp[n-2] 이다. 왜냐하면 마지막에 한 계단을 오르는 경우와 두 계단을 오르는 경우로 나눌 수 있기 때문이다.
• 기본 조건 : dp[0] = 1 (아무 계단도 오르지 않은 경우를 1가지 방법으로 간주) / dp[1] = 1 (첫 번째 계단까지 오르는 방법은 1가지)

1. 반복적(Bottom-Up) 방식으로 DP 구현하기

fun climbStairs(n: Int): Int {
    // n이 0 또는 1인 경우 바로 반환
    if (n <= 1) return 1

    // dp 배열 생성: dp[i]는 i번째 계단까지 도달하는 방법의 수
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1

    // 2번째 계단부터 n번째 계단까지 방법의 수를 구함
    for (i in 2..n) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

fun main() {
    val n = 5  // 예를 들어 계단이 5개인 경우
    println("계단 $n개를 오르는 방법의 수: ${climbStairs(n)}")
    // 출력 예시: 계단 5개를 오르는 방법의 수: 8
}

2. 재귀와 메모이제이션을 활용한 방식

fun climbStairsRecursive(n: Int, memo: MutableMap<Int, Int> = mutableMapOf()): Int {
    // n이 0 또는 1이면 바로 반환
    if (n <= 1) return 1
    // 이미 계산된 값이면 바로 반환
    if (memo.containsKey(n)) return memo[n]!!

    // 재귀 호출과 메모이제이션
    memo[n] = climbStairsRecursive(n - 1, memo) + climbStairsRecursive(n - 2, memo)
    return memo[n]!!
}

fun main() {
    val n = 5
    println("재귀적 접근: 계단 $n개를 오르는 방법의 수: ${climbStairsRecursive(n)}")
    // 출력 예시: 재귀적 접근: 계단 5개를 오르는 방법의 수: 8
}

// 같은 계산을 반복하지 않도록, 한 번 계산한 결과를 memo에 저장한다. 이렇게 하면, 재귀 호출의 중복을 피할 수 있다.

대부분의 테이블에 날짜 데이터가 등록된 컬럼이 있을 것이다. 날짜별로 그룹화 하여 조회하려면 어떻게 해야할까??

1. TRUNC 함수 사용

TRUNC 함수를 사용하면 날짜별로 잘라낼 수 있다.

* 월 단위로 자르는 예시

SELECT TRUNC(REG_DT, 'MM') AS month_start,
       COUNT(*) AS cnt
FROM your_table
GROUP BY TRUNC(REG_DT, 'MM')
ORDER BY month_start;

이 쿼리는 REG_DT의 월의 첫 날(예: 2024-08-01) 기준으로 그룹화하여 각 월에 해당하는 데이터 건수를 보여준다.

2. TO_CHAR 함수 사용 

날짜를 원하는 형식(예: 'YYYY-MM')으로 변환하여 그룹화할 수도 있다.

SELECT TO_CHAR(REG_DT, 'YYYY-MM') AS month,
       COUNT(*) AS cnt
FROM your_table
GROUP BY TO_CHAR(REG_DT, 'YYYY-MM')
ORDER BY month;

* 만약 REG_DT 컬럼이 문자열 형식이라면, 먼저 TO_DATE 또는 TO_TIMESTAMP 함수를 사용하여 날짜로 변환해야 한다.

실시간 통신은 채팅, 알림, 게임. 금융 거래 등 다양한 분야에서 핵심 기술로 사용된다. 예를 들어, 소셜 미디어에서 친구가 게시물을 올릴 때 실시간 알림이 전송되는 경우, WebSocket을 통해 효율적으로 구현할 수 있다. 추후에 어떤 서비스를 구현해 볼지 모르기 때문에 한번 관련된 내용을 정리해두자

기본 개념을 먼저 이해해보자 

1. HTTP 프로토콜

HTTP(HyperText Transfer Protocol)는 웹의 기본 통신 프로토콜이다. 

• 요청-응답 구조 : 클라이언트가 요청하면 서버가 응답
• 단발성 연결 : 요청 후 연결 종료
• 비상태성 : 각 요청이 독립적

위처럼 HTTP의 한계는 실시간 상호작용에 적합하지 않다는 점이다. 실시간 데이터 전송이나 서버의 지속적인 이벤트 알림은 HTTP만으로 구현하기 어렵다.

2. WebSocket이란?

WebSocket은 HTTP와 달리 양방향, 지속적인 연결을 제공하는 프로토콜이다. 

• 지속 연결 : 클라이언트와 서버가 한 번 연결되면 계속해서 데이터를 주고받을 수 있다.
• 양방향 통신 : 서버가 클라이언트에게 자유롭게 메시지를 전송할 수 있다.
• 실시간성 : 낮은 지연시간으로 실시간 데이터를 처리할 수 있다.

HTTP와 WebSocket의 차이점을 표로 만들어보자

실시간 애플리케이션에서 왜 WebSocket을 선호하는지 알 것 같다. 그러면 WebSocket의 동작 원리에 대해서 알아보자

3. WebSocket의 동작 원리

3.1 핸드쉐이크 과정

WebSocket 통신은 HTTP 핸드쉐이크로 시작한다.

1. 클라이언트 요청 : 클라이언트는 HTTP 업그레이드 헤더를 포함하여 서버에 연결 요청을 보낸다.
2. 서버 응답 : 서버는 요청을 수락하고, 프로토콜을 WebSocket으로 전환하는 응답을 보낸다.
3. 연결 수립 : 이후 연결은 TCP기반의 지속 연결로 전황되어 데이터를 주고받는다.

이 과정을 통해 기존 HTTP 환경에서도 WebSocket을 사용할 수 있는 유연성을 제공한다.

3.2 연결 유지 및 메시지 교환

연결이 성립되면 클라이언트와 서버는 프레임 단위로 메시지를 주고받는다.

• 텍스트 프레임 : 일반 텍스트 메시지 전송
• 바이너리 프레임 : 이미지, 파일 등 이진 데이터 전송
• 컨트롤 프레임 : 연결 종료, 핑/퐁 등 관리 메시지 전송

3.3 연결 종료 메커니즘

연결 종료 시에는 양측에서 종료 요청을 보내고, 지정된 절차에 따라 연결을 정상적으로 마감한다. 이 과정을 예기치 않은 연결 종료를 방지하고, 자원 누수를 최소화한다.

Spring Boot를 활용해서 간단한 서비스를 만들어보자

Spring Boot에서는 기본적으로 WebSocket을 지원하고, 모듈도 제공해준다.

• spring-boot-starter-websocket : WebSocket 관련 의존성 자동 구성
• STOMP(Simple Text Oriented Messaging Protocol) : 메시지 브로커와의 통신 지원

Spring Boot에서 WebSocket을 사용하려면 Gradle 또는 Maven을 통해 의존성을 추가해준다.

*gradle 예시

implementation 'org.springframework.boot:spring-boot-starter-websocket'

간단한 실시간 알림 서비스 

• 사용자가 실시간으로 이벤트를 감지
• 서버는 이벤트 발생 시 즉시 모든 관련 클라이언트에 알림 전달
• 연결 상태를 지속적으로 유지하여 지연 없이 메시지 전송

WebSocket 설정 클래스

@Configuration
@EnableWebSocket
class WebSocketConfig : WebSocketConfigurer {
    override fun registerWebSocketHandlers(registry: WebSocketHandlerRegistry) {
        registry.addHandler(NotificationHandler(), "/ws/notifications")
            .setAllowedOrigins("*")
    }
}

WebSocket 핸들러 클래스

class NotificationHandler : TextWebSocketHandler() {

    override fun handleTextMessage(session: WebSocketSession, message: TextMessage) {
        val receivedText = message.payload
        val response = TextMessage("알림: $receivedText")
        session.sendMessage(response)
    }

    override fun afterConnectionEstablished(session: WebSocketSession) {
        println("클라이언트 연결됨: ${session.id}")
    }

    override fun afterConnectionClosed(session: WebSocketSession, status: CloseStatus) {
        println("클라이언트 연결 종료: ${session.id}")
    }
}

실행 클래스

@SpringBootApplication
class WebSocketApplication

fun main(args: Array<String>) {
    runApplication<WebSocketApplication>(*args)
}

화면

<!DOCTYPE html>
<html lang="ko">
<head>
    <meta charset="UTF-8">
    <title>Kotlin WebSocket 테스트</title>
</head>
<body>
    <h2>실시간 알림 테스트</h2>
    <input id="input" type="text" placeholder="메시지 입력">
    <button onclick="send()">전송</button>
    <div id="log"></div>

    <script>
        const ws = new WebSocket("ws://localhost:8080/ws/notifications");
        ws.onmessage = (event) => {
            const log = document.getElementById('log');
            log.innerHTML += `<p>${event.data}</p>`;
        };

        function send() {
            const input = document.getElementById('input');
            ws.send(input.value);
            input.value = '';
        }
    </script>
</body>
</html>