본문 바로가기

분류 전체보기448

[HackerRank] The Maximum Subarray def maxSubarray(arr): # Write your code here len_arr = len(arr) dp_array = [0]*(len_arr) dp_sequence = [0]*(len_arr) dp_array[0], dp_sequence[0] = arr[0], arr[0] for i in range(1,len_arr): dp_array[i] = max(arr[i], arr[i]+dp_array[i-1]) for i in range(1,len_arr): dp_sequence[i] = max(dp_sequence[i-1], dp_sequence[i-1]+arr[i], arr[i]) return [max(dp_array),dp_sequence[len_arr-1]] 이번 문제는 주어진 배열(ar.. 2023. 5. 15.
[HackerRank] The Coin Change Problem def getWays(n, c): # Write your code here coin_count = len(c) dp = [[0]*(n+1) for _ in range(coin_count+1)] for i in range(1,coin_count+1): dp[i][0] = 1 for i in range(1,coin_count+1): for j in range(1,n+1): coin_value = c[i-1] if coin_value > j : dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-coin_value] return dp[coin_count][n] 이번 문제는 주어진 c 배열 안의 값들로 n을 만들 수 있는 경우의 수를 구하는 문제이다. 문제.. 2023. 5. 14.
[Python] 파이썬 자료구조 연산 시간복잡도 정리 리스트 자료형(list) 메서드의 시간복잡도 append, pop(), clear(), length 👉🏻 O(1) ==, !=, insert(), delete, pop(i), del, copy(), in, min(), max(), reverse() 👉🏻 O(n) sort() 👉🏻 O(nLog n) 집합 자료형(set) 메서드의 시간복잡도 add(), in, remove, pop(), clear() 👉🏻 O(1) copy() 👉🏻 O(n) 사전 자료형(dict) 메서드의 시간복잡도 store, len(), del, get, pop(k), clear(), keys(), values()👉🏻 O(1) 2023. 5. 13.
[HackerRank] Pairs def pairs(k, arr): # Write your code here # length = len(arr) count = 0 new_set = set(arr) for ele in arr: target_one = ele+k target_two = ele-k if target_one in new_set: count += 1 if target_two in new_set: count += 1 new_set.remove(ele) # for i in range(length): # for j in range(i+1,length): # if abs(arr[i]-arr[j]) == k: # count += 1 return count 이번 문제는 주어진 배열(arr)과 타겟 값(k)가 주어졌을 때, 두 수의 차가 k인.. 2023. 5. 13.
[HackerRank] Connected Cells in a Grid def bfs(x,y,area,row,column,visited): if area[x][y] != 1 or visited[x][y]: return 0 count = 1 visited[x][y] = True queue = [(x,y)] nx = [-1,1,0,0,-1,-1,1,1] ny = [0,0,-1,1,-1,1,-1,1] while queue: v = queue.pop(0) for i in range(8): temp_x = v[0] + nx[i] temp_y = v[1] + ny[i] if temp_x >= 0 and temp_x = 0 and temp_y < column: if area[temp_x][temp_y] == 1 and not visited[temp_x][.. 2023. 5. 12.
[HackerRank] KnightL on a Chessboard def findMinimum(a,b,n): area = [[0]*n for _ in range(n)] visited = [[False]*n for _ in range(n)] nx = [a, a, -a, -a, b, b, -b, -b] ny = [b, -b, b, -b, a, -a, a, -a] queue =[[0,0]] visited[0][0] = True while queue: v = queue.pop(0) for i in range(8): temp_x = v[0] + nx[i] temp_y = v[1] + ny[i] if temp_x >= 0 and temp_x =0 and temp_y < n: if not visited[temp_x][temp_y]: if area[tem.. 2023. 5. 12.

티스토리툴바