Leetcode 51 문제 보기 문제 이해하기 n X n 체스판 위에 n개의 queen을 배치하려한다. (1

Leetcode 1849 문제 보기 문제 이해하기 0 ~ 9까지의 숫자로 이루어진 문자열 s를 2개 이상의 substring으로 나눠보자. 이 때 각 substring들이 바로 이전의 substring에 비해 1이 작은 수로 이루어져 있다면, 즉 "substring = previous_substring - 1"일 경우, true를 return하는 프로그램을 작성하라. 각각의 substring은 빈 문자열이서는 안되며, substring은 1개 이상, 20개 이하의 숫자로 이루어져있다. 또한 1 ~ 9 이전에 등장하는 "0"은 무시해도 된다. 즉, "05" 은 숫자 5다. 아이디어 구상 Decision Tree를 그리며 생각해보자. s = "050043"인 test case를 살펴보자. 적어도 한 번은 s..

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..