SW개발/코딩테스트
[LeetCode]Perfect Squares
https://leetcode.com/problems/perfect-squares/description/ Perfect Squares - LeetCode Can you solve this real interview question? Perfect Squares - Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some in leetcode.com 문제 분석 n이 주어질 때 완전 제곱수 몇개를 더하여 n을 만들 수 있는지 ..
[Leetcode]Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 Trie 자료 구조를 구현하는 문제입니다. insert, search, startsWith 함수를 구현하면 됩니다. 처음 시도한 답안 class Trie: def __init__..
[LeetCode]Word Break
https://leetcode.com/problems/word-break/description/ Word Break - LeetCode Can you solve this real interview question? Word Break - Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may leetcode.com 문제 분석 문자열 s와 단어 집합인 wordDict가 주어진 경우에, 문자열 s를 wordDi..
[LeetCode]Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/description/ List[List[str]]: answer = [] def dfs(i, path): if i == len(s): answer.append(path) return for j in range(i, len(s)): a = s[i:j+1] if a == a[::-1]: dfs(j+1, path + [a]) dfs(0, []) return answer 접근 방법 DFS를 활용해 풀이합니다. dfs 내부에서 탐색한 깊이가 주어진 문자열 길이가 된다면 정답에 path를 추가합니다. 주어진 문자열을 모두 사용했다는 의미입니다. 전달받은 i 부터 문자열 길이까지 반복합니다. 대상이 되는 문자열을 파티셔..
[LeetCode]Edit Distance
https://leetcode.com/problems/edit-distance/ Edit Distance - LeetCode Can you solve this real interview question? Edit Distance - Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: * Insert a character * D leetcode.com 문제 분석 주어진 word1을 word2로 만들기 위해 필요한 Operation의 최소 횟수를 구하는 문..
[LeetCode]Unique Paths
https://leetcode.com/problems/unique-paths/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 주어진 그리드에서 가장 오른쪽 아래로 가는 Unique 경로의 수를 구하는 문제입니다. 처음 시도한 답안 - 실패, DFS 이용 class Solution: def uniquePaths(self, m: ..
[LeetCode]House Robber II
https://leetcode.com/problems/house-robber-ii/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 강도가 들키지 않고 가장 많은 돈을 훔칠수 있는 값을 구하는 문제입니다. 단, 집이 원형으로 이어져있다고 가정합니다. 처음 시도한 답안 class Solution: def rob(self, nums..
[LeetCode]House Robber
https://leetcode.com/problems/house-robber/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 강도가 들키지 않고 가장 많은 돈을 훔칠수 있는 값을 구하는 문제입니다. 처음 시도한 답안 class Solution: def rob(self, nums: List[int]) -> int: if len(..
[LeetCode]Maximal Square
https://leetcode.com/problems/maximal-square/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 주어진 이차원 Matrix에서 가장 큰 정사각형에 포함된 1의 갯수를 구하는 문제입니다. 처음 시도한 답안 - 실패 class Solution: def maximalSquare(self, matrix..
[LeetCode]Triangle
https://leetcode.com/problems/triangle/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 분석 triangle 리스트가 주어질 때 위에서부터 아래로 이동시 가장 최소가 되는 경로의 합을 구하는 문제입니다. 처음 시도한 답안 class Solution: def minimumTotal(self, triang..