1. 문제 : 어떤 주식에 대해 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요.
  2. 주가 테이블
  3. 문제 분석과 모델링
    1. 주식 거래로 수익을 내는 가장 좋은 방법은 ‘가장 쌀 때 사서 가장 비쌀 때 파는 것’
    2. 얼핏 생각하면 주가(주식의 가격)의 최댓값에서 주가의 최솟값을 뺀 것으로 착각하기 쉬움
    3. 표 18-1을 예로 들면, 6월 1일의 주가 10,300원이 최댓값이고 6월 5일의 주가 7,800원이 최솟값
    4. 하지만 아직 사지도 않은 주식을 6월 1일에 먼저 팔고 6월 5일에 주식을 살 수는 없으므로 단순히 최댓값과 최솟값을 구하는 것만으로는 올바른 답을 얻을 수 없음
  4. 날짜 정보는 필요없고 주가만 필요하므로 stock 리스트 생성
  5. 가능한 모든 경우 비교 알고리즘
  6. 1회의 반복으로 최대 수익 찾기 알고리즘
  7. 두 알고리즘 비교
  8. 계산 복잡도
    1. 알고리즘 1 : O(n^2),  동명이인 찾기1 알고리즘과 유사
    2. 알고리즘 2 : O(n),      동명이인 찾기2 알고리즘과 유사
error: Content is protected !!