[10872] Q : 0보다 크거나 같은 정수 N이 주어진다. 이 때 N!을 출력하는 프로그램을 작성해라
A :for문이 아닌 재귀함수로 풀었다. 원래는 line 2에서 if (num==1)로 두었었는데 에러가 떴다. 왜 그런지 모르겠다. 그리고 사실 팩토리얼은 math lib에 math.factorial()로 구현되어 있다.
[10870] Q : 0번째 피보나치 수는 0이고, 1번째 피보나치수는 1이다. 그 다음 피보나치 수 부터는 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성해라
A :Line 9처럼 쓰면 코드를 단축할 수 있다.
[2447] Q : 재귀적인 패턴으로 별을 찍어보자. N이 3의 거듭제곱(3,9,27,..)이라 할 때, 크기 N의 패턴은 NxN 정사각형 모양이다. N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)x(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다.
A : 위 그림처럼 n에 대해 n//3으로 9개의 블록이 나온다. 9개의 블록 중 가운데 블록(line 12,13)은 빈칸으로 놔두면 되고, 나머지 8개의 블록들에 대해서는 동일한 패턴이 들어간다. 다시 n//3 크기의 블록에 대해 들여다보면, 동일한 원리가 반복된다. 이는 n=3일때 멈춘다(line 4~7) 처음에는 star 함수 안에서 바로 *이나 ' '를 출력하려 했었는데, n=3 크기의 블록을 출력하고 가로방향으로 동일한 패턴을 출력하는 것이 불가했다. 위 코드에서는 이를 해결하기 위해 함수 밖에서 처음부터 N*N 크기의 행렬을 만들어준다. 그리고 star()에서는 def star() 밖의 Map을 불러다 사용한다. 그러기 위해 line 2의 global 변수를 사용했다. 만약 def star() 밖에도 Map이라는 변수가 있고, 안에도 Map이라는 변수가 있으면 star 함수 안에서는 안에있는 Map이 사용된다. 그리고 함수 밖을 벗어나면 star 안의 Map은 사용할 수 없다. 만약 star 밖에 Map이 없고 안에만 있는데, 함수 밖에서 Map을 사용하려 하면 에러가 뜬다. 하지만 만약 line 2처럼 global Map을 사용하게 되면, line 18처럼 def star() 밖에서 Map이 정의되어 있지 않더라도, 함수 안에서 정의된 Map을 함수 밖에서도 사용할 수 있게 된다. https://study-all-night.tistory.com/5 https://cotak.tistory.com/38
[11729] Q : 세 개의 장대가 있고, 첫 장대에는 반경이 다른 서로 다른 n개의 원판이 쌓여 있다. 원판은 반경이 큰 순서대로 쌓여있다. 다음의 두 규칙에 따라 원판들을 첫째 장대에서 셋째 장대로 옮기려 한다. 1. 한 번에 한 개의 원판만 다른 탑으로 옮길 수 있다. 2. 쌓아놓은 원판은 아래 있는 것이 더 커야 한다. 이 작업을 수행하는데 필요한 이동순서를 출력해라. 단, 이동횟수는 최소가 되어야 한다. 입력으로 N이 주어지면 첫째 줄에 옮긴 횟수 K를 출력해라. 둘째 줄부터 수행과정을 출력한다. K개의 줄에 걸쳐 두 정수 A B를 빈 칸을 두고 출력하는데, 이는 A번째 탑에 가장 위에 있는 원판을 B번쨰 탑의 가장 위로 옮긴다는 뜻이다.
A : 이 문제는 다음 세 단계를 거쳐 풀이할 수 있다. n-1개의 원판을 모두 2로 옮기고(1단계), 마지막 원판을 1에서 3으로 옮기고(2단계), 2에 있는 n-1개의 원판을 3으로 옮기는 것(3단계)이다. 결국 1에 있는 가장 큰 원판을 3으로 옮겨야 하는데, 그러려면 1의 가장 큰 원판 위에는 아무것도 없어야 하고, 3에는 아무 원판도 없어야 하기 때문에 나머지 n-1개의 원판들은 모두 2에 있어야 한다. 때문에 이것이 최적 알고리즘이다. https://study-all-night.tistory.com/6
처음에는 line 4의 return을 쓰지 않을까 했지만, 그러면 num==1일때 line 5로 넘어가 버리기 때문에 안된다. 아무것도 리턴하지 않더라도 line 4처럼 써줘야 한다. line 5가 1단계, line 6가 2단계, line 7이 3단계이다. line 5,7에서 6-(start+end)라고 쓴 이유는, 막대 1,2,3의 합이 6이기 때문이다. 처음에 start=1, end=3이므로 6-(start+end) = 2가 된다. line 7에서는 2에서 3으로 n-1개의 원판을 옮기는 것이므로 저렇게 쓸 수 있다. 만약 hanoi(1,start,end)면 한 개의 원판만 start에서 end로 그냥 옮기면 되기 때문에 line 3처럼 print하면 된다.
line 10에서 총 이동횟수는 2^n-1임을 알 수 있다. 만약 n=5라면 h(4,1,2) + print(1,3) + h(4,2,3)이다. h(4,1,2) = h(3,1,3) + print(1,2) + h(3,3,2)이다. 4개의 원판을 1에서 2로 옮기려면 3개의 원판을 1에서 3으로 옮기고, 마지막 원판을 1에서 2로 옮기고, 3개의 원판을 다시 3에서 2로 옮기면 되기 때문이다.
h(5,1,3) ====> h(4,1,2)[15] ====> h(3,1,3)[7] ====> h(2,1,2) [3] ====> h(1,1,3) [1] ====> print(1,3) print(1,3)[1] print(1,2)[1] print(1,3)[1] print(1,2)[1] h(4,2,3)[15] h(3,3,2)[7] h(2,2,3)[3] h(1,3,2)[1] ====> print(3,2) <31> <15> <7> <3> 이처럼 n==5이면 2^5-1 = 31이 성립하는 것을 확인할 수 있다.
