인프런 커뮤니티 질문&답변
작성한 질문수
제가 이해한 칸토어집합 문제를 풀어서 써봤습니다.
해결된 질문
작성
·
83
·
수정됨
1
나중에 강의를 복습 할 때 제가 어떤식으로 문제에 접근하고 이해하고 강의를 들었는지 회고 하기 위해서 기록 해둡니다. 또한 제가 이해한 부분이 다른 분들에게 도움이 되면 더 좋겠습니다.
목표
문자열 길이가 주어지면 길이가 1이 될때까지
- -형태로 바꾸는 문제
제약조건
1 <= N <= 12
어떻게 해결?
입출력 결과를 보면 아래와 같이 추론이 가능하다.
ans[0] = 3⁰ = 1 => -
ans[1] = 3¹ = 3 => - -
ans[2] = 3² = 9
=> - - - -
=> ans[2-1] + 3²⁻¹ + ans[2-1]
결론적으로
=> ans[i-1] + 3ⁱ ⁻ ¹ + ans[i-1]
이러한 규칙을 찾을 수 있다.
시간 복잡도
칸토어 집합은 0부터 N까지 각 단계별로 3⁰ + 3¹ + 3² + ... 3¹² 만큼의 문자열을 처리해야 하므로 모든 합이 전체 연상량이다.
0 <= N <= 12
ans[0] ~ ans[12]
ans[i]의 길이 : 3ⁱ
ans[0] : 1
ans[1] : 3
ans[2] : 9
- 위에 0,1,2일때 공백 - 합쳐서의 길이
등비수열
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
rhkdtjd_12님께서 공유해주신 칸토어 집합 문제 풀이를 통해 문제를 접근하는 방식을 잘 배울 수 있었습니다. 문제의 규칙을 잘 찾아내셨습니다.
시간 복잡도 분석 역시 칸토어 집합의 성격을 잘 반영하여 분석하신 것 같습니다. 주어진 입출력 패턴과 수열의 규칙성을 잘 파악하셨고, 이를 통해 복잡도 O(3^N)으로 잘 정리하셨습니다.
이러한 기록은 나중에 강의 복습 시 도움이 될 뿐만 아니라, 다른 사람들에게도 좋은 참고 자료가 될 것입니다. 좋은 학습 습관을 공유해주셔서 감사합니다!
강의 내용에 대한 더 깊은 이해를 위해 ‘강의 노트 기능’을 이용해보시면 복습에 더욱 도움이 될 것이라고 생각합니다. 언제, 어디까지 내용을 들었는지 기록할 수 있는 기능입니다. 강의 노트 기능 관련 FAQ를 확인하시면 자세한 내용을 참고할 수 있습니다.
계속해서 학습에 좋은 성과가 있으시길 바랍니다!