꾸준하게 거북이처럼

코딩테스트 문제에서 재귀 함수 문제가 나오고, 2차 3차 배열이 나오는 빡 구현문제라면, 배열을 매개변수로 전달할 경우 조심해야한다. 현재까지의 depth 반영한 배열을 가지고 이어서 연산을 해야하는데, copy라이브러리의 deepcopy를 이용하거나 따로 배열을 복사해두지 않으면 참조가 계속 이어져서 대참사를 만날 수 있다. 참고 할 수 있는 문제는 백준의 청소년 상어다. 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net

2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 위의 사진은 n == 27일 때 패턴과 주황색으로 표시한 부분은 n== 9일 때의 패턴이다. 그림을 보면 n==9 일 때는 n == 3 일 때의 패턴을 기준으로 만들어지고, n == 27일 때는 n == 9일 때의 패턴을 기준으로 만들어지는 것을 알 수 있다. 아이디어 n == 3일 때의 패턴을 배열로 나타내면 arr = ['***', '* *', '***'] 로 표현할 수 있다. n == 9일 때의 패턴을 찾아보자. 1. arr의 각..

하노이 탑은 정말 유명한 대표적인 재귀 알고리즘 문제이다. 그렇기 때문이기도 하고 전에 배웠지만 또 까먹어서 정확히 개념을 정리하고자 한다. 하노이 탑에서는 결국은 목적이 모든 원반을 하나씩 옮겨서 1에서 3으로 다 옮겨야한다. 그렇다면 이를 반복적인 부분을 고려해서 크게 3가지로 세분화 할 수 있는데, 1. 작은 원반 n-1개를 즉, 맨 아래 원반을 제외한 나머지 원반. 을 A 에서 B로 이동 2. 큰 원반인 제일 아래 원반 1개를 A에서 C로 이동 3. 작은 원반 n-1개를 다시 B에서 C로 이동 이렇게 크게 나눌 수 있다. 재귀니까 종료조건도 생각해야하는데 n-1부분 재귀를 하다보면 1개가 남을 것이다. 그 때가 종료 조건이 된다. 파이썬 코드로 옮겨 보자면 n = int(input()) a = [..