[java] 스택을 이용한 스팬 알고리즘 구현하기

05 Dec 2023

java

스팬 알고리즘은 시계열 데이터에서 특정 기간 내에 발생한 이벤트의 빈도를 계산하는데 사용되는 데이터 구조입니다. 이 알고리즘을 구현하는 방법 중 하나는 스택을 사용하는 것입니다. 이 글에서는 자바를 사용하여 스택을 이용한 스팬 알고리즘의 구현 방법을 알아보겠습니다.

스팬 알고리즘 이란?

스팬(span)은 시간 내에서 연속적으로 발생한 이벤트의 개수를 나타냅니다. 스팬 알고리즘은 시계열 데이터에서 각 데이터 값의 스팬을 계산하는데 사용됩니다. 예를 들어, 일일 주식 시장 데이터에서 각 날짜별로 해당 날짜에 이전에 몇 번연속으로 상승한 데이터가 있는지 계산할 수 있습니다.

스팬 알고리즘의 구현 방법

스팬 알고리즘을 구현하기 위해 스택을 사용할 수 있습니다. 스택은 후입선출(LIFO) 방식의 데이터 구조로, 배열이나 연결 리스트와 같은 다른 데이터 구조에 비해 삽입, 삭제, 조회 등의 연산이 효율적으로 이루어집니다.

아래는 자바로 스팬 알고리즘을 구현한 예제 코드입니다.

import java.util.*;

public class SpanAlgorithm {
    public static int[] calculateSpan(int[] prices) {
        int[] span = new int[prices.length]; // 스팬 값을 저장할 배열
        Stack<Integer> stack = new Stack<Integer>(); // 인덱스를 저장할 스택
        int n = prices.length;

        // 첫 번째 요소의 스팬은 항상 1
        span[0] = 1;
        stack.push(0);

        for (int i = 1; i < n; i++) {
            // 현재 요소보다 작거나 같은 값의 인덱스들을 스택에서 제거
            while (!stack.empty() && prices[stack.peek()] <= prices[i])
                stack.pop();

            // 스택이 비어있으면 현재 요소 이전에 작은 값이 없으므로 스팬은 현재 인덱스+1
            // 그렇지 않으면 현재 인덱스에서 현재 요소보다 작은 값의 인덱스를 뺀 값이 스팬
            span[i] = (stack.empty()) ? (i + 1) : (i - stack.peek());

            // 현재 인덱스를 스택에 추가
            stack.push(i);
        }

        return span;
    }

    public static void main(String[] args) {
        int[] prices = { 100, 80, 60, 70, 60, 75, 85 }; // 가격 데이터
        int[] span = calculateSpan(prices);

        System.out.println("스팬 값: " + Arrays.toString(span));
    }
}

위 코드는 calculateSpan() 메서드를 사용하여 시계열 데이터에 대한 스팬 값을 계산하는 예제입니다. 이를 실행하면 [1, 1, 1, 2, 1, 4, 6]이라는 결과가 출력됩니다.

요약

이 글에서는 스택을 이용하여 스팬 알고리즘을 구현하는 방법을 알아보았습니다. 스팬 알고리즘은 시계열 데이터에서 연속적으로 발생한 이벤트의 개수를 계산하는데 사용되며, 스택은 이를 구현하는데 효율적인 자료구조입니다. 스팬 알고리즘은 주식 시장 데이터 및 기타 시계열 데이터에 대한 분석에 유용하게 사용될 수 있습니다.

스팬 알고리즘 이란?

스팬 알고리즘의 구현 방법

요약

참고 자료