본문 바로가기

알고리즘

 (43)
Remove Invalid Parentheses | LeetCode 301 | Python3 🐍 📄 목차 제목: https://leetcode.com/problems/remove-invalid-parentheses/🐍 🤔 문제 : Remove Invalid Parentheses | LeetCode 301 문제: https://leetcode.com/problems/remove-invalid-parentheses/ 주어진 문자열에서 가장 긴 palindrome을 찾는 문제입니다. 💡 풀이 1. 구구절절.. iteration 주어진 s의 모든 substring에 대해서, valid parenthesis 여부를 확인하면서, 가장 긴 것들을 저장해서 반환해야 겠다. 그럼 TLE 가 날 것 같으니, (와 )의 갯수를 대조해서 더 많은걸 많은 갯수만큼 삭제한 substring먼저 확인하고.. 거기서 없으면 (..
Big-O 표기법 (1) 기본 원칙, 배열(ArrayList), 재귀함수, 이진트리(Binary Tree, BT)에서의 Big-O 알고리즘 문제를 풀다보면 big-O notation을 통해 시간복잡도, 공간복잡도를 계산하곤 합니다. 저는 대략적인 호출 수, for loop, 캐싱 등을 염두에 두고 계산하곤 했는데요, CTCI(Cracking the Code Interview)책을 읽다 보니 recursion, string, binary tree 등에서 보다 정확한 Big-O Notation에 대한 부분이 있어 정리해두려고 합니다. 01. big-O 표기법이란? big-O 표기법은 N에 따라 수행시간이 어떻게 변화하는지를 표현해주는 도구입니다. 두 big-O 표기법 중 어떤게 더 수행시간이 빠른지를 비교하는것이 아닙니다! 즉, big-o 표기로 더 크다고 해서 항상 더 느린 것은 아닙니다. 입력과 연산에 따라 O(N) 코드가 O(1)..
Longest Increasing Subsequence | LeetCode 810 | Python3 🐍 📄 목차 🤔 문제 : Longest Increasing Subsequence | LeetCode 810 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/810/ 주어진 리스트 내 가장 긴 increasing subsequence 의 길이를 찾는 문제입니다. subsequence 란 배열에서 몇개의 요소를 삭제해서 만들 수 있는 sequnce를 말합니다. (순서는 바꾸지 않습니다) 예를들어, [2, 1, 3]의 subsequence는 아래와 같습니다. [2, 1, 3], [2, 1], [2, 3], [1, 3], [2], [1], [3], [] increasing subs..
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,..

티스토리툴바