본문 바로가기

컴퓨터공학 & 정보통신84

[LeetCode] 200. Number of Islands 접근 오히려 easy난이도보다 쉬운 문제인 것 같다 제공되는 자료형이 숫자가 아니라 문자임을 감안하지 않아 조금 고민 일반적인 방법의 코드도 숙지하는 것이 중요해 보임 문제 https://leetcode.com/problems/number-of-islands/description/ 솔루션 class Solution: def numIslands(self, grid: List[List[str]]) -> int: answer = 0 ROW_length = len(grid) COL_length = len(grid[0]) visited = [[False for _ in range(COL_length)] for _ in range(ROW_length)] def dfs(ROW, COL): # update this p.. 2023. 3. 26.
[LeetCode] 463. Island Perimeter 접근 각 사이드를 확인하여 perimeter를 추가해야 하는 지 그렇지 않은 지를 논리적으로 확실하게 구분하는 것이 핵심 문제 조건 중 섬의 갯수는 무조건 하나이므로 DFS나 DFS를 사용하여 탐색 성능을 높이는 것이 중요해 보임 논리적 흐름이 잘못되었으면 동일한 코드를 수정하기 보다 논리적 흐름을 재설정하여 코드를 새롭게 짜는 것이 좋은 습관인 것 같음.. 문제 링크 https://leetcode.com/problems/island-perimeter/description/ 솔루션 class Solution: def islandPerimeter(self, grid: List[List[int]]) -> int: perimeter = 0 ROW_length = len(grid) COL_length = len.. 2023. 3. 25.
[LeetCode] 131. Palindrome Partitioning 접근 평이한 백트래킹 문제 pailndrome을 체크하는 방법을 어렵지 않으나 파이썬 문법을 제대로 이해하지 못하여 시간이 많이 걸렸다. 내가 알고리즘을 푸는 것인지 파이썬 문법을 공부하는 것인지.. 솔루션 class Solution: def partition(self, s: str) -> List[List[str]]: answer = [] s_length = len(s) def backtrack(answer_list, index): if index == s_length: answer.append(answer_list) return for i in range(index, s_length): current_str = s[index:i+1] if current_str == current_str[::-1]: .. 2023. 3. 23.
[LeetCode] 46. Permutations 접근 문제 자체는 기타 평이한 백트래킹 문제와 다를 바 없었지만 파이썬 리스트에 대한 개념 이해 부족으로 시간을 많이 씀 재귀 함수 내에서 리스트는 참조가 아닌 복사본을 활용하는 것을 권장 시간 버리는 문제라고 생각했는데 오히려 파이썬 리스트 좀더 깊게 알게 되는 계기가 되었음...😅 솔루션 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: answer = [] nums_length = len(nums) if nums_length == 1: answer.append(nums) return answer def backtrack(answer_list): if len(answer_list) == nums_length: answer.a.. 2023. 3. 21.
[LeetCode] 17. Letter Combinations of a Phone Number 접근 난이도가 있는 문제는 아니지만 특수한 상황에 탐색 기법을 사용하여 솔루션을 작성할 수 있느냐를 묻는 문제 예제가 부실함. 3가지 이상의 예제도 좀 넣어주지... 솔루션 class Solution: def letterCombinations(self, digits: str) -> List[str]: answer = [] digits_length = len(digits) if digits_length == 0: return answer # create mapped list # this result dial list to be # ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] dial = ["", ""] index = 97 for i.. 2023. 3. 20.
[LeetCode] 22. Generate Parentheses 접근 기본적인 백트래킹 문제, 문제 조건이 크게 까다롭지 않아 브루트 포스로 풀 수도 있지만 백트래킹 방법이 출제 의도인 것 같음 문제의 해답이 될 수 있는 경우에 대한 경우를 일반화해야 함. 여기서 막혔음 자연스럽게 중간에 오답이 되는 케이스는 흘려 보내는 논리 흐름이 백트래킹의 핵심 스택이 아닌 변수를 활용하여 괜찮은 솔루션을 작성할 수 있음 솔루션 class Solution: def generateParenthesis(self, n: int) -> List[str]: answer = [] def backtracking(answer_str, left, right): # if it reach to the end, add answer if len(answer_str) == n*2: answer.appen.. 2023. 3. 20.

티스토리툴바