[SISS/C언어 스터디] 2학기 5주차 스터디

2학기 5주차 스터디

백준 제출 내역 화면 캡쳐

 

자율 2문제를 풀어서 제출하면 됩니다.

언어는 C언어만 가능합니다.

​레벨 제한사항: Silver 5 이상

 

10025

---

• 누적 합, 슬라이딩 윈도우 → 슬라이딩 윈도우를 사용하여 주어진 범위 내의 최대 합을 구함

#include <stdio.h>

#define MAX_SIZE 1000001 // 배열 최대 크기

// 큰 값 반환
int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int N, K;
    
    // N, K 입력
    scanf("%d %d", &N, &K);

    // 배열 선언 및 초기화
    int arr[MAX_SIZE] = {0};

    // 배열에 저장
    for (int i = 0; i < N; i++) {
        int g, x;
        // 값(g), 배열 위치(x)
        scanf("%d %d", &g, &x);
        arr[x] = g; // x를 인덱스로 하는 배열 위치에 g를 저장
    }

    // K 범위를 2 * K + 1로 변환 (K만큼 넓힘)
    K = 2 * K + 1;
    
    int sum = 0; // 슬라이딩 윈도우 합
    int ans = 0; // 최대 합 저장 변수
    
    // 배열 순차 탐색
    for (int i = 0; i <= MAX_SIZE; i++) {
        // 슬라이딩 윈도우에서 왼쪽 끝 제거
        if (i >= K) {
            sum -= arr[i - K]; // 범위에서 벗어난 값을 합에서 뺌
        }
        // 슬라이딩 윈도우에 오른쪽 값 추가
        sum += arr[i]; // 현재 위치 값 더하기
        // 최대 합 계산
        ans = max(ans, sum); // 최대 값 갱신
    }

    // 출력
    printf("%d\n", ans);
    return 0;
}

 

4948

---

• 소수 판정 → 에라토스테네스의 체 이용

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

// 에라토스테네스의 체를 사용하여 소수 판별
void sieve(bool* isPrime, int limit) {
    // 0, 1(소수 아님)
    isPrime[0] = false;
    isPrime[1] = false;

    // 2에서 limit의 제곱근까지 증가
    for (int i = 2; i <= sqrt(limit); ++i) {
        // 소수일 경우
        if (isPrime[i]) {
            // i의 배수는 소수가 아님
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// n보다 큰 소수 개수
int countPrimes(int n) {
    int limit = 2 * n; // 2n까지 판별
    
    // 소수 판별을 위한 배열 할당
    bool* isPrime = (bool*)malloc((limit + 1) * sizeof(bool));
    
    // 배열 초기화(모두 소수)
    for (int i = 0; i <= limit; i++) {
        isPrime[i] = true;
    }

    // 소수 판별
    sieve(isPrime, limit);

    int count = 0;  // 소수 개수 저장 변수
    for (int i = n + 1; i <= limit; ++i) {
        if (isPrime[i]) {
            count++;
        }
    }

    free(isPrime); // 메모리 해제
    return count; // 소수 개수 반환
}

int main() {
    while (1) {
        int n;
        // n 입력
        scanf("%d", &n);

        // 0이 입력시 종료
        if (n == 0) {
            break;
        }

        // 소수 개수 계산 및 출력
        int result = countPrimes(n);
        printf("%d\n", result);
    }

    return 0;
}