[백준/Python] 4779 칸토어 집합
정답 코드 및 설명
def cantor(start_index, segment_length):
if segment_length == 1:
return
middle_start = start_index + segment_length // 3
middle_end = start_index + (segment_length // 3) * 2
for i in range(middle_start, middle_end):
cantor_set[i] = ' '
cantor(start_index, segment_length // 3)
cantor(start_index + (segment_length // 3) * 2, segment_length // 3)
while True:
try:
N = int(input())
cantor_set = ['-'] * (3**N)
cantor(0, 3**N)
print(''.join(cantor_set))
except:
break
칸토어 집합
칸토어 집합은 0과 1 사이의 구간에서 시작해, 각 단계에서 현재 구간을 3등분하여 가운데 구간을 제거하는 과정을 무한히 반복하여 생성된다. 이 과정은 프랙탈의 한 예로, 각 단계에서 집합의 복잡성이 증가하며, 끝없는 반복을 통해 독특한 구조를 형성한다.
위 코드는 칸토어 집합을 유한한 단계까지 시뮬레이션하여 근사적으로 표현한다. cantor 함수는 주어진 세그먼트(여기서는 문자열의 일부)에 대해 재귀적으로 중간 1/3 구간을 공백으로 만드는 작업을 수행한다.
재귀적 과정
기저 조건: segment_length == 1일 때, 더 이상 나눌 수 없으므로 함수는 더 이상의 작업 없이 종료한다. 이는 재귀의 종료 조건으로, 더 이상 가운데 구간을 제거할 수 없음을 의미한다.
재귀 단계: 현재 구간을 3등분하여 가운데 구간을 공백으로 만든 후, 나머지 두 구간(앞부분과 뒷부분)에 대해 같은 과정을 재귀적으로 반복한다. 이때 각 재귀 호출은 새로운 시작 인덱스와 세그먼트 길이를 계산하여 전달한다.
코드 설명
함수 정의: cantor(start_index, segment_length)는 칸토어 집합의 일부를 생성하는 함수다. start_index는 처리할 세그먼트의 시작 위치를, segment_length는 세그먼트의 길이를 나타낸다.
중간 구간 제거
계산된 middle_start와 middle_end를 이용하여 가운데 1/3 구간을 공백으로 변경한다. 이는 칸토어 집합을 생성하는 핵심 단계다.
재귀 호출
가운데 구간을 제거한 후, 앞부분과 뒷부분에 대해 같은 함수를 재귀적으로 호출한다. 이 과정은 각 세그먼트의 길이가 1이 될 때까지 반복된다.
종료 조건
세그먼트의 길이가 1이 되면, 더 이상 세분화할 수 없으므로 함수는 작업 없이 종료한다. 이는 재귀 호출의 깊이를 제한하며, 무한 루프에 빠지지 않게 한다.
실행 부분
사용자로부터 N 값을 입력받아, 해당하는 칸토어 집합의 근사치를 생성하고 출력한다. cantor_set 배열은 초기에 모두 '-'로 채워지며, cantor 함수를 통해 중간 구간이 공백으로 변경된다.
