[LeetCode] Word Search
문제링크 문제 설명 Given 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 o...
[LeetCode] Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Example 3:
Input: m = 7, n = 3
Output: 28
Example 4:
Input: m = 3, n = 3
Output: 6
Sol
맵의 size가 주어지고 로봇을 Finish로 최단거리로 옮길 수 있는 경우의 수를 구하는 문제입니다.
Example 1 의 m=3, n=7 인 경우,
결국 Finish에 도달하기 위해 ↓(down) 2번, →(right) 6번이 필요합니다.
즉, 이 문제는 [↓, ↓, →, →, →, →, →, →] 를 배치하는 ‘경우의 수’ 문제로 볼 수 있습니다.
중복이 있는 배치 경우의 수 풀이는 다음과 같습니다.
그럼 이제, m과 n에 대해 일반해를 구할 수 있습니다.
Code
import math
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return int(math.factorial(m+n-2)/(math.factorial(m-1) * math.factorial(n-1)))
math 라이브러리의 factorial을 활용했습니다.
2021
[LeetCode] Letter Combinations of a Phone Number
문제링크 문제 설명 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answe...
[프로그래머스] 기지국 설치
문제링크 문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기...
[백준] 괄호 제거
문제링크 괄호 제거 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 2016 680 ...
[LeetCode] Longest Palindromic Substring
문제링크 문제 설명 Given a string s, return the longest palindromic substring in s. Example 1: Input: s = "babad" Output: "bab" Note: "aba" is also a valid ans...
[프로그래머스] 거리두기 확인하기
문제링크 문제 설명 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5...
[프로그래머스] 불량 사용자
문제링크 문제 설명 개발팀 내에서 이벤트 개발을 담당하고 있는 “무지”는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자...
[프로그래머스] 보석쇼핑
문제링크
[프로그래머스] 문자열 압축
문제링크 문제 설명 데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되...
[LeetCode] Container With Most Water
문제링크 Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpo...
[LeetCode] Trapping Rain Water
문제링크 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Exam...
[LeetCode] Median of Two Sorted Arrays
문제링크 Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time c...
[LeetCode] First Missing Positive
문제링크 Given an unsorted integer array nums, find the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses co...
[백준] 나무 자르기
문제링크 나무 자르기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 72052 20773 ...
[프로그래머스] 광고삽입
문제링크 문제 설명 카카오TV에서 유명한 크리에이터로 활동 중인 죠르디는 환경 단체로부터 자신의 가장 인기있는 동영상에 지구온난화의 심각성을 알리기 위한 공익광고를 넣어 달라는 요청을 받았습니다. 평소에 환경 문제에 관심을 가지고 있던 “죠르디”는 요청을 받아들였고 광고효과...
[LeetCode] Climbing Stairs
문제링크 Easy You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you ...
[프로그래머스] 거스름돈
문제링크 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 ...
[LeetCode] Unique Paths
문제링크 A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any p...
[LeetCode] 3Sum
문제링크 Medium Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + ...