[알고리즘]분할과 정복 알고리즘

소개글

: 연속하는 날들에 대하여 각 날의 주식 가격이 주어져 있다. 이때 어떤 날에 주식을 산 후, 최대 이익을 남기며 이후의 날에 팔고자 한다. 어떤 날에 사서 어떤 날에 팔면 되는가?
- 두 가지 방법으로 해결하라.
방법 1: O(n2) 시간의 알고리즘
방법 2: 분할과 정복을 이용한O(n log n) 알고리즘

목차

1. 문제정의
2. 알고리즘
3. 분석(시간)
4. 시행결과
5. 소스코드

본문내용

1. 문제정의
: 연속하는 날들에 대하여 각 날의 주식 가격이 주어져 있다. 이때 어떤 날에 주식을 산 후, 최대 이익을 남기며 이후의 날에 팔고자 한다. 어떤 날에 사서 어떤 날에 팔면 되는가?
- 두 가지 방법으로 해결하라.
방법 1: O(n2) 시간의 알고리즘
방법 2: 분할과 정복을 이용한O(n log n) 알고리즘

2. 알고리즘
< 방법 1: O(n2) 시간의 알고리즘 >
0
1
2
3
4
14
2
57
21
4




- i노드 가 0번지부터 마지막 번지(4)까지 loop를 이용하여 탐색을 한다.
- 2중 loop를 이용하여 시작이 j노드는 i노드 하나에 대하여 i부터 마지막 번지까지 탐색한다.
- j번지에서 i번지의 노드값을 빼준 것을 임시로 저장한다.
- 임시로 저장한 이윤과 그 전의 이윤을 비교하여 큰 이윤을 저장한다.
- 이윤을 갱신할 때마다 그 시점의 i노드는 사는 날, j노드는 파는 날로 갱신한다.

< 방법 2: 분할과 정복을 이용한O(n log n) 알고리즘 >
- 재귀함수인 MergeSort를 이용하여 왼쪽배열의 첫 노드 하나만을 가리킨다.
- 배열을 왼쪽과 오른쪽으로 나누는 것은 가운데값[(low+high)/2] 을 구하여 이용한다.
- 노드하나만을 가리키는(BaseCase, low와 high가 같음)가 되면 리턴하여 오른쪽 배열의 BaseCase를 가지도록 계속 재귀한다.
- BaseCase가 되면 왼쪽의 배열에서는 최소값을, 오른쪽의 배열에서는 최대값을 구한다.
- 최대값에서 최소값을 뺀 값을 이전의 이윤보다 크면 갱신한다.
- 이윤을 갱신할 때 최소값과 최대값의 번지를 저장한다.(사고 파는 날짜)

참고 자료

없음