Sevity Blog

으허.. 머리에 쥐나긴했는데.. chatGPT한테 힌트 받고 스스로 풀긴했다 ㄷ

재귀를 통해서 하는건데.. 알아두면 두고두고 써먹을거 같긴하다.

#include <bits/stdc++.h>
using namespace std;

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;

ll length[21];
ll val[21];//val[3]이면 F(3)일때 1의 개수

ll solution_sub(int n, ll l, ll r) {
    if (n <= 0) return 1;
    ll answer = 0;
    if (n == 1) {
        for (int i = l; i <= r; i++) {
            if (i != 3) answer += 1;
        }
        return answer;
    }

    //n에 대해서 5등분 해서 재귀로 들어가면 되지 않을까?
    ll lx = (l - 1) / length[n - 1] + 1;
    ll rx = (r - 1) / length[n - 1] + 1;

    ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
    ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);


    if (lx == rx) {
        if(lx!=3) answer += solution_sub(n - 1, nl, nr);
    } else {
        //왼쪽

        //answer += solution_sub(n - 1, l - length[n-1]*((l-1)/length[n-1]), r - length[n - 1] * ((r - 1) / length[n - 1]));
        ll nl = l - length[n - 1] * ((l - 1) / length[n - 1]);
        ll nr = r - length[n - 1] * ((r - 1) / length[n - 1]);
        ll a = ((l - 1) / length[n - 1] + 1) * length[n - 1];
        ll rv = nr; if (r > a) rv = length[n - 1];
        if(lx!=3) answer += solution_sub(n - 1, nl, rv);

        //오른쪽
        a = ((r - 1) / length[n - 1]) * length[n - 1];
        ll lv = nl; if (l < a) lv = 1;
        if(rx!=3) answer += solution_sub(n - 1, lv, nr);

        //중간
        for (int i = lx + 1; i < rx; i++) {
            if (i != 3) answer += val[n - 1];
        }

    }
    return answer;
}


ll solution(int n, ll l, ll r) {
    length[1] = 5; for (int i = 2; i <= 21; i++) length[i] = length[i - 1] * 5;
    val[1] = 4; for (int i = 2; i <= 21; i++) val[i] = val[i - 1] * 4;

    return solution_sub(n, l, r);
}

int main() {
    cout << solution(3, 35, 102) << endl;
    // 예시 입력: n = 2, l = 4, r = 17 → 결과는 8이어야 함
    cout << solution(2, 4, 17) << endl;

    return 0;
}

초기구현.. 거의 한번에 AC받긴함

1. RDD
   • 초창기 Spark가 제공하던 가장 기본적인 분산 데이터 구조
   • 스키마/최적화 부재 → 낮은 수준의 유연성은 높지만, 최적화 성능은 DataFrame/Dataset보다 떨어질 수 있음
2. DataFrame
   • 스키마가 있는 구조화된 데이터셋(Dataset[Row])
   • SQL-like 문법, Catalyst 최적화로 사용 편의성 및 성능 측면에서 개선
   • 컬럼 접근 시 컴파일 타임 타입 체크가 안 됨 → 런타임 오류 가능성
3. Dataset
   • DataFrame의 장점(스키마, 최적화) + RDD의 장점(타입 안정성)을 모두 제공
   • 스칼라의 케이스 클래스 등에 매핑해 사용하면 컴파일 시점에 타입을 체크
   • Spark SQL의 강력한 최적화 엔진(Catalyst) 적용 가능

결국, 데이터에 스키마가 있고 SQL 연산을 자주 사용한다면 DataFrame/Dataset을 추천하고, 추가로 컴파일 시점의 타입 안전성을 원한다면 Dataset을 사용하는 편이 좋습니다. 아직도 아주 범용적이거나, 스키마 없이 자유로운 처리가 필요한 상황(저수준 제어 등)에서는 RDD를 쓰기도 하지만, 일반적인 애플리케이션에서는 주로 DataFrame/Dataset을 사용해 개발/성능 양쪽을 만족시킵니다.

RDD와 List자료구조와의 차이

“방대하게 분산 처리되는 부분”이나 “불변(Immutable)” 같은 특성을 잠시 제쳐두고, 코드를 짤 때 RDD를 다루는 경험적 관점으로 보자면, 일반적인 컬렉션(List나 Seq 같은)을 ‘함수형 스타일’로 조작하는 느낌과 꽤 유사합니다.

• filter, map, flatMap, reduce 등 함수형 연산을 체인으로 연결해 쓰는 방식이, 스칼라의 List나 Seq에 있는 메서드와 유사하기 때문입니다.
• 다만 RDD는 **‘지연 평가(Lazy Evaluation)’**라서, map, filter 등으로 변환(Transformation)을 쌓아두다가, 최종적으로 collect(), count() 등의 **액션(Action)**을 호출할 때 한 번에 계산을 실행한다는 점이 가장 다른 부분입니다.

그래서 “분산, 불변” 등을 빼고 보면, 개발자 입장에서 연산을 작성하는 흐름은 오히려 스칼라의 List/Seq보다 스칼라의 Stream(Lazy)이나 자바의 Stream API 같은 지연성 컬렉션에 더 가깝다고 볼 수도 있습니다.

1. 함수형 메서드 체인
   • map, filter, flatMap 식으로 컬렉션을 변환하는 점은 List나 Seq와 유사
2. 지연 평가
   • RDD는 변환을 쌓아두고, 액션을 만나야 계산을 실행하는 특성이 있으므로,
   • 일반적인 즉시 평가형 List보다는 지연(Lazy) 컬렉션 혹은 자바의 Stream에 더 가깝다.
3. 불변/분산을 배제한다 해도, “RDD = 일종의 큰 컬렉션을 함수형 연산으로 다룬다”는 점에서,
   • 개발자 입장에서는 ‘(Lazy)Seq’나 ‘Stream’을 다루는 것과 유사한 경험이 될 것이다.

결국, “방대한 분산 처리”나 “불변”을 잠시 잊고, 코드를 작성·사용하는 관점만 놓고 보면,

• 스칼라의 List/Seq에 함수형 메서드를 적용하는 방식과 상당히 닮았고,
• 평가 시점이 지연된다는 점에서는 **Lazy 컬렉션(Stream류)**에 더 가깝다고 볼 수 있습니다.

Competitive Progrmming Helper의 약자로 백준같은 사이트에서 testcase같은걸 긁어다가 vscode에서 할 수 있게 해준다.

chrome에서도 확장프로그램을 설치해야하고(Competitive Companion)

vscode에서도 확장을 설치해야한다(Competitive Programming Helper)

원격ssh로 실행하는 경우는 포트전달이 필요할수도 있다.