반응형 전체 글124 [DSA][Backtracking] 07. Word Search LeetCode 79 07. Word SearchGiven an m x n grid of characters board and a string word, return true if word exists in the grid.The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring.The same letter cell may not be used more than once. [아이디어]- board에서 word의 첫 글자와 일치하는 칸을 시작점으로, DFS를 사용해 상·하·좌·우로 탐색하며 word를 순서대로 탐색한다... 2025. 12. 16. [DSA][Backtracking] 06. Catalan Numbers Problem지난번 Generate Parenthesis 문제에서 정수 n이 주어졌을 때 만들 수 있는 모든 유효한 괄호 문자열(valid parentheses)을 구했는데 (2025.12.04 - [자료구조와 알고리즘] - [DSA][Backtracking] 06. Generate Parentheses), 이 문제를 분석하다 보면 아래와 같은 다소 직관적으로 이해하기 어려운 시간 복잡도가 등장한다. 이번 포스팅에서는 이 복잡도가 어디서 나오는 결과인지를 수학적·직관적으로 살펴보자. 먼저 문제 조건을 다시 해석해 보자.괄호 쌍이 n개라는 것은 여는 괄호 '('가 n개, 닫는 괄호 ')'가 n개로 총 2n개의 문자가 주어진다는 뜻이다. 이 문자들을 나열하는 모든 경우의 수는 2n개의 자리 중에서 '('.. 2025. 12. 13. [DSA][Backtracking] 06. Generate Parentheses LeetCode 22 06. Generate ParenthesesGiven n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. [아이디어]- '('의 개수가 ')'의 개수보다 많을 때만 ')'를 붙이며 backtracking 한다. [풀이 1] Backtrackingclass Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def dfs(tmpStr, left, right): if left + right == 2 * n: re.. 2025. 12. 4. [DSA][Backtracking] 05. Subsets II LeetCode 90 05. Subsets IIGiven an integer array nums that may contain duplicates, return all possible subsets (the power set).The solution set must not contain duplicate subsets. Return the solution in any order. [아이디어]- 각 원소가 포함되는 경우와 포함되지 않는 경우를 나누어 가능한 모든 부분 집합을 탐색하고, 같은 level에서 중복된 숫자가 있으면 PASS 한다. [풀이 1] Backtrackingclass Solution: def subsetsWithDup(self, nums: List[int]) -> List[Lis.. 2025. 11. 30. 이전 1 2 3 4 ··· 31 다음