자료구조 프로그래밍_Lab02) 역대 최고가 주식

자료구조 프로그래밍_Lab02) 역대 최고가 주식

문제.

어느 기업의 주식가격을 날짜별로

Day 1. 100 

Day 2. 50 

Day 3. 70 

Day 4. 60 

Day 5. 30 

Day 6. 120 

Day 7. 50 

와 같이 제시한다.

해당 주식 가격이 며칠 동안 최고가 였는지를 비교하며 기록하여 비교횟수와 함께 출력한다.

단, 단순배열비교와 스택의 두 가지 방법을 사용하여 비교한다.

해결 알고리즘.

주어진 주식가격은 1차원 배열의 Stock에 저장하고

각 요일별 최고가는 span에 저장한다.

알고리즘 <1> 단순 배열 비교 방법

0. span 기록 배열을 1로 초기화(최소 1일동안 최고가 일 수 있으므로)

1. for 문을 통해 2번 째 날짜(인덱스 1) 부터 반복문처리

2. count라는 변수를 주어진 날짜 -1 로 주고 while(count>=0) 문으로 처리 및 비교

3. 0으로 가는 동안 해당 값보다 큰 값을 만나면 두 index의 차이를 기록후 탈출.

4.  만약 count가 0이 된다면 최고기록(날짜 +1)으로 기록후 탈출. 그렇지 않다면 count-- 

// 방법 1. 되돌아가면서 비교하기
void method1() {
    
    int count, compare=0;
 
    // span 배열 할당
    int *span;
    span= (int *)malloc(sizeof(int)*size);
 
    // span 값 초기화
    for (int i = 0; i < size; i++) {
        span[i] = 1;
    }
 
    // 반복하기
    for (int i = 1; i < size; i++) {
        count = i-1; // 출발지점
        
        // 0까지 가기
        while (count >= 0) {
            compare++; // 비교횟수 증가
 
            // 현재 i의 값보다 더 큰 값을 만나면 span에다 값 넣고 탈출
            if (stock[i] < stock[count]) {
                span[i] = i - count;
                break;
            }
 
            if (count == 0) {
                span[i] = i + 1; // 끝까지 왔으면 
            }
 
            count--; // 하나씩 줄이기
            
        }
    }
 
    // 출력하기
    fprintf(fp2, "1번 방법 비교횟수 : %d\n", compare);
    for (int i = 0; i < size; i++)
        fprintf(fp2, "%d ", span[i]);
 
    // 할당해제
    free(span);
}

알고리즘<2> 스택사용

주의사항) 스택에는 index 값을 넣고 빼고 한다!

0. 기록배열 1로 초기화

1. 첫 번째 날짜(인덱스 0) 값을 push

2. for 문 2번 째 날짜 (인덱스 1) 부터 반복문 처리

3. while 반복문으로 처리, 안에서 스택 top 부터 비교를 하는데 해당 날짜 (인덱스) 값보다 큰 값을 만나면 span 배열에다 날짜 차이(인덱스 차이)의 값을 주고 탈출.

4. 그렇지 않다면 stack을 하나 pop 하고 stack이 empty가 된다면 최고기록(인덱스+1)으로 기록 후 스택에 해당 날짜(인덱스) 값 push

// 방법 2. 스택사용
void method2() {
 
    // span 배열 할당
    int *span, compare=0;
    span = (int *)malloc(sizeof(int)*size);
 
    // span 값 초기화
    for (int i = 0; i < size; i++) {
        span[i] = 1;
    }
    
    // 시작값 stack에 넣기
    push(0);
 
    // 반복하기
    for (int i = 1; i < size; i++) {
        
        while (1) {
            // 스택의 top 부터 비교해서 올라가기
            compare++;
 
            // 현재가 더 크면
            if (stock[stack[top]] < stock[i]) {
                pop(); // 스택 빼버리기
            }
 
            // 현재가 더 작으면
            else {
                // 최대 기록에서 내보다 큰 span의 index 차를 넣는다
                span[i] = (i) - stack[top];
                push(i); // 현재값 스택에넣기
                break;
            }
 
            // 스택이 빌 때 까지 왔으면
            if (top == -1) {
                span[i] = i + 1; // 최대치
                push(i);
                break;
            }
        }
    }
    // 출력하기
    fprintf(fp2, "2번 방법 비교횟수 : %d\n", compare);
    for (int i = 0; i < size; i++)
        fprintf(fp2, "%d ", span[i]);
 
    // 할당해제
    free(span);
}