198. House Robber
https://leetcode.com/problems/house-robber/
My answer 1: Accepted (Runtime: 28 ms - 85.65% / Memory Usage: 14.4 MB - 19.99%)
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) < 3:
return max(nums)
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[-1]길이 2 까지는 오직 하나만 훔칠 수 있으니까 최댓값 return
나머지는 nums 길이만큼의 dp 를 만들어서
0 ~ i 까지 훔친 거 중에 최댓값을 넣어줌
ex) [2, 7, 9, 3, 1]
[2] dp[0] = 2
[2, 7] dp[1] = 2 or 7 => 7
[2, 7, 9] dp[2] = dp[0]+nums[2] or dp[1] = 11 (2+9) or 7 => 11
[2, 7, 9, 3] dp[3] = dp[1]+nums[3] or dp[2] = 10 (7+3) or 11 => 11
[2, 7, 9, 3, 1] dp[4] = dp[2]+nums[4] or dp[3] = 12 (11+1) or 11 => 12dp[-1] 이 전체 최댓값이 된다.
200. Number of Islands
https://leetcode.com/problems/number-of-islands/
My answer 1: Accepted (Runtime: 128 ms - 93.40% / Memory Usage: 15.6 MB - 39.26%)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def func(i, j):
grid[i][j] = "2"
if i+1 < len(grid) and grid[i+1][j] == "1":
func(i+1, j)
if i-1 >= 0 and grid[i-1][j] == "1":
func(i-1, j)
if j+1 < len(grid[0]) and grid[i][j+1] == "1":
func(i, j+1)
if j-1 >= 0 and grid[i][j-1] == "1":
func(i, j-1)
ans = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == "1":
ans += 1
func(i, j)
return ansgrid 값 중에 1 을 만나면
그 1 과 이어진 모든 1 들을 2 로 변경 & ans + 1
207. Course Schedule
https://leetcode.com/problems/course-schedule/
My answer 1: Accepted (Runtime: 136 ms - 16.48% / Memory Usage: 33.3 MB - 5.29%)
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
dp = [0] * numCourses
dic = {}
for i in range(numCourses):
dic[i] = []
for i in range(len(prerequisites)):
a = prerequisites[i][0]
b = prerequisites[i][1]
if a in dic[b] or a == b:
return False
dic[a].append(b)
def func(idx, lists):
a = 1
for i in range(len(dic[idx])):
if dp[dic[idx][i]] == 0 and dic[idx][i] not in lists:
a *= func(dic[idx][i], lists+[idx])
elif dp[dic[idx][i]] == 0 and dic[idx][i] in lists:
return False
dp[idx] = 1
return a
i = 0
while i < numCourses:
if dp[i] == 0:
if func(i, []) == 0:
return False
i += 1
return True이 문제 보자마자 무한 굴레에 빠졌던 트라우마가...^^
-
0 ~ numCourses을 key 로 갖는dic만들기 -
prerequisites를 보면서 각 과목마다 선수과목을dic에 append
if a in dic[b] or a == b:=> cycle 이 생기거나 자기 자신이 선수과목인 경우 처리 -
dp값이 0 이면 재귀 돌려서 유효한지 확인 /lists에는 꼬리물기 진행상황을 저장
dp[i]가 1 이라면i코스는 이미 유효함이 증명된거니까 continue
dp[i]가 0 인 애들은 증명이 필요함
=> for 문 돌려서 선수과목 중에 증명 안된애들만 다음 재귀로 넘김
이때, 증명도 안됐는데 이미 만난 적이 있으면 cycle 이니까 return False
cycle 없이 꼬리물기가 잘 된 애들은dp[idx] = 1로 변경
(*연산자로 하나라도 0 이 있으면 False 가 되도록 함)
dp에 0 이 있는지 확인해서 T/F return
테스트케이스 엄청 돌려서 끼워 맞춰갔다...ㅎ
Solution 1: Accepted (Runtime: 88 ms - 96.29% / Memory Usage: 17.5 MB - 19.08%)
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = {i:[] for i in range(numCourses)}
for course,pre_course in prerequisites:
graph[course].append(pre_course)
# whether exist circle
def DFS(course,seen):
# if node have been traveled
if seen[course]==0:
return False
elif seen[course]==1:
return True
seen[course] = 1
for pre_course in graph[course]:
if DFS(pre_course,seen):
seen[course] = 0
return True
seen[course] = 0
return False
seen = {i:-1 for i in range(numCourses)}
for course in range(numCourses):
if DFS(course,seen):
return False
return True비슷한 거 같은데 훨씬 깔끔하고 빠름
dp 대신 seen 이라는 dictionary 를 만들어서 사용
seen 은 -1 로 초기화
DFS 가 True 면 cycle 이 있다는 것
DFS 돌면서 seen 을 1 로 바꿔서 봤다는 체크를 해줌
꼬리물기를 무사히 통과하면 seen = 0 이 됨
seen = 1: 완전 증명은 안된 값이므로 다시 만나면 True => cycle
seen = 0: 완전 증명이 된 값이므로 다시 만나면 False
이걸로 알아두자!!!
