Julie의 개발 기록

문제 링크 : https://www.acmicpc.net/problem/14712 N x M 격자 안에 네모를 배열하되, 2 X 2 정사각형 모양이 없도록 하는 경우의 수를 구하는 문제이다.예를 들면 격자가 2 X 3 이라고 할 때 세어야하는 경우와 아닌 경우는 아래와 같다.  행의 개수 N, 열의 개수는 M으로 주어지고, 시간제한은 1초이다. (1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25) 아무리 생각해도 모든 경우의 수를 만들어낸 후, 네모가 있는지 검사하는 것이 가장 확실하다는 생각이 들었는데, 이중 list를 사용하면 시간도 메모리도 초과할 것이 뻔했다. 게다가 이러면 네모 유무를 확인하는것도 어려웠다. 각 경우의 수를 검사하는 방식을 엄청나게 최적화 해야 최대 2 ^ 25 가지 경우의..

문제 링크 : https://www.acmicpc.net/problem/12015 LIS는 최장 증가 부분 수열을 의미한다. 주어진 수열에서 숫자를 몇개 빼서 가장 긴 증가 수열을 만드는 것이 규칙이다. [0, 1, 2, 0, 5, 4]에 대해서 LIS를 찾는다고 하면, [0, 1, 2, 5] 또는 [0, 1, 2, 4]가 답이다. 부분 수열이 인덱스 i에서 끝날 때의 LIS 수열의 길이를 lis[i]라고 할 때, lis[i]에 대한 점화식을 적용하면 O(N^2) 해법을 쉽게 떠올릴 수 있다.def dp(arr): N = len(arr) lis = [1] * N for i in range(N): # 0부터 i까지 구간에서 부분수열의 최대 길이를 구한다. for k in ran..