이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제설명 맨 아래 이외의 원반들은 목표장대가 아닌 보조장대로 옮기는 것을 재귀적으로 실행한다. 또한, n개의 원반을 이동시키기 위해서는 그 위의 n-1개의 원반을 다른 장대로 이동하고 맨 아래 원반을 도착지로 이동해야 한다. 그리고 다시 n-1개의 원반을 이동해야 하므로 다음과 같은 점화식이 성립한다. a_n = 2a_(n-1) + 1 이를 일반항으로 풀어내면 총 이동횟수는 ..

문제링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 재귀함수로 푸는 문제이다. 규칙파악이 포인트이고, 그 이후에는 재귀로 풀면 된다. 규칙파악 일정하게 가운데가 뚫린 정사각형 패턴이 반복되고 있다. 예를 들어, 3(=3^1)일 때는 가운데에 공백이 있고 1(=3^0)개 씩의 별이 찍히고 있다. 따라서 패턴은 다음과 같다. 3^i일 때 가운데를 공백으로 하고, 3^(i-1) 개 씩의 별 찍는다. 또한, 정사각형의 ..