develop

날마다 주식의 가격을 prices 배열로 주고, 주식을 사고팔아서 얻을 수 있는 최대 이익을 구하는 문제다. python을 사용해서 3번의 시도 끝에 풀었으며, 접근 방법과 솔루션에 대해 소개한다. 연관 문제로 Best Time to Buy and Sell Stock 1~3 등이 있다. 다양한 접근방법으로 풀어볼 수 있어서 흥미로웠던 문제이다. 122. Best Time to Buy and Sell Stock II 문제 링크 Solution 바로가기   First Approach (5분) 문제 이해 문제를 명확히 하기 위한 과정(Q&A) 생각나는 알고리즘/자료구조 주식을 사고파는데, 최대 1주만 보유할 수 있다. price가 최소일 때 사야 할 것 같다는 생각이 들었다. 최소에서 팔 수 있을 때까지 날마다 diff profit을 저장해놓으면? DP를 적용해도 될 것 같은데 DP를 정확히 모르겠다. 합이 더 크면 더 큰 노드로 옮겨가고, 작아질 때 멈추고 하면 될 것 같은데, 각 node 들의 차이를 합해 나가는 방법으로도 가능할 것 같다.    First Solution(brute force) class Solution: def calculate(self, prices: List[int], start: int) -> int: max_profit = 0 max = 0 if start < len(prices): for s in range(start, len(prices)): for e in range(start+1, len(prices)): if prices[e] - prices...

Leetcode 문제 풀이를 코딩 인터뷰를 준비하는 관점에서 어떻게 하면 더 효과적으로 할 수 있을지 생각해 보고, 기준을 정했다.  기술 면접을 준비하기 위해 Leetcode의 문제를 해결하는 방법 한 주에 하나의 주제만 일관된 시간/정해진 시간을 정해 놓고 매일 1~2시간 가장 약한 주제에 집중 1st step: easy 전부 풀기 2nd step: easy/medium/hard 중 medium의 80%를 풀 정도면 넘어가기 시간제한 easy: 20분 medium: 45분 hard: 60분 Hint/Forum 활용 시간 안에 풀지 못한 문제는 solution 을 보고 확실히 공부하기 어떤 문제를 해결했는지, 그 문제에 몇 분을 할당했는지 진행 시트를 직접 만들어 관리하기 효과적인 문제 해결 과정 문제 난이도에 따라 타이머를 설정한다. 문제를 이해하는데 5분을 사용한다. 명확하게 이해하기 위해 스스로 질문/답을 해본다.  문제를 보고 중요해 보이는 부분을 적어두고, 생각나는 알고리즘/자료구조 등 접근 방법을 적는다. 이런 방식은, 나중에 나의 경향성을 확인할 수 있다. 비슷한 사고를 하거나 편협한 생각을 하는 것을 객관적으로 깨달을 수 있을 것이다.  나머지 시간은 종이와 펜을 사용해 문제를 푸는데 집중한다. Solution을 공부하는데 10분을 쓴다. (10분은 권고) Solution을 완벽하게 이해하지 못했더라도, 한 문제에 30-35분 이상 할애하지 않는다. 문제를 풀었던 과정과 결과를 ...

정렬된 배열에서 중복된 원소를 제거하는 문제를 풀었다. 코딩 인터뷰 관점에서 문제 해결 과정을 brute force 방법부터 시간, 공간 복잡도를 고려하는 과정까지 순서대로 정리하고 python/C++ 최적 Solution까지 정리해 봤다. Easy Collection - Top Interview Questions - Array Remove Duplicates from Sorted Array 리트코드 문제 링크   Solution 바로보기 First Approach (5분) 문제 이해 중복을 제거하는데, 순서는 그대로 유지해야 된다. 중복 제거된 후의 개수 K를 return 하고, 처음 주어진 array의 배열 크기는 그대로 두어도 된다. K 뒤로 오는 배열 안의 원소는 don't care 배열을 추가로 선언하면 안 되고 주어진 배열 안에서 수정해야 한다. O(1) extra memory 문제를 명확히 하기 위한 과정(Q&A) 생각나는 알고리즘/자료구조 앞의 원소는 그대로 두고, 뒤에 나오는 원소는 뒤로 이동시킨다. 뒤로 보내면 뒤쪽 index도 가지고 있어야 됨 앞에서부터 순회, 뒤에 교체된 index 가 K가 될 것 같다. 처음 K는 nums array length로 시작?   First Solution(brute force) index i = 0부터 중복되는 count를 세면서 순회하고, K 는 N(nums array의 length) 중복되는 count만큼 K = N - count i + 1에 i + count + 1 부터 가져옴 다음 i++ 부터 다시 순회 시작 Second Solution 순회하면서 중복되는 원소를 곧바로 제거하고, 뒤에 있는 원소들을 앞으로 ...