코딩하는 오리

[문제] 모든 부분 집합을 리턴하라 · 입출력 예 num_list return [1, 2, 3] [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []] [풀이] 입력값으로 트리를 구성하고, 트리를 DFS하는 문제로 풀이할 수 있다. 경로 (path)를 만들어 나가면서, 인덱스를 1씩 증가하는 형태로 깊이 우선 탐색을 진행하였다. 별도의 종료 조건이 없기 때문에, 탐색이 끝나면 저절로 함수가 종료된다. 입력받은 숫자 배열로 만들 수 있는 모든 부분 집합들이 정답이기 떄문에, dfs를 진행할 때마다 결과 배열에 값을 추가하고, 이를 반환하는 형태로 문제를 풀었다.

[문제] 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라 · 입출력 예 string return "abcabcbb" 3 (abc) "bbbbb" 1 (b) "pwwkew" 3 (wke) [풀이] 1. 슬라이딩 윈도우와 투 포인터 사이즈 조절 def lengthOfLongestSubstring(s: str) -> int: used = {} max_length = start = 0 for index, char in enumerate(s): if char in used and start

[문제] 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라 · 입출력 예 digits return "23" ["ad", "ae", "af", "bd", "bf", "bf", "cd", "ce", "cf"] [풀이] 1. 모든 조합 탐색 -> 가능한 경우를 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다. 입력값 digits를 자릿수로 쪼개어 반복하고, 숫자에 해당하는 모든 문자열을 반복하며 문자 단위로 재귀 탐색을 진행한다. 문자를 조합해 만들 수 있는 길이는 입력값의 길이와 동일하므로, 해당 조건을 재귀함수의 종료 조건으로 설정하고, 조건에 맞지 않을 경우 dfs를 반복 수행한다.

[문제] 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라) · 입출력 예 grid map return 11110 11010 11000 00000 1 11000 11000 00100 00011 3 [풀이] 1. DFS로 그래프 탐색 이와 같이 작성하였을 경우, grid를 dfs 함수 호출시마다 넘겨주어야 하고, 함수 호출 시 매번 self.가 따라 붙는다. 2. DFS로 그래프 탐색 (중첩함수 사용) DFS 탐색을 하는 dfs 함수는 동서남북을 모두 탐색하며 재귀호출한다. 이동하고자 하는 곳이 육지가 아닌 경우에 return 하도록 설정해 줌으로써 연결되어 있는 섬을 구할 수 있다. 이 함수에서 이미 방문했던 곳(grid[i..

[문제] 매일의 화씨 온도(˚F) 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라 · 입출력 예 T [73, 74, 75, 71, 69, 72, 76, 73] return [1, 1, 4, 2, 1, 1, 0, 0] [풀이] 1. 스택 값 비교 -> 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교 하여, 더 높다면 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다. def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in en..

[문제] 괄호로 된 입력값이 올바른지 판별하라. · 입출력 예 s return ()[]{} True [풀이] 1. 스택 일치 여부 판별 -> 파이썬 리스트는 스택 연산인 푸시와 팝이 O(1)에 동작한다. def isValid(s: str) -> bool: stack = [] table = { ')':'(', '}':'{', ']':'[' } for char in s: if char not in table: stack.append(char) elif not stack or table[char] != stack.pop(): return False return len(stack) == 0 매핑 테이블을 만들어놓고, 매핑 테이블에 존재하지 않으면 푸시하고, 팝했을 때 결과가 일치하지 않으면 False를 리턴한다..

[문제] 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. · 입출력 예 nums target return [2, 7, 11, 15] 9 [0, 1] [풀이] 1. 브루트 포스로 계산 def twoSum(nums: list[int], target: int) -> list[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] 브루트 포스란 배열을 2번 반복하며 모든 조합을 더해 일일이 확인해보는 무차별 대입 방식으로, 비효율적인 풀이법에 해당한다. nums 배열을 이중 탐색하며 nums[i], nums[j] 두 값을 더했을 때 target이 되..