잡다한 IT 지식

문제 출처 : https://leetcode.com/problems/climbing-stairs/description/ [문제 설명] 계단을 1걸음, 2걸음 오를 수 있을 때 n번째 계단까지 오를 수 있는 방법은? [접근 방법] 전형적인 dp 연습문제. n번째 계단에 올라가는 방법은 n-1번째 계단에서 1걸음 올라가기 + n-2번째 계단에서 2걸음 올라가기 점화식 : dp[n] = dp[n - 1] + dp[n - 2] 굳이 배열을 사용하지 않고 변수만 두고도 풀 수 있는 문제지만 n의 최대 크기가 45밖에 되지 않으므로 배열을 사용하여 풀었다. class Solution { public: int climbStairs(int n) { if (n

문제 출처 : https://leetcode.com/problems/design-a-number-container-system/ [문제 설명] insert, find 함수를 구현하시오. insert(int index, int number) : 해당하는 인덱스의 number 값을 대입한다. find(int number) : number를 가지는 인덱스 중에서 최솟값을 반환하라. 단, number에 해당하는 값이 없으면 -1을 리턴 [접근 방법] 1. 인덱스와 값을 구현하기 위해서 단순 배열을 사용하면 어떨까 생각 2. 그러나, 주어진 number의 최댓값이 10^9이므로 단순 배열 생성에만 10^9가 필요함. 3. map을 통해 key를 인덱스 value를 숫자로 하는 맵과 key를 숫자 value를 인덱..

문제 출처 : https://leetcode.com/problems/search-insert-position/description/ [문제 설명] The array is sorted. so you can use a binary search algorithm, not a linear search. the time complexity of a linear search is O(N) but a binary search is O(logN). (N is the size of the array) The given array has consisted of distinct integers. So if you find a target's index then you should return the index. if you..