99클럽 코테 스터디
어제오늘 시골에서 농사일을 돕느라 어제는 빼먹고 오늘도 늦은 시간에 TIL을 작성하게 되었다.
엊그제 greedy와 dp에 강하다고 썼는데, 오늘은 dp였다. 그 중에서도 dp에는 아주 자신이 있다.
하지만 문제가 쉬운 편이라 딱히 보여줄 건 별로 없었다.
비기너 문제 Pascal's Triangle : https://leetcode.com/problems/pascals-triangle/description/
미들러 문제 Count Sorted Vowel Strings : https://leetcode.com/problems/count-sorted-vowel-strings/description/
챌린저 문제 정수 삼각형 : https://school.programmers.co.kr/learn/courses/30/lessons/43105
출처 : 프로그래머스, leetcode
비기너 문제 : Pascal's Triangle
풀이 접근
파스칼의 삼각형에 한 줄을 추가할 때 그 바로 윗줄을 가지고 만드므로, dp로 접근할 수 있다.
그냥 쌩으로 처음부터 만들어도 되고, 재귀를 이용할 수도 있다. 그도 아니라면, 이항계수를 그냥 수학적으로 구할 수 있으므로(파스칼의 삼각형의 n+1번째 줄은 (x+1)^n의 이항계수들이다) 그냥 nCr을 구해다 넣어도 된다. 나는 dp로만 풀었다.
코드(Python3, Accepted, 30ms(상위 8.24%), 16.44MB(상위 11.91%))
재귀 없는 그냥 쌩dp이다. 재귀를 해봤자 함수 호출만 n번 할 뿐 어차피 파스칼의 삼각형을 처음부터 만들어야 되는건 똑같기 때문에, 이 쪽이 효율 면에선 더 나을 수도?
맨 왼쪽과 맨 오른쪽은 1로 고정이고, 윗줄에서 두 개가 아닌 한 개만 더하는 거라서 그냥 for문에서 분리해서 따로 처리했다.
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
pt = [[1]]
for i in range(1, numRows):
pt.append([1])
for j in range(1, i):
pt[i].append(pt[i - 1][j - 1] + pt[i - 1][j])
pt[i].append(1)
return pt미들러 문제 : Count Sorted Vowel Strings
풀이 접근
비기너 문제도 그렇지만, 이 문제도 dp로 풀 수도 있고, 수학적으로 풀 수도 있다.
일단 dp로 푸는 아이디어는 다음과 같다.
a,e,i,o,u를 각각 n글자짜리 lexicographically sorted 단어 중 a로 끝나는 것, e로 끝나는 것, ... u로 끝나는 것이라 하자.
그러면 n+1글자짜리 lexicographically sorted 단어는
n글자짜리 a로 끝나는 것에 a,e,i,o,u를 붙여서,
e로 끝나는 것에 e,i,o,u를 붙여서,
i로 끝나는 것에 i,o,u를 붙여서,
o로 끝나는 것에 o,u를 붙여서,
u로 끝나는 것에 u를 붙여서 만들 수 있다.
이걸 dp로 만들면 된다.
수학적으로는, n글자짜리 lexicographically sorted 단어의 수는 5개의 알파벳 중 n개를 중복을 허용해서 뽑는(조합) 경우의 수이다. 조합만 정해지면 순서가 고정되므로, 조합만 뽑으면 되기 때문이다. 그리고 중복조합의 공식은 5Hn = (n+4)Cn = (n+4)C4 = (n+1)(n+2)(n+3)(n+4)/24 이다.
코드1(Python3, Accepted, 28ms(상위 5.96%), 16.40MB(상위 4.4%))
dp로는 거의 극한의 효율인 코드이다.
e,i,o,u는 해당 알파벳으로 끝나는 1글자짜리 단어의 개수이다. (for문 한번 돌릴 때마다 글자 수는 1씩 늘어난다)
우선 a로 끝나는 단어는 항상 1개(a로만 이루어진 단어)이므로 변수 할당도 필요없다.
e로 끝나는 k+1글자 단어는, e로 끝나는 k글자 단어들 맨 뒤에 e를 붙인 것 (변수 e)개 + a로 끝나는 k글자 단어 1개에 e붙인것 1개이다.
i로 끝나는 k+1글자 단어는, 방금 만든 e로 끝나는 단어에 e대신 i를 붙인 것 (변수 e)개 + i로 끝나는 k글자 단어 (변수 i)개이다.
o도, u도 마찬가지 논리로 더해주기 연산 한 번씩으로 dp 한 사이클을 끝낸다.
class Solution:
def countVowelStrings(self, n: int) -> int:
e,i,o,u = 1,1,1,1
for _ in range(n - 1):
e += 1
i += e
o += i
u += o
return 1+e+i+o+u코드2(Python3, Accepted, 28ms(상위 5.96%), 16.45MB(상위 26.67%))
놀랍게도 고효율 dp 코드와 날로먹는 중복조합 공식 코드는 실행시간이 같게 나왔다. 몇 번 다시 제출해도 28ms 이상의 기록은 안 나왔다. 6%의 사람들은 대체 어떻게 푼 건지 궁금해진다. 그냥 leetcode의 채점 서버가 클린할 때 나온 기록인 것일까?
answer에 할당 안 하고 저 식을 그대로 return해도 29ms가 한계이더라.
class Solution:
def countVowelStrings(self, n: int) -> int:
answer = (n+1)*(n+2)*(n+3)*(n+4) // 24
return answer챌린저 문제 : 정수 삼각형
풀이 접근
dp 문제는 보통 주어진 데이터와 별개의 변수(나는 보통 리스트로 만든다)를 만들어서 수행하게 되는데, 이 문제는 특이하게 주어진 triangle을 그대로 가지고 변형시켜 답이 나오게 짤 수 있다.
triangle[i][j], 즉 i행의 j번째 자리에, 원래는 해당 위치의 값이 들어있다.
이를 위에서부터 아래로 순회하면서 그 자리를 '맨 위에서 해당 위치까지 내려오는 경로 중 합이 가장 큰 경우의 합'으로 바꾼다.
그리고 이는 그 바로 위에 있는 두 숫자 중 더 큰 값에 원래 값을 더해서 구할 수 있으므로, dp가 적용될 수 있다.
코드(Python3, 통과, 최대 38.80ms, 14.7MB)
파스칼의 삼각형 때도 그렇지만, 맨 왼쪽(triangle[i][0])과 맨 오른쪽(triangle[i][i])은 외길이므로 선택지가 없다.
그 사이(triangle[i][j])는, 바로 위의 두 숫자((triangle[i-1][j-1]), (triangle[i-1][j])) 중 더 큰 값에 본인의 값을 더한 것으로 결정된다.
그렇게 만든 triangle의 맨 마지막 줄의 최댓값이 바로 정답!
def solution(triangle):
n = len(triangle)
for i in range(1, n):
triangle[i][0] += triangle[i - 1][0]
for j in range(1, i):
triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])
triangle[i][i] += triangle[i - 1][i - 1]
answer = max(triangle[n - 1])
return answer