[Algorithm] C++/Python 백준 13416번 : 주식 투자

주식 투자는 미래의 이익을 기대하며 자본을 투입하는 행위이다. 하지만 매일매일의 시장 상황을 정확하게 예측하는 것은 어려운 일이다. 이번에 다룰 백준 13416번 문제는 주어진 주식 데이터에서 최대의 이익을 낼 수 있는 방법을 찾아내는 문제이다. 이 글에서는 문제의 상세한 설명과 함께 효율적인 알고리즘을 통해 문제를 해결해보도록 하겠다.

문제 : https://www.acmicpc.net/problem/13416

문제 설명

환규는 오늘부터 주식 투자를 하려고 한다. 그는 정보를 수집한 결과 A사, B사, C사 세 개의 회사에 투자하기로 결정했다. 그러나 그는 어떤 주식이 오를지, 떨어질지 예측하는 것이 아직은 힘들었다. 그래서 다음과 같은 투자 전략을 세웠다.

하루에는 최대 한 개의 회사 주식만 살 수 있다.
서로 다른 날에는 서로 다른 회사의 주식을 살 수 있지만, 하루에는 최대 한 개의 회사 주식만 구매한다.
매일 장이 열리기 전에 그날 주식을 살 회사를 정하고, 장이 열릴 때 해당 회사의 주식을 산다.
장이 닫힐 때 그날 산 주식을 모두 판다.
만약 세 회사 중 어느 곳도 수익이 날 것 같지 않으면 주식을 구매하지 않아도 된다.

환규는 주식을 처음 해보기 때문에 이 전략으로 주식 투자를 했을 때 얼마나 이익을 낼 수 있는지 궁금해졌다. 그래서 투자하려는 회사들의 지난 N일 동안의 주식 데이터를 이용해 N일 동안 위의 규칙을 지키며 주식 투자를 했을 때 과연 얼마를 벌 수 있는지 계산해 보기로 했다.

환규는 각 회사별로 장이 열릴 때 주식을 사고, 장이 닫힐 때 모두 팔았을 경우 매일 얼마를 벌 수 있었는지 정리했다. 다음은 N = 4일 때 환규가 정리한 데이터를 나타내는 표이다.

날짜	A사	B사	C사
1일	500	800	200
2일	300	0	300
3일	-100	-200	-400
4일	600	200	300

양수는 이익을, 음수는 손해를 나타내며, 0은 이익도 손해도 없음을 의미한다.
예를 들어, 1일째에 A사의 주식을 장이 열릴 때 사고, 장이 닫힐 때 팔면 500의 이익을 얻을 수 있었다.
3일째에 C사의 주식을 장이 열릴 때 사고, 장이 닫힐 때 판다면 400의 손해가 발생한다.

데이터를 분석하던 환규는 자신이 정리한 데이터를 이용해서 N일 동안 규칙을 지키면서 매일 최적의 투자를 할 경우 최대 얼마를 벌 수 있었는지 궁금해졌다.

예를 들어 위 표에서:
- 1일째에는 B사의 주식을 사면 가장 많은 이익을 남길 수 있다 (800).
- 2일째에는 A사 또는 C사의 주식을 사면 가장 많은 이익을 남길 수 있다 (300).
- 3일째에는 어떤 주식을 사도 손해가 나므로 주식을 사지 않는다.
- 4일째에는 A사의 주식을 사면 된다 (600).
이렇게 주식 투자를 할 경우 환규는 800 + 300 + 0 + 600 = 1700으로, 최대 1700의 이익을 남길 수 있다.

문제: 환규가 N일 동안 위의 규칙을 지키며 최적의 투자를 했을 때 얻을 수 있는 최대 이익을 계산하는 프로그램을 작성하시오.

접근 방식

이 문제는 각 날마다 선택할 수 있는 가장 큰 이익을 선택하는 그리디(Greedy) 알고리즘으로 해결할 수 있다. 매일 세 회사의 손익 중에서 양수인 값 중 최대값을 선택하고, 음수이거나 0이면 그날은 투자를 하지 않는다.

알고리즘 단계

입력 처리:
- 테스트 케이스 수 T를 입력받는다.
- 각 테스트 케이스마다 주식 데이터의 일수 N을 입력받는다.
매일의 최대 이익 계산:
- 각 날마다 A사, B사, C사의 손익을 입력받는다.
- 세 회사의 손익 중에서 최대값을 찾는다.
- 최대값이 양수이면 총 이익에 더하고, 그렇지 않으면 아무 것도 하지 않는다.
결과 출력:
- 총 이익을 출력한다.

이 알고리즘은 매일 최적의 선택을 하므로 전체 기간 동안의 최대 이익을 구할 수 있다. 시간 복잡도는 **O(N)**으로, N은 주식 데이터의 일수이다.

C++ 코드와 설명

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream> // 표준 입출력 사용
#include <algorithm> // max 함수 사용
using namespace std;

int main() {
    int T; // 테스트 케이스 수
    cin >> T; // 테스트 케이스 입력
    while (T--) {
        int N; // 주식 데이터의 일수
        cin >> N; // 일수 입력
        long long totalProfit = 0; // 총 이익 초기화
        for (int i = 0; i < N; ++i) {
            int A, B, C; // 각 회사의 손익
            cin >> A >> B >> C; // 손익 입력
            int maxProfit = max({A, B, C}); // 세 회사 중 최대 이익
            if (maxProfit > 0) { // 최대 이익이 양수인 경우
                totalProfit += maxProfit; // 총 이익에 더하기
            }
        }
        cout << totalProfit << endl; // 결과 출력
    }
    return 0;
}

코드 설명

헤더 파일 포함
- #include <iostream>: 표준 입출력을 사용하기 위해 포함한다.
- #include <algorithm>: max 함수를 사용하기 위해 포함한다.
using namespace std;
- 표준 네임스페이스를 사용하여 코드의 가독성을 높인다.
메인 함수 정의
- int main() { ... }: 프로그램의 시작점이다.
테스트 케이스 처리
- int T; cin >> T;: 테스트 케이스 수를 입력받는다.
- while (T--) { ... }: 테스트 케이스 수만큼 반복한다.
주식 데이터 처리
- int N; cin >> N;: 주식 데이터의 일수를 입력받는다.
- long long totalProfit = 0;: 총 이익을 저장할 변수를 초기화한다.
- for (int i = 0; i < N; ++i) { ... }: 각 날에 대해 반복한다.
  - int A, B, C; cin >> A >> B >> C;: 각 회사의 손익을 입력받는다.
  - int maxProfit = max({A, B, C});: 세 회사의 손익 중 최대값을 찾는다.
  - if (maxProfit > 0) { totalProfit += maxProfit; }: 최대값이 양수이면 총 이익에 더한다.
결과 출력
- cout << totalProfit << endl;: 총 이익을 출력한다.
프로그램 종료
- return 0;: 프로그램을 정상적으로 종료한다.

코드 동작 단계별 설명

입력 받기
- 프로그램은 먼저 테스트 케이스 수 T를 입력받는다.
테스트 케이스 반복
- 각 테스트 케이스마다 다음을 수행한다.
  - 주식 데이터의 일수 N을 입력받는다.
  - 총 이익을 저장할 변수 totalProfit을 0으로 초기화한다.
일별 데이터 처리
- N일 동안 다음을 반복한다.
  - A사, B사, C사의 손익 A, B, C를 입력받는다.
  - max({A, B, C})를 사용하여 세 값 중 최대값 maxProfit을 찾는다.
  - maxProfit이 양수이면 totalProfit에 더한다.
결과 출력
- 각 테스트 케이스마다 계산된 totalProfit을 출력한다.

C++ without library 코드와 설명

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h> // 표준 입출력 사용

int main() {
    int T; // 테스트 케이스 수
    scanf("%d", &T); // 테스트 케이스 입력
    while (T--) {
        int N; // 주식 데이터의 일수
        scanf("%d", &N); // 일수 입력
        long long totalProfit = 0; // 총 이익 초기화
        for (int i = 0; i < N; ++i) {
            int A, B, C; // 각 회사의 손익
            scanf("%d %d %d", &A, &B, &C); // 손익 입력
            int maxProfit = A; // 최대 이익 초기화
            if (B > maxProfit) maxProfit = B; // B와 비교하여 최대값 갱신
            if (C > maxProfit) maxProfit = C; // C와 비교하여 최대값 갱신
            if (maxProfit > 0) { // 최대 이익이 양수인 경우
                totalProfit += maxProfit; // 총 이익에 더하기
            }
        }
        printf("%lld\n", totalProfit); // 결과 출력
    }
    return 0;
}

코드 설명

헤더 파일 포함
- #include <stdio.h>: 표준 입출력을 사용하기 위해 포함한다.
메인 함수 정의
- int main() { ... }: 프로그램의 시작점이다.
테스트 케이스 처리
- int T; scanf("%d", &T);: 테스트 케이스 수를 입력받는다.
- while (T--) { ... }: 테스트 케이스 수만큼 반복한다.
주식 데이터 처리
- int N; scanf("%d", &N);: 주식 데이터의 일수를 입력받는다.
- long long totalProfit = 0;: 총 이익을 저장할 변수를 초기화한다.
- for (int i = 0; i < N; ++i) { ... }: 각 날에 대해 반복한다.
  - int A, B, C; scanf("%d %d %d", &A, &B, &C);: 각 회사의 손익을 입력받는다.
  - int maxProfit = A;: 최대 이익을 A로 초기화한다.
  - if (B > maxProfit) maxProfit = B;: B와 비교하여 최대값을 갱신한다.
  - if (C > maxProfit) maxProfit = C;: C와 비교하여 최대값을 갱신한다.
  - if (maxProfit > 0) { totalProfit += maxProfit; }: 최대값이 양수이면 총 이익에 더한다.
결과 출력
- printf("%lld\n", totalProfit);: 총 이익을 출력한다.
프로그램 종료
- return 0;: 프로그램을 정상적으로 종료한다.

코드 동작 단계별 설명

입력 받기
- 표준 입력 함수를 사용하여 테스트 케이스 수 T를 입력받는다.
테스트 케이스 반복
- 각 테스트 케이스마다 다음을 수행한다.
  - 주식 데이터의 일수 N을 입력받는다.
  - 총 이익을 저장할 변수 totalProfit을 0으로 초기화한다.
일별 데이터 처리
- N일 동안 다음을 반복한다.
  - 각 회사의 손익 A, B, C를 입력받는다.
  - 최대값 maxProfit을 A로 초기화한다.
  - B와 비교하여 더 큰 값을 maxProfit에 저장한다.
  - C와 비교하여 더 큰 값을 maxProfit에 저장한다.
  - maxProfit이 양수이면 totalProfit에 더한다.
결과 출력
- 각 테스트 케이스마다 계산된 totalProfit을 출력한다.

Python 코드와 설명

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
T = int(input())  # 테스트 케이스 수 입력
for _ in range(T):
    N = int(input())  # 주식 데이터의 일수 입력
    total_profit = 0  # 총 이익 초기화
    for _ in range(N):
        A, B, C = map(int, input().split())  # 각 회사의 손익 입력
        max_profit = max(A, B, C)  # 세 회사 중 최대 이익
        if max_profit > 0:  # 최대 이익이 양수인 경우
            total_profit += max_profit  # 총 이익에 더하기
    print(total_profit)  # 결과 출력

코드 설명

테스트 케이스 처리
- T = int(input()): 테스트 케이스 수를 입력받는다.
- for _ in range(T):: 테스트 케이스 수만큼 반복한다.
주식 데이터 처리
- N = int(input()): 주식 데이터의 일수를 입력받는다.
- total_profit = 0: 총 이익을 저장할 변수를 초기화한다.
- for _ in range(N):: 각 날에 대해 반복한다.
  - A, B, C = map(int, input().split()): 각 회사의 손익을 입력받는다.
  - max_profit = max(A, B, C): 세 회사의 손익 중 최대값을 찾는다.
  - if max_profit > 0: total_profit += max_profit: 최대값이 양수이면 총 이익에 더한다.
결과 출력
- print(total_profit): 총 이익을 출력한다.

코드 동작 단계별 설명

입력 받기
- 표준 입력 함수를 사용하여 테스트 케이스 수 T를 입력받는다.
테스트 케이스 반복
- 각 테스트 케이스마다 다음을 수행한다.
  - 주식 데이터의 일수 N을 입력받는다.
  - 총 이익을 저장할 변수 total_profit을 0으로 초기화한다.
일별 데이터 처리
- N일 동안 다음을 반복한다.
  - 각 회사의 손익 A, B, C를 입력받는다.
  - max(A, B, C)를 사용하여 최대값 max_profit을 찾는다.
  - max_profit이 양수이면 total_profit에 더한다.
결과 출력
- 각 테스트 케이스마다 계산된 total_profit을 출력한다.

결론

이번 문제는 각 날마다 최대 이익을 가져다주는 주식을 선택하는 간단한 그리디 알고리즘으로 해결할 수 있었다. 매일의 데이터에서 최대값을 선택하고, 그 값이 양수인 경우에만 총 이익에 더하는 방식으로 문제를 풀었다. 이 과정에서 시간 복잡도는 **O(N)**으로 매우 효율적이다.

문제를 풀면서 입력 데이터를 어떻게 효율적으로 처리할지, 그리고 그리디 알고리즘의 적용 가능성을 확인하는 것이 중요하다는 것을 다시 한 번 느꼈다. 또한, 코드를 작성할 때 변수의 자료형에 주의하여 큰 수의 합산에서도 오버플로우가 발생하지 않도록 해야 한다.

앞으로도 다양한 문제에서 그리디 알고리즘을 적용할 수 있는지 고민해보고, 효율적인 알고리즘 설계에 집중해야겠다.