백준 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 알고리즘
백준 17219번 바로가기 나의 풀이 # 입력 import sys read = sys.stdin.readline n,m = map(int, read().split()) pro = dict() # 처리 for _ in range(n): ad, pw = read().split() pro[ad] = pw for _ in range(m): print(pro[read().strip()]) CODE REVIEW hash 형태로 정보를 저장하고, 다시 불러내는 문제. sys.stdin.readline 코드의 반복을 줄이기 위해 read = sys.stdin.readline으로 지정하고, read()로 부르면 편하게 사용 가능하다.
백준 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 문자열을 구할 수도 있다.