본문 바로가기

알고리즘

 (43)
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] -> ..
Search for a Range | LeetCode 802 | Python3 🐍 📄 목차 🤔 문제 : Longest Palindromic Substring | LeetCode 802 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/ 정렬된 배열에서 타겟이값이 나오는 구간을 찾는 문제입니다. time complexity 를 O(logN)으로 하라는 단서가 있습니다. 💡 풀이 1. Binary Search 시작점, 끝점을 찾는 binary search를 두번 수행하는 방식으로 코드를 작성했습니다. class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: ..
Sort Colors | LeetCode 798 | Python3 🐍 📄 목차 🤔 문제 : Longest Palindromic Substring | LeetCode 780 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/798/ 주어진 배열을 정렬하는 문제입니다. 단, 이 문제에서 배열의 값은 0,1,2중 하나입니다. quick sort를 활용한다면 O(NlogN) 이 걸리겠지만, 배열의 값이 정해져있다는 점을 활용하여 더 빠르게 풀 수 있습니다. 💡 풀이 1. hashMap활용, 0,1,2의 갯수 count 배열에서 나오는 값을 이미 알고 있기 때문에, 이를 활용해봅니다. nums를 읽으며 0,1,2의 갯수를 저장하고, 한번 더 순회..
Permutations, Subsets | LeetCode | Python3 🐍 📄 목차 백트레킹의 대표적인 문제인 permutation과 subset을 풀어보겠습니다. 🤔 문제1 : Permutations 문제: https://leetcode.com/problems/permutations/ 주어진 리스트로 순서를 조합하여 만들 수 있는 모든 리스트을 만들어 반환하는 문제입니다. class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ret = [] def getPermutation(current_array, item_list): ret.append(current_array) if not item_list: return for idx in range(len(item_list)): getPermutation(cur..
Generate Parentheses | LeetCode 780 | Python3 🐍 📄 목차 🤔 문제 : Generate Parentheses | LeetCode 794 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/ Stack을 활용한 단골문제 중 하나인 괄호만들기입니다. n개의 열린괄호, 닫힌괄호를 활용하여 잘 닫힌 괄호들을 만들어 리스트로 반환하면 됩니다. 잘 닫힌 괄호(?) ((())) [O] ()) [X] 연 것 보다 더 많이 닫음 ((()) [X] 하나를 덜 닫음 💡 풀이 1. 접근 - 잘 닫힌 괄호의 조건은? ((())) [O] ()) [X] 연 것 보다 더 많이 닫음 ((()) [X] 하나를 덜 닫음 위의 괄호 케이스들을 보며 잘 닫힌 괄호임..
Letter Combinations of a Phone Number | LeetCode 793 | Python3 🐍 📄 목차 🤔 문제 : Letter Combinations of a Phone Number | LeetCode 793 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/793/ 숫자 -> 3~4개의 문자 로 매핑될 때 숫자 input이 주어지면 가능한 모든 문자 output을 리스트로 만들어 반환하는 문제입니다. 💡 풀이 1. 접근 - BFS? DFS? BFS : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법 DFS : 하나의 분기를 완벽하게 탐색한 뒤에야 다른 이웃 노드를 방문하는 방법 input이 23이라고 할..
Longest Palindromic Substring | LeetCode 780 | Python3 🐍 📄 목차 🤔 문제 : Longest Palindromic Substring | LeetCode 780 문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/780/ palindorme : 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 주어진 문자열에서 가장 긴 palindrome을 찾는 문제입니다. palindrome은 항상 홀수 palindrome 짝수 palindrome 두가지 케이스 모두 고려해야 합니다.! 홀수 palindrome: babad 짝수 palindrome: cbbd 💡 풀이 1. 문자열을 순회하며..

티스토리툴바