칸토어 집합이 깨달음을 주었다

런닝 뛰고 샤워하고 맥주 한 잔 걸치면서 쓰는 ps 일기...

나는 내가 재귀를 정말 못한다고 생각했었음...
그래서 재귀를 잘해지기 위해서 재귀 문제만 골라서 쭉 풀고 하던 시절도 있었음... (이건 글도 썼는데 이 블로그 말고 딴 데다 써서.. 나중에 완성되면 올림)

예를 들어서 정말 유명한 재귀 문제
별 찍기 10
PS를 하는 사람이라면 모두 한 번쯤은 풀어봤을 그 유명한 문제임

전에 이 문제를 풀어보려고 했었는데... 마찬가지로 재귀를 더럽게 못했던 나는 좀 끄적끄적만 거리다가 완전히 엉망인 결과가 나와서 던졌던 기억이 있다
이유는 모르겠지만 코드가 안 남아있네 지웠나... 아무튼

---

그리고 까마득하게 이 문제를 잊고 지내다가 오늘 백준 단계별에서 재귀를 풀다가 만난 이 문제
칸토어 집합

한 번 손대봐야겠다고 생각은 하고 있었어서 마침 오늘 만난 김에 해결해버려야겠다고 생각했다

// 칸토어 집합 - 실버 3

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

void makeCantor(string& str, int l, int r) {
    if (l >= r) return;
    int len = (r - l) / 3 + 1;
    fill(str.begin() + l + len, str.begin() + r - len + 1, ' ');
    makeCantor(str, l, l+len-1);
    makeCantor(str, r-len+1, r);
}

int main() {
    int n;
    while (cin >> n) {
        string answer (pow(3, n), '-');
        makeCantor(answer, 0, pow(3, n) - 1);
        cout << answer << '\n';
    }
}

결과적으로는 매우 유익했던 것 같음
string 생성자 중에 저렇게 변수명 (길이, 문자) 해서 자동으로 채워주는 게 있다는 것도 배웠고
fill 함수도 처음 써봤고... pow 함수도 써보고...
그리고 이 문제를 어떻게 접근해야 될지를 되게 고민했었는데 이번에는 운좋게도 보자마자 떠올랐음.
길이를 삼등분을 해주고 그 만큼을 공백문자로 채워준 다음에, 그러면 양 옆 두 부분이 남으니까 그 부분을 또 삼등분을 하고... 남은 두 부분을 또 삼등분... 또... 이렇게 재귀적으로 나눠주면 됨!
전보다 재귀가 많이 익숙해진 기분이 듬... 재귀 특훈의 성과가 이렇게 보이는 것 같다

---

그래서 이제는 별 찍기 문제를 풀었다는 말을... 해야겠지요...? 맥락상ㅋㅋㅋㅋ

그냥 이 문제는... 칸토어 집합을 2차원으로 확장한 버전이라고 할 수 있음. 딱 그게 전부임. ㅋㅋ
진짜 그냥 칸토어에서는 가로로 삼등분해서 공백 넣어준 거를 여기서는 가로 세로를 둘 다 삼등분해서 공백을 넣어주면... 그걸로 끝

근데 이제 여기서 sub-problem이 칸토어는 2개가 생기는데 여기는 8개가 생김... 이유는 생각해보면 알거라고 생각함^^
그래서 그게 좀 귀찮았음... 이건 뭔가 더 좋은 방법이 있지 않을까 싶은데 나중에 한 번 찾아봄ㅋㅋㅋ

//별 찍기 - 10 - 골드 5

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pi;

void makePattern(vector<vector<char>>& arr, pi l, pi r) {
    int len = (r.first - l.first + 1) / 3;
    if (!len) return;

    for (int i = l.first + len; i < r.first -len + 1; i++) {
        for (int j = l.second + len; j < r.second -len + 1; j++) {
            arr[i][j] = ' ';
        }
    }

    makePattern(arr, l, {l.first + len - 1, l.second + len - 1});
    makePattern(arr, {l.first + len, l.second}, {r.first - len, l.second + len - 1});
    makePattern(arr, {r.first - len +1, l.second}, {r.first, l.second + len - 1});

    makePattern(arr, {l.first, l.second + len}, {l.first + len - 1, r.second - len});
    makePattern(arr, {r.first - len +1, l.second + len}, {r.first, r.second - len});

    makePattern(arr, {l.first, r.second - len + 1}, {l.first + len - 1, r.second});
    makePattern(arr, {l.first + len, r.second-len+1}, {r.first - len, r.second});
    makePattern(arr, {r.first - len + 1, r.second - len + 1}, r);

}

int main() {
    int n;
    vector<vector<char>> arr;
    cin >> n;
    arr.assign(n, vector<char> (n, '*'));

    makePattern(arr, {0, 0}, {n-1, n-1});

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j];
        }
        cout << '\n';
    }
}

아무튼 전보다 발전한 거 같아서 매우 뿌듯했다!