분류 전체보기 썸네일형 리스트형 69. Sqrt(x) 음수가 아닌 정수가 인풋으로 들어올 때, 루트를 한 인풋에서 가까운 정수로 반내림한 결과를 리턴한다. 루트를 만들기 위한 빌트인 함수나 오퍼레이터를 사용하지 않아야 한다. solution 1. n이 1부터 1씩 증가시키는 while문을 만들고 인풋이 n 제곱보다 크거나 같고 (n+1) 제곱보다 작으면 n이 인풋을 루트하고 반내림한 결과로 여길 수 있다. 따라서 n을 결과값으로 도출할 수 있다. class Solution: def mySqrt(self, x: int) -> int: n = 0 while True: if n*n 더보기 66. Plus One int로 구성된 리스트가 주어진다. 이를 index 순서대로 나열한 숫자를 제시한다. 그 후 나열된 수에서 더하기 1을 한다. 이를 다시 int로 구성된 리스트로 변환하여 리턴한다. solution 1. 문제 그대로 리스트를 나열된 수로 변경한다. 이때 리스트에서 스트링으로 변환한 후, 더하기 1을 하기 위해 정수형으로 변환한다. 그후 더하기 1을 한다. 정수를 리스트로 변환해야하기 때문에 정수를 스트링으로 감싼 상태에서 map으로 int 형변환을 하고 그 위에 list로 다시 변환해준다. class Solution: def plusOne(self, digits: List[int]) -> List[int]: num = int(''.join(str(i) for i in digits)) + 1 res = l.. 더보기 198. House Robber 순서대로 나열된 집을 터는 문제다. 조건은 연속된 집을 털면 안 된다. solution 1. 집을 연속되지 않게 털려면, 현재에서 1곳 또는 2곳의 집을 띄워놓고 다른 집을 털러 갈 수 있다. 타뷸레이션을 활용한다. class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) 더보기 70. Climbing Stairs n개의 계단을 오른다. 한번에 1또는 2의 숫자만큼 계단을 오를 수 있다. 몇가지 경우의 수가 나오는가? solution 1. 1은 1가지 경우의 수, 2는 2가지 경우의 수가 나온다는 것을 안다. 1: (1), 2 : (1,1), (2) 이를 이용하여 재귀 함수를 만든다. class Solution: cnt = collections.defaultdict(int) def climbStairs(self, n: int) -> int: if n == 1: return 1 if n == 2: return 2 return self.climbStairs(n-1) + self.climbStairs(n-2) 타임아웃이 걸린다. solution 2. 메모제이션을 활용하여 값을 저장해놓는다. class Solution: .. 더보기 53. Maximum Subarray 연속된 서브 어레이 중에서 합이 가장 큰 서브 어레이를 구하고 그 합을 리턴한다. solution 1. 왼쪽, 오른쪽 포인터를 이용해서 풀이. 왼쪽, 오른쪽 포인터를 움직이기 위해서는 다음 숫자가 음수여야하고 그 다음, 그 다음,... 등등 과 합했을 때 더 클 수 있다는 것을 증명해야 한다. 그리고 이는 정렬된 상태에서 하는 것이 현명하다. 하지만 그렇게 되어있지 않기 때문에 이는 쉽지 않다. pass solution 2. 메모제이션 기법. 차례로 누적합을 계산해나가되, 음수가 되는 누적합은 버리고 다시 차례로 누적합을 진행한다. class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): if n.. 더보기 509. Fibonacci Number 피보나치 수열이다. 2이상의 정수일 때, 인덱스 하나 전의 수와 두개 전의 수가 합쳐져서 해당 수가 만들어진다. 초기값으로 0일때 0이고 1일때 1이다. solution 1. 재귀로 푸는 방법이다. 0과 1일때는 값을 그대로 뱉고, 2보다 큰 값은 재귀로 값을 얻어낸다. class Solution: def fib(self, n: int) -> int: if n int: i.. 더보기 455. Assign Cookies child list가 있고 cookie list가 있다. child list의 각 값은 쿠키를 몇 개 이상 먹어야 만족하는지 적혀있다. 다시 말해서 쿠키를 먹어야하는 최소의 갯수다. 그리고 cookie list는 쿠키 개수가 각각 들어있다. child list index i와 cookie list index j가 있을 때, child[i] >= cookie[j]가 되는 child의 수를 구하는 문제다. 문제에서 아이는 g[i] 리스트에 들어있고 쿠키는 s[j] 리스트에 들어있다. 먼저 각 리스트를 오름차순으로 정렬하고, 쿠키 하나를 정해놓고 그것이 아이가 원하는 값보다 크거나 같으면 아이 index을 하나씩 늘려간다. 그리고 원하는 값이 없으면 쿠키 index를 하나씩 늘려간다. 결과적으로 아이 inde.. 더보기 406. Queue Reconstruction by Height 입력은 people = [[h1, k1], [h2, k2], [h3, k3]...] h는 해당 사람의 키, k는 자기 앞에 사람들 중 자신의 키 이상인 사람들의 수를 나타낸다. 입력은 이 조건대로가 아닌 랜덤으로 들어가 있다. 따라서 출력은 이 배열이 올바른 순서대로 재정렬된 결과를 나타낸다. 이 배열이 올바른 순서대로 재정렬하는 알고리즘을 만들어라 풀이 1. 가장 큰 사람일 수록 앞에 사람이 없기 때문에 가장 큰 사람일수록 앞에 배치를 한다. 2. 그리고 같은 사람일 경우 k가 작은 순으로 앞에 배치한다. 그러면 앞에 키 크고 동일할 경우 k가 적은 순서대로 나온다. 이런 우선순위를 사용하기 위해 heapq 우선순위 큐를 이용하여 큐에 삽입한다. 그 이후에 pop을 할 때마다 가장 크고 k가 작은 순으.. 더보기 이전 1 ··· 11 12 13 14 15 16 다음