백준 11727번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline arr = [1, 2, 3] + [0]*1000 # 처리 for i in range(n:=int(read().strip())): arr[i+2] = (arr[i+1] + arr[i]) % 10007 print(arr[n-1]) CODE REVIEW 백준 11726번 - 2xn 타일링의 확장판. 점화식은 $a_{n+2} = a_{n+1} + 2 a_{n}$ n+1에 (1*2) 한 개 넣거나, n에 (2*1) 위아래로 두 개 또는 (2*2)짜리 한 개 넣는 경우의 합으로 계산할 수 있다.
백준 15482번 바로가기 나의 풀이 # 입력 - python의 경우 유니코드 처리 없이도 가능하다!! 갓갓 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) CODE REVIEW 백준 9251 - LCS 문제의 연장선. C++의 경우 한글을 유니코드 처리해서 3글자씩 끊어서 비교해야하는데, python은 그럴 필요가 없다. 역시 갓갓 언어!! python 사랑해요.
백준 17218번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[''] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + A[i - 1] else: if len(LCS[i - 1][j]) > len(LCS[i][j - 1]): LCS[i][j] = LCS[i - 1][j] else: LCS[i][j] = LCS[i][j - 1] print(LCS[n][m]) CODE REVIEW 문제를 풀다가 도저히 해결 방법을 모르겠어서 구글링을 통해 LCS 알고리즘에 대해 알게 되었다. 아래 블로그에 그림으로 잘 설명되어있었는데, n*m matrix에 경로에 따라 +1 해가면서 빈칸을 채우는 기발한 방법으로 문제를 풀어낼 수 있었다. 숫자를 채워넣는 LCS 알고리즘을 응용해서, matrix속에 조건을 만족하면 문자열 string을 추가하는 방식으로 문제를 해결했다. dp 문제는 정말 생각지도 못한 기발한 풀이법들이 존재해서 항상 배우게 하는 것 같다. REFERENCES 그림으로 이해하는 LCS 알고리즘
백준 1958번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline A, B = read().strip(), read().strip() n, m = len(A), len(B) LCS = [[0] * (m + 1) for _ in range(n + 1)] # 처리 - LCS 알고리즘 이용 for i in range(1, n + 1): for j in range(1, m + 1): if A[i - 1] == B[j - 1]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) print(LCS[n][m]) CODE REVIEW 백준 9251번 - LCS를 풀면서 3개 이상의 문자열의 LCS 구하는 문제도 만들어볼 수 있겠다 생각했는데, 역시나 이미 그런 문제가 존재했다. 3중 array를 사용하면 되었는데 2차원을 3차원으로 확대하는 과정이 생각보다 단순해서 금세 해결 가능했다. 문제에서 요구하진 않았지만, 역추적 하면 LCS에 해당하는 string 문자열을 구할 수도 있다.
백준 9095번 바로가기 나의 풀이 import sys read = sys.stdin.readline arr = [1,2,4] + [0]*12 for i in range(12): arr[i+3] = arr[i+2] + arr[i+1] + arr[i] for _ in range(int(read().strip())): print(arr[int(read().strip())-1]) CODE REVIEW 처음 아이디어는 중복조합에서 칸막이를 세우는 방법을 생각했는데, 1, 2, 3만 사용 가능해서 적용하기에 쉽지 않았다. 사실 n<=11이기 때문에 11까지 직접 노가다로 구하는 방법도 있겠지만, 코딩 문제 풀이이기 때문에 다른 방법을 생각해보았다. n이 1부터 6까지에 대한 $a_{n}$ 수열을 구해다가, $a_{n+3} = a_{n+2} + a_{n+1} + a_{n}$ 규칙성을 발견했다. 이 점화식을 분석해보면, (n+3)개의 경우의 수는 (n+2)개에 1을 오른쪽에 붙인 경우 + (n+1)개에 2을 오른쪽에 붙인 경우 + (n)개에 3을 오른쪽에 붙인 경우의 합이다. 반대쪽에 붙이는 경우, case가 겹치기 때문에 중복 counting 되어 안된다.