철학과 함께하는 투자인사이트

이 문제는 O(logN)으로 풀라고 나와있다. logN으로 주어진 것이면 우리는 binary search라는 것을 직감적으로 알아야한다. 바로 최소값을 찾기 위한 여정을 해야하는데, 안타깝게도 좌로 n번이 회전이 되어있는 array안에서 찾아야한다. 이런 경우에는 우리는 문제에 어떻게 다가갈 것인지 생각을 해봐야한다. 즉 mid로 항상 중앙에 위치한 값을 찾으면서, 역전이 일어난 부분이 있다면 그 부분이 변곡이 일어난 곳이며, 각 최대값 또는 최소값이 해당 mid 주변에 위치해있다는 뜻이다. 완성된 코드는 아래와 같다 class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) =..

class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ max_product = nums[0] min_product = nums[0] ans = nums[0] for i in range(1, len(nums)): min_val = min_product*nums[i] max_val = max_product*nums[i] max_product = max(min_val, nums[i], max_val) min_product = min(min_val, nums[i], max_val) ans = max(ans, max_product) return ans

합이 최대가 되는 subarray를 찾고 그 합을 구하는 문제이다. O(n)으로 풀지 않으면 Times Limit Exceeded가 뜬다. 따라서 Brute force로 풀면 array를 탐색하면서 가능한 모든 subarray를 비교하게 될 것이다. 코드는 짧지만 subarray의 합이 최대가 되는 경우를 생각해야 한다. current_sum이라는 값을 두고, max_sum이라는 값을 따로 둔다. current_sum은 이전에 구한 합과 현재의 값을 비교하여 더 큰 값을 저장하는 변수다. max_sum은 첫 번째 값으로 초기화한 뒤 current_sum과 비교해 더 큰 값을 항상 저장한다. current_sum은 현재 index의 값을 포함하는 값 중 최대가 되는 합이고, max_sum은 전체 array..

배열을 순회하면서 각 idx에 있는 수를 제외한 나머지들을 모두 곱한 값을 출력하는 문제 게다가 문제에서도 O(n)의 시간복잡도로 풀이를 하라고 되어있다. [1,2,3,4]의 경우는 [ 2*3*4 , 1*3*4, 1*2*4, 1*2*3] 인 [24, 12, 8, 6] 이 답인 것이다. 이는 뒤집에서 생각해보면, [1*2*3*4 / 1 , 1*2*3*4 / 2 , 1*2*3*4 / 3 , 1*2*3*4 / 4] 의 계산으로도 가능하기 때문에, 전체 의 곱인 24를 구하고 각 1,2,3,4로 나누면 되는 것이다. 이때 주의해야 하는 점이 리스트에 0이 포함되는 경우이다. [-1, 1, 0, -3, 3]인 경우, 모든 곱을 하게 되면 0이 나오니 위의 로직을 그대로 따른 다면 [0, 0, 0, 0, 0]이 나..

굉장히 쉽다 즉 distinct 한지 아닌지만 확인하면 되기 때문에, 배열의 길이와 set(배열)의 길이가 같은지 다른지만 체크하면 OK. class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ if len(set(nums)) == len(nums) : return False return True

하루에 한번 매매를 할 수 있을 때, 어떻게 하면 저점에 사서, 고점에 팔 수 있는 알고리즘을 짜는 것이다. for loop를 두번 도는 것이 아닌, 매 loop를 돌 때마다 최고 가격과 최저가격을 기록하면 되는 것이므로, 아래와 같이 그냥 O(n)으로도 풀이가 가능하다. class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ import sys profit = 0 min_price = sys.maxsize for price in prices: if price profit : profit = ..

New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode questions that teach you core concepts and techniques for each category/type of problems! Many other LeetCode questions are a mash of the techniques from these individual questions. I used this list in my last job hunt to only do the important questions. Good luck and Happy New..

1. vim-plug설치 curl -fLo ~/.vim/autoload/plug.vim --create-dirs \ https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim 2. ~/.vimrc 만들기 call plug#begin('~/.vim/plugged') Plug 'fatih/vim-go' Plug 'gmarik/Vundle.vim' Plug 'nanotech/jellybeans.vim' Plug 'majutsushi/tagbar' Plug 'scrooloose/nerdtree' Plug 'nathanaelkane/vim-indent-guides' Plug 'airblade/vim-gitgutter' " vim with git sta..

우연히 Go와 성능이 비슷하다는 Fastapi를 접하고 나서 주말에 시간 여유를 내서 가볍게 두드려본다. FastApi fastapi.tiangolo.com/ FastAPI FastAPI FastAPI framework, high performance, easy to learn, fast to code, ready for production Documentation: https://fastapi.tiangolo.com Source Code: https://github.com/tiangolo/fastapi FastAPI is a modern, fast (high-performance), web framework for buil fastapi.tiangolo.com 일반 html이 서빙이 가능하도록 일단은 ..