부분합 문제

Honor's method (특정 진법의 수를 10진법으로 변환)

char vect[10];
int result;
 
// a진법을 10진법으로 변환
int honor()
{
    for (int i = 0; vect[i]; ++i) {
        
        if (vect[i] >= 'A' && vect[i] <= 'Z') {
            result = result * a + (vect[i] - 'A' + 10);
        }
        else {
            result = result * a + (vect[i] - '0');
        }
    }
 
    // 첫 비트가 음수일경우 적절히 result 에서 값을 빼주기
    if (result > 127)
        result -= 256;
}
 
// 10진법을 b진법으로 변환
void reverse_honor()
{
    int temp[100] = { 0 };
    int t = 0;
 
    while (1) {
        temp[t++] = result % b;
        result /= b;
 
        if (result == 0) break;
    }
 
    for (int i = t - 1; i >= 0; i--) {
        if (temp[i] >= 10) {
            printf("%c", 'A' + temp[i] - 10);
        }
        else {
            printf("%d", temp[i]);
        }
    }
    printf("\n");
}

연속 부분합의 최대값 구하기

// 연속 부분합
int main()
{
    int sum = 0;
    int max = -21e8;
    for (int i = 0; i < n; i++) {
        sum += vect[i];    // 현재까지의 부분합
        
        // 현재까지의 부분합이 max보다 크면 max로
        if (sum > max) max = sum;    
 
        // 현재까지의 부분합이 나 자신보다 작으면 부분합을 나 자신으로
        if (sum < vect[i]) sum = vect[i];    
    }
    if (sum > max) max = sum;    // 마지막 값 처리
 
    printf("%d", max);
 
    return 0;
}

 

슬라이딩 어려운 문제중 하나.

ABACCABAAATAAG

위에서 특정영역(5개)을 골랐을때 가장 알파벳이 많이 등장하는 범위와 갯수는?

alph[26] 이런식으로 배열을 만들어 놓고 카운트해서 체크하는 방법 사용

 

2X2 map의 부분합을 구하는건

(0,0)~(x,y)를 구하는건 sum(x-1, y)+sum(x, y-1)-sum(x-1,y-1)+data(x,y) 이렇게 하면되고

(x1,y1)~(x2,y2)를 구하는건 sum(x2,y2)-sum(x2,y1)-sum(x1,y2)+sum(x1,x2) 이렇게 하면된다.