Brute Force(3)
-
Leetcode 51. N-Queens - Python (cf. 백준 9663)
Leetcode 51 문제 보기 문제 이해하기 n X n 체스판 위에 n개의 queen을 배치하려한다. (1
2022.03.24 -
Leetcode 17. Letter Combinations of a Phone Number - Python
Leetcode 17 문제 보기 문제 이해하기 스마트폰이 출현하기 이전, 휴대폰의 자판은 위 그림과 같았다. 전화번호의 각 번호는 특정 알파벳들과 매칭이 된다. 어떤 번호가 주어진다면, 해당 번호를 이용해 출력 가능한 단어들을 구하라. 번호는 2~9로 이루어져 있으며, 번호의 길이는 최소 0부터 최대 4까지 가능하다. 아이디어 구상 Decision Tree를 그리며 생각해보자. digits = "23"인 test case를 살펴보자. 이 때 트리의 각 level은 주어진 digits의 각 숫자를 탐색하는 경우에 해당된다. 모든 조합을 찾아야하므로, Brute Force하게 탐색을 해야한다. DFS를 활용해 가능한 알파벳 조합들을 하나씩 얻어 결과 리스트에 넣고, 최종적으로 정답을 출력하면 되겠다. 이 때..
2022.03.22 -
Leetcode 79. Word Search - Python (cf. 백준 15705)
Leetcode 79 문제 보기 문제 이해하기 m x n grid 한 칸(cell) 당 대소문자 알파벳이 한 글자씩 들어가있다. 이 때, 주어진 word를 grid에서 찾을 수 있다면 true, 찾을 수 없다면 false를 return한다. 탐색 규칙은 다음과 같다. 수직, 수평으로 탐색을 하되 중간에 방향을 틀 수도 있다. 또한 한 번 방문한 cell은 재방문할 수 없다. 아이디어 구상 손으로 문제를 푼다면 본 문제를 어떻게 풀 수 있을까? 우선 하나의 cell을 찍고 이 cell이 주어진 word의 첫 글자와 일치하는지 비교한다. 그리고 주어진 탐색 규칙에 맞게 탐색하며 과연 word가 존재할지 알아본다. 만약 word를 발견했다면 true를 return하고 탐색을 종료, 발견하지 못했다면 다음 ce..
2022.03.17