121. 주식을 사고 팔기 가장 좋은 시점

이 문제는 주어진 주식 가격 배열에서 최대 이익을 얻기 위해 주식을 사는 날과 파는 날을 선택하는 문제입니다. 이 문제를 해결하기 위해 우리는 주식을 사는 날의 가격을 최소화하고, 주식을 파는 날의 가격을 최대화하여 최대 이익을 계산하는 방법을 사용합니다.

1. 알고리즘의 핵심 아이디어

알고리즘의 핵심은 주식을 사는 날의 가격을 지속적으로 추적하여 가장 낮은 가격에 사고, 이후의 날들 중 가장 높은 가격에 파는 것입니다. 이렇게 하면 최대 이익을 얻을 수 있습니다. 중요한 점은 주식을 사는 날은 파는 날보다 항상 앞서야 한다는 것입니다.

2. 코드의 주요 로직 설명

• minPrice 변수는 현재까지의 최소 주식 가격을 저장하는 데 사용됩니다.
• profit 변수는 현재까지의 최대 이익을 저장합니다.
• 배열을 순회하면서 각 날의 주식 가격을 확인하고, minPrice와 profit을 업데이트합니다.

3. 각 단계별 동작 과정

1. 초기화:

   • minPrice를 첫 번째 날의 가격으로 설정합니다. 이는 우리가 첫 날에 주식을 산다고 가정하는 것입니다.
   • profit을 0으로 설정합니다. 초기에는 이익이 없기 때문입니다.

2. 배열 순회:

   • 두 번째 날부터 마지막 날까지 배열을 순회합니다.
   • 각 날의 주식 가격과 현재 minPrice를 비교하여 더 낮은 가격을 minPrice에 저장합니다. 이는 더 저렴한 가격에 주식을 사기 위함입니다.
   • 현재 날의 가격에서 minPrice를 뺀 값과 현재 profit을 비교하여 더 큰 값을 profit에 저장합니다. 이는 최대 이익을 계산하기 위함입니다.

3. 결과 반환:

   • 순회가 끝난 후 profit에는 최대 이익이 저장되어 있습니다. 이를 반환합니다.

4. 핵심 변수들의 역할

• minPrice: 현재까지 발견한 최소 주식 가격을 저장하여, 가장 저렴한 가격에 주식을 살 수 있도록 합니다.
• profit: 현재까지 계산된 최대 이익을 저장하여, 가장 높은 이익을 얻을 수 있도록 합니다.

5. 왜 이 방법이 효과적인지

이 방법은 한 번의 배열 순회로 문제를 해결할 수 있어 매우 효율적입니다. 시간 복잡도는 O(n)으로, 이는 배열의 길이에 비례하여 동작합니다. 또한, 추가적인 배열이나 복잡한 자료 구조 없이 상수 공간을 사용하므로 공간 복잡도도 O(1)입니다. 이러한 효율성 덕분에 큰 입력 배열에서도 빠르게 최대 이익을 계산할 수 있습니다.

이 알고리즘은 주식을 사는 날과 파는 날의 순서를 자연스럽게 유지하며, 매일의 가격 변동을 고려하여 최적의 거래 시점을 찾습니다. 이는 주식 거래 문제에서 매우 직관적이고 효과적인 접근 방식입니다.