바위타는 두루미

문제 다량의 널빤지를 이어 붙여서 다이빙 보드를 만들려고 한다. 널빤지는 길이가 긴 것과 짧은 것 두가지 종류가 있는데 정확히 K개의 널빤지를 사용하여 다이빙 보드를 만들어야 한다. 가능한 다이빙 보드의 길이를 모두 구하는 메서드를 작성하라 해결법 1. 재귀적 해법 재귀적으로 K번의 널빤지를 선택하면 다이빙 보드를 완성할 수 있고 완성된 보드를 리스트에 추가하면 된다. + 메모이제이션 def getAllLengths(k, long, short): memo = set() lengths = set() def allLengths(k, lengths , total, long, short, memo): if k == 0: lengths.add(total) key = (total, k) if key in memo ..

문제 사람의 태어난 연도와 사망한 연도가 리스트로 주어졌을때, 가장 많은 사람이 동시에 살았던 연도를 찾는 메서드를 작성하라. 모든사람이 1900년도에서 2000년도 사이에서 태어났다고 가정해도 좋다. 또한 해당 연도의 일부만 살았더라도 해당 년도에 살아있었다고 봐야한다. 예르르들어 어떤 사람이 1908년에 태어나서 1909년에 사망했다면 이 사람은 1908년과 1909년 모두에 삶을 살았던 사람이된다. 해결법 1. 무식한 방법 각 년도를 순회하면서 각 년도에 살아있는 사람들을 카운트한다. R이 가능한 연도의 범위이고 P가 사람의 수라고 했을때 시간 복잡도는 O(RP)가 된다. 2. 무식하지만 조금 나은 방법 해마다 태어난 인구수를 기록하는 배열을 만들고, 사람을 순회하면서 배열에 기록한다. (배열을 잡..

문제 임시 변수를 사용하지 않고 숫자를 교환하는 함수를 작성하라. 해법 이 문제는 두 수중 하나의 수에 그 둘의 '차이'를 가지고 있도록 하면 해결할 수 있는 문제이다. 숫자 a, b가 있다면 a = a-b 를 통해 a가 차이를 가지고 있도록 하고, b = a +b 를 통해 a가 된다. 그리고 다시 a = b -a를 통해 a 는 b가 된다. a = 9 b = 4라고 할때 a = a- b ( a = 9 - 4 =5) b = a+b (b = 5+4 =9) a = b-a ( a = 9-5 =4) 비트로도 같은 연산이 가능하다. 이러면 정수 이외의 자료형에서도 동작한다는 이점이 있다. a = a^b b = a^b a = a^b

300. Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note: There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2)..

322. Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], a..

62. Unique Paths A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? Note:..

55. Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: [3,2,1,0,4] O..

33. Search in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm's runtime complexity must be in the order of O(lo..

56. Merge Intervals Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6]. Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping. NOTE: input types have been changed on Ap..

34. Find First and Last Position of Element in Sorted Array Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums..