본문 바로가기

INT NUM

 (164)
Task Scheduler | LeetCode 826 | Python3 🐍 📄 목차 🤔 문제 : Task Scheduler | LeetCode 826 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/826/ input으로 Task리스트와 cooltime값인 숫자 n이 들어옵니다. 같은 Task사이에는 무조건 n 이상의 cooltime을 쉬어야 합니다. 이런 상황에서 주어진 task를 다 처리하기 위해 필요한 최소 cpu time을 구하는 문제입니다. 가장 남은 task를 가장 먼저 처리한다 까지는 직관적으로 이해가 되었고, 그래서 task를 처리해가며 남은 task를 계속 sorting해서 다음 task를 뽑고, cooltime은 deque로 관리하였는데도 TLE가 ..
Majority Element | LeetCode 824 | Python3 🐍 📄 목차 🤔 문제 : Majority Element | LeetCode 824 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/114/others/824/ 주어진 배열에서 절반 이상을 차지하는 원소를 구하는 문제입니다. 단, Could you solve the problem in linear time and in O(1) space? 💡 풀이 1. Majoirity Component는 다른 원소 다 합친거보다 더 많이 나온다는 점! 그냥 dictionary 이용해서 각 원소별 나온 횟수 count하는 걸로는 도저히 O(1) space만에 해결이 안 되어 discussion을 봤습니다.. ㅎ 핵심은 Majoirit..
Divide Two Integers | LeetCode 820 | Python3 🐍 📄 목차 🤔 문제 : Divide Two Integers | LeetCode 820 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/820/ 나눗셈 연산자를 사용하지 않고 나눗셈의 몫을 구하는 문제입니다. 초등학교에서 배운.. 10/3 이라 하면 10-3-3-3.. 해서 양수일 때 까지 뺀 횟수를 구하는 방식이 떠오르네요. 1번 풀이는 그 풀이에서 반복을 활용하여 연산횟수를 log로 줄이는 방식이고 2번 풀이는 shift연산자를 활용한 풀이입니다. 💡 풀이 1. 뺄셈 반복을 통한 몫 구하기 16/2 의 몫을 구한다고 하면 16 - 2- 2 - .... 이렇게 2을 반복하여 빼겠지요? 어차피 2로 ..
Search a 2D Matrix II | LeetCode 806 | Python3 🐍 📄 목차 🤔 문제 : Search a 2D Matrix II | LeetCode 806 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/806/ Matirx상에서 타겟값이 있는지 확인하는 문제입니다. 단, Matrix는 각 행, 열이 모두 정렬되어있습니다. 💡 풀이 1. 각 열에 대해 BS 당연히 BS로 접근해야 하는 문제로 생각했습니다. 1) 각 열의 첫번째 항을 순회합니다. 첫 행을 순회하는게 되겠죠. 2) 열의 첫번재 값이 타겟값보다 작으면, 그 열에 타겟값이 있을 수 있다는 뜻이겠죠? 해당 열에 대해 BS를 합니다. class Solution: def sear..
Search in Rotated Sorted Array | LeetCode 804 | Python3 🐍 📄 목차 🤔 문제 : Search in Rotated Sorted Array | LeetCode 804 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/804/ 정렬된 배열에서 타겟 숫자의 인덱스를 찾는 문제입니다. 단, 여기서 배열은 rotated 되어있습니다. 예를들어, [0,1,2,4,5,6,7] 배열을 오른쪽으로 4칸 옮겨 [4,5,6,7,0,1,2] 를 만드는 식입니다. 💡 풀이 1. Rotate 된 시작점을 찾은 후 한쪽 범위에서 BS 가장 먼저 떠올린 풀이는 어느부분부터 Rotate된 것인지, pivot을 찾자는 거였습니다. nums = [4,5,6,7,..
[AWS] AWS CDK 시작하기 (1) | Javascript, AWS Configure, CDK Init, CDK deploy, lambda, api gateway 📄 목차 1. AWS & CDK 설정 AWS Configure 기존에 aws configure를 통해 AWS와 로컬이 연결되어 있다면 건너뛰어도 됩니다. aws configure list AWS의 IAM에서 키페어(AWS Access Key, AWS Secret Access Key) 발급 참고) 키페어 발급 https://docs.aws.amazon.com/ko_kr/cli/latest/userguide/cli-configure-quickstart.html#cli-configure-quickstart-creds terminal에서 aws configure 커맨드를 통해 aws 계정 연결 $ aws configure AWS Access Key ID: [aws 에서 IAM생성하여 입력] AWS Secret ..
Coin Change | LeetCode 809 | Python3 🐍 📄 목차 🤔 문제 : Coin Change | LeetCode 780 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/809/ 동전을 조합하여 가장 적은 동전 조합으로 주어진 금액을 만드는 문제입니다. 전형적인 Dynamic Programming 문제네요. Dynamic Programming 1. 큰 문제는 작은 문제로 나누어 푼다 2. 작은문제에서 푼 정답은 기억해두었다가 동일한 문제가 나오면 그대로 활용한다. 💡 풀이 1. Top Down amount에서 동전만큼씩 깎아내려가는 방식입니다. dp()라는 함수를 recursive하게 호출하게 됩니다. from typin..
Merge Intervals | LeetCode 803 | Python3 🐍 📄 목차 🤔 문제 : Merge Intervals | LeetCode 803 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/803/ 배열로 주어진 범위(interval)들을 합치는 문제입니다. 예를들어 [1,3], [2,4]가 들어오면 -> [1,4] 로 합쳐집니다. 💡 풀이 접근 : interval이 겹치는 종류 일단 interval끼리 어떤 방식으로 겹칠 수 있을지 생각해보았습니다. 1. left overlapping : 새로 들어오는 interval의 왼쪽 범위가 기존에 있던 범위의 오른쪽에 겹쳐서 들어감 ex) 기존 : [1, 3] 신규: [2, 4] -> ..

티스토리툴바