22년 11월 2주차 회고록

public void solution(){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 동물원의 열 저장 // Dp[n][0] -> 두 개의 방 중에 사자를 아예 넣지 않은 경우 // Dp[n][1] -> 두 개의 방 중에 사자를 왼쪽 방에 넣은 경우 // Dp[n][2] -> 두 개의 방 중에 사자를 오른쪽 방에 넣은 경우 //행을 3까지 넣은 이유는 사자가 없을때도 체크하기 위해서. int[][] dp = new int[N+1][3]; dp[0][0] = 1; // 사자가 없을경우도 1이다. final int MOD = 9901; for (int i = 1; i <= N; i++) { // 기저조건 = dp[1][0,1,2]는 전부 1 // 기저조건부터 저장해가며 답을 찾아간다. // dp[i][0] 일때는 아무것도 없을때이다. = 본인이 위치한 자리를 카운트 하는것. dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % MOD; dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD; dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % MOD; System.out.printf("dp[0] = %d, dp[1] = %d, dp[2] = %d\n",dp[i][0], dp[i][1], dp[i][2]); } int answer = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD; System.out.println("answer = " + answer); } public static void main(String[] args) { 동물원1 z = new 동물원1(); z.solution(); }

# import sys # sys.setrecursionlimit(10**10) # 파이썬의 재귀함수 -> 1000이 한계 -> recursionlimit걸어준다 def calculate_cases(rows): if rows == 1: return 3 elif rows == 2: return 7 if result_list[rows-1] != 0: return result_list[rows-1] else: result_list[rows-1] = 2*calculate_cases(rows-1) + calculate_cases(rows-2) return result_list[rows-1] print(calculate_cases(row_num)%9901) # -> 시간초과... # 꼬리 재귀 방식? 어떻게...? calculate_case(rows, total) # calculate_case(rows-1, total+row를 넣었을 때 더해지는 수) # : n-1 n-2와 관련있는 경우 사용하기 어려울 듯

# 메모리 문제 row_num = int(input()) result_list = [0] * row_num result_list[0] = 3 result_list[1] = 7 for i in range(2, row_num): result_list[i] = 2*result_list[i-1] + result_list[i-2] # print(result_list) print(result_list[row_num-1]%9901)

row_num = int(input()) forward_num = 3 # n-2 backward_num = 7 # n-1 # N이 1부터 10,000 까지 -> 1일때랑 2일때 조건을 반드시 포함해주어야한다!!!! if row_num == 1: print(3) elif row_num == 2: print(7) else: for i in range(row_num-2): temp = backward_num backward_num = 2*backward_num + forward_num forward_num = temp backward_num %= 9901 # 9901 넘어가면 나머지가 다음으로 넘어가기 때문에 backward만 해도 되는데... print(backward_num%9901)

점화식을 찾는 방법이 어려웠습니다.... DP문제를 풀때에는 어떻게 하면 한번 계산한 값을 사용할 수 있을까? 라는 생각을 계속 해야할 것 같습니다.

에러가 계속 발생해서 처리하는 것이 어려웠습니다 ㅠㅠ 1. 파이썬의 재귀함수는 1000까지로 한계가 있다 -> limit 풀어줘야 함 2. 재귀함수에서 stackoverflow error가 발생하면 꼬리재귀를 이용하거나 값이 이미 존재하는 경우는 if 절을 사용해서 생성하지 않도록 함

- 문제 해결에 필요하다면 배열의 인덱스를 다른 조건에도 사용 할 수 있다. ex) 0번째 : 사자가 없을때 1번째 : 사자가 왼쪽에 있을때 2번쨰 : 사자가 오른쪽에 있을때

- 파이썬의 리스트는 배열이 아니다 - swap이 은근히 유용하게 쓰인다 - 재귀 함수는 제한 조건을 걸거나 꼬리 재귀를 이용해서 메모리를 많이 잡아먹지 않도록 해야한다

머리속으로만 생각해서그런지 단순히 계산실수로 인해서 돌아갔던 적도 많았습니다! 앞으로는 필기를 하며 풀던지, 그림을 그려가며 풀던지 좀 더 효율적으로 풀어야 겠습니다.

혼자서 생각하는 것보다 비슷한 예시(피보나치 수열)를 보고 적용해보는 것이 어쩌면 더 빠르고 확실할 수도 있겠다는 생각이 들었습니다