Leetcode 17 문제 보기 문제 이해하기 스마트폰이 출현하기 이전, 휴대폰의 자판은 위 그림과 같았다. 전화번호의 각 번호는 특정 알파벳들과 매칭이 된다. 어떤 번호가 주어진다면, 해당 번호를 이용해 출력 가능한 단어들을 구하라. 번호는 2~9로 이루어져 있으며, 번호의 길이는 최소 0부터 최대 4까지 가능하다. 아이디어 구상 Decision Tree를 그리며 생각해보자. digits = "23"인 test case를 살펴보자. 이 때 트리의 각 level은 주어진 digits의 각 숫자를 탐색하는 경우에 해당된다. 모든 조합을 찾아야하므로, Brute Force하게 탐색을 해야한다. DFS를 활용해 가능한 알파벳 조합들을 하나씩 얻어 결과 리스트에 넣고, 최종적으로 정답을 출력하면 되겠다. 이 때..

Leetcode 131 문제 보기 문제 이해하기 알파벳 소문자로 이루어진 String s에 대하여 파티션을 나누었을 때, 각각의 substring들이 팰린드롬일 경우의 파티션들을 출력하라. 팰린드롬이란, 순서를 뒤집어도 본래의 단어와 같은 단어를 의미한다. 아이디어 구상 Decision Tree를 그리며 생각해보자. 주어진 단어 s를 root로 시작해서, 가능한 s의 substring들을 그려나간다. 탐색 시, 만약 s의 substring이 팰린드롬이 아니라면 해당 경우에 대한 탐색을 멈춘다. (Backtracking) s = "aab" 일 경우의 test case를 살펴보자. 탐색을 진행하며 "ab" 와 "aab"의 경우, 각각의 substring이 팰린드롬이 아니므로 탐색을 중단하게 된다. 따라서 본..

Leetcode 78 문제 보기 문제 이해하기 주어진 숫자 리스트 nums의 원소들을 이용하여 생성가능한 부분 집합(the power set)을 출력하라. 이 때 가능한 집합들의 출력은 어떤 순서로 해도 상관없다. 아이디어 구상 온라인 코딩 테스트에서는 조합을 생성하는 라이브러리를 활용해서 쉽게 구하도록 하자. 파이썬의 경우, itertools를 활용하면 된다. class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] for i in range(len(nums)+1): res += list(itertools.combinations(nums, i)) return res 이제 직접 알고리즘을 구현해보자. 반복문을 이용한 i..

Leetcode 47 문제 보기 문제 이해하기 주어진 숫자 리스트 nums의 원소들을 이용하여 생성가능한 순열을 출력하라. 이 때 nums의 원소 중에는 중복된 값이 존재 가능하다. 가능한 순열들의 출력은 어떤 순서로 해도 상관없다. 아이디어 구상 본 문제는 와 유사하나 주어진 list에 중복된 값이 존재할 수 있다는 차이가 있다. 마찬가지로 온라인 코딩 테스트에서는 순열을 생성하는 라이브러리를 활용해서 쉽게 구하도록 하자. 파이썬의 경우, itertools를 활용하면 된다. 방법은 다음과 같이 가능한 순열들을 구한 후, set을 취해 중복된 값들을 제거한다. 성능도 제법 준수하다. class Solution: def permuteUnique(self, nums: List[int]) -> List[Lis..

Leetcode 46 문제 보기 문제 이해하기 주어진 숫자 리스트 nums의 원소들을 이용하여 생성가능한 순열을 출력하라. 이 때 가능한 순열들의 출력은 어떤 순서로 해도 상관없다. 아이디어 구상 반복문을 이용한 iterative한 방법, 재귀를 통한 recursive한 방법 등 다양한 방법으로 문제를 풀 수 있다. 그 중 온라인 코딩 테스트에서는 순열을 생성하는 라이브러리를 활용해서 쉽게 구하도록 하자. 파이썬의 경우, itertools를 활용하면 된다. class Solution: def permute(self, nums: List[int]) -> List[List[int]]: return list(itertools.permutations(nums)) 하지만 만약 화이트보드 인터뷰라면? Decisio..

Leetcode 79 문제 보기 문제 이해하기 m x n grid 한 칸(cell) 당 대소문자 알파벳이 한 글자씩 들어가있다. 이 때, 주어진 word를 grid에서 찾을 수 있다면 true, 찾을 수 없다면 false를 return한다. 탐색 규칙은 다음과 같다. 수직, 수평으로 탐색을 하되 중간에 방향을 틀 수도 있다. 또한 한 번 방문한 cell은 재방문할 수 없다. 아이디어 구상 손으로 문제를 푼다면 본 문제를 어떻게 풀 수 있을까? 우선 하나의 cell을 찍고 이 cell이 주어진 word의 첫 글자와 일치하는지 비교한다. 그리고 주어진 탐색 규칙에 맞게 탐색하며 과연 word가 존재할지 알아본다. 만약 word를 발견했다면 true를 return하고 탐색을 종료, 발견하지 못했다면 다음 ce..