본문 바로가기

컴퓨터공학 & 정보통신/알고리즘 문제 풀이41

[LeetCode] 79. Word Search 접근 항상 리스트 자료형을 활용할 때에는 조심해야 한다. 대중적인 접근법을 사용해서 문제 풀이, 가능 여부와 관계없이 선행 탐색 후 올바르지 않는 경우를 조건문을 통해 거르는 로직 진행 백트래킹 함수 구현 시 boolean 형을 리턴하는 방식을 추천, 괜찮은 테크닉을 구현할 수 있다. 문제 https://leetcode.com/problems/word-search/description/ 솔루션 class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROW_length = len(board) COL_length = len(board[0]) WORD_length = len(word) def backtrack(ROW, COL, i.. 2023. 3. 26.
[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.

티스토리툴바