[BOJ/Python] 2447 별 찍기 - 10, 11729 하노이 탑 이동 순서

알고리즘 문제 풀다보면 시간복잡도 때문에 약간 강박적으로 for문을 안쓰려고 해서 재귀함수가 이에 대한 해답이 될 줄 알았더니 오히려 성능이 더 떨어진다니.. 섭섭하다. 아무튼 for문 잘 써보자

<2447 별 찍기 - 10>

# 별찍는 함수 만들기
def square(number):

    # 주어지는 number가 3일 때가 가장 기본 형태 
    if number == 3:
        star = ['***','* *','***']
        return star

    # number가 3이 아닌 3의 거듭제곱일 때 재귀함수 이용
    else:
        # 리스트 star의 길이는 number
        star = [''] * number
        
        # square(number//3)의 리스트로부터 number에 대한 star을 만들어줌
        for i, s in enumerate(square(number//3)):

            # 새로운 star는 square(number//3)의 3배 길이이므로 i, i+(number//3), i+(number//3)*2마다 규칙성 생김
            # star[i]와 star[i+(number//3)*2]는 s의 3배를 해준 값
            # star[i+(number//3)]은 s + (number//3)만큼의 공백 + s 의 값
            star[i] = s*3
            star[i+(number//3)] = s + ' ' * (number//3) + s
            star[i+(number//3)*2] = s*3

        return star


number = int(input())

# square(number)는 number길이 만큼의 리스트 형태이므로 요소별로 출력
for s in square(number):
    print(s)

이 문제는 fractal처럼 논리는 너무 간단했는데 구현해서 출력하기가 너무 어려웠다.. 결국 검색을 통해 정답을 공부하고 풀었다.

각 줄을 하나의 list item으로 재귀함수마다 저장해주면 됐다. 혼자서 몇시간을 끙끙 거릴때는 * 하나하나마다 2차원 배열의 item으로 저장하려고 애쓰고 구현도 못하고.. 쉽지가 않다. 재귀가 많이 약한가보다 난

 

이런 아이디어를 어떻게 떠올려야 하는가.. 공부가 더 필요한건지 다른 풀이를 보고나면 이해는 잘 되는데, 한단계씩 손코딩하는 것도 나름 재미는 있다. 계속하다보면 늘겠지 싶다.

 

다음으로 하노이 탑 문제

<11729 하노이 탑 이동 순서>

하노이탑 역시 논리 자체는 너무 단순한데 매번 어디에서 어디로 이동하는지 출력하는 것을 구현하는게 너무 어려웠다.

아래와 같은 깔끔한 생각, 유연한 생각을 하지 못해서 그저 무식하게 다 작성하고 규칙을 찾아보려고 몇시간을 용썼다 아주 홀수 입력시는 13 32 21 짝수는 12 23 31 와 같은 규칙... 이마저도 문제 조건과 비교하니까 틀렸다.

아직도 컴퓨터를 잘 이용하지 못한다니!!! 논리 잘 짜서 코딩좀 잘 해보자...

def hanoi(n, i, via, j):
  if n==1:#이동할 원반이 1개일 때
    print(f"{i} {j}")
    return
  hanoi(n-1, i, j, via)#n-1개 원반을 경유지로 이동
  print(f"{i} {j}")#남은 1개의 원반 n을 이동
  hanoi(n-1, via, i, j)#n-1개 원반 경유지에서 j로 이동
  return    

n=int(input())
print(2**n-1)
hanoi(n, 1, 2, 3)

하노이탑 문제야 말로 재귀함수를 이용해 완전 수학처럼 푼것 같아서 재밌다.

기본 아이디어들은 역시 검색을 통해 가져왔다. 아직도 함수 여러 변수들을 이용해 문제해결하는 능력은 부족하다.

어느면에서는 생각이 참 갇혀있는 것 같기도 하고

하노이는 결국 3개 칸에서 왔다갔다 하는 거니까 from, via, to를 지정해서 이용할 수 있다는 이 단순한 생각. 왜 못했을까

막상 해결하고보니 좀 예쁜 코드이기까지 하다(?)ㅎㅎ 복잡할 수도 있었는데