문제는 여기에서 볼 수 있다. 고등학교 시절 자주 풀던 유형의 수학 문제와 똑같은데, m행 n열의 그리드가 있을 때 (0, 0)에 위치한 로봇이 (m-1, n-1)까지 도달하는 경로의 수를 구하는 문제이다. 풀이 1 보자마자 수험생 시절 지긋지긋하게 풀었던 수학 문제와 똑같아서 바로 공식을 적용해서 풀어봤다. m행 n열의 행렬이 있을 때, 유니크한 경로의 수를 구하는 공식은 Combination을 이용하는 것이다. 보통 (m+n-2)C(n-1) 공식으로 쉽게 구할 수 있다. 내가 수험생 시절 다녔던 수학 학원 원장님이 정말 천재여서 이러한 특정 유형의 문제에서의 공식들을 굉장히 매끄럽게 유도하고 알려주셨었다. 하고 싶은 말은 위 공식의 원리는 잘 기억이 안 남. 하여튼 완성된 내 코드는 아래와 같으며 나..
Medium
문제는 여기서 볼 수 있다. 특별한 알고리즘 기법이 필요한 문제는 아니다. 내 풀이 바로 코드 먼저 보자. class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if len(intervals) == 1: return intervals result = [] intervals.sort(key = lambda x: x[0]) leftIdx, rightIdx = 0, 1 tempElement = intervals[leftIdx] while rightIdx < len(intervals): if tempElement[1] < intervals[rightIdx][0]: result.append(tempElement) leftId..
문제는 여기서 볼 수 있다. Dynamic Programming을 사용하도록 만든 문제인데, Solution 작성을 정말 잘 해놨다. 이 글은 해당 Solution을 한글로 풀어 작성했으며, Solution 페이지에는 Java 코드만 있기 때문에 참고하여 Python 코드를 작성했다. 문제 입력 값으로 음수가 아닌 정수로 구성된 nums 라는 배열이 들어온다. 문제에서 요구하는 것은, 배열의 가장 첫 번째 인덱스부터 시작하여 배열의 가장 끝 인덱스까지 도달할 수 있는지의 여부를 return 하면 된다. 얼마만큼의 인덱스를 이동하는 지에 대한 것은, 최대 현재 위치한 인덱스의 원소만큼 오른쪽으로 인덱스를 움직일 수 있다. 예를 들어, [2, 3, 1, 1, 4]라는 배열이 있을 때, 0번째 인덱스(2)에서..
문제는 여기에서 볼 수 있다. 문제 일단 Anagram(아나그램)이 무엇인지 알아야 한다. 어떠한 단어나 구(phrase)를 이루고 있는 글자(알파벳)를 정확히 한 번씩만 사용해서 만든 다른 단어나 구를 아나그램이라고 한다. 예를 들면, "eat"으로는 "tea", 혹은 "tree"로는 "reet"와 같은 아나그램을 만들 수 있다. 이 문제에서는 여러 문자열을 담은 리스트가 입력으로 주어지고 그 문자열들을 아나그램끼리 모아서 return 하면 된다. 풀이 첫 번째 방법 처음에는 입력받은 리스트의 원소를 순회하며 각 원소를 sorting 하고 해당 값을 Dictionay의 key 값으로 사용하여 value에는 리스트의 원소를 넣을 생각이었지만, 시간 복잡도가 꽤 걸릴 것 같아 시도하지 않았다. 그런데 아무..
문제는 여기에서 볼 수 있다. 역시 과거에 풀었던 문제인데, 당시에는 혼자 못 풀었지만 이번에는 용케 혼자 풀었다. 문제 설명 N x N 모양의 matrix가 있고, 각 칸에는 숫자가 채워져 있다. 이를 시계 방향으로 90도 돌렸을 때 나타나는 matrix를 return하면 되는데, 문제에서 주어지는 2차원 배열 말고 다른 2차원 배열을 선언하면 안 된다는 조건이 있다. 즉, 주어진 matrix 배열만 이용하라는 뜻. 해결 과정 1차 시도 처음에는 각 칸의 인덱스를 다 적고 결과적으로 return 해야 하는 matrix에 맞추어 바뀌는 인덱스를 또 적어봤다. 예를 들면, (0, 0)의 숫자는 (0, 2)로, (0, 1)의 숫자는 (1, 2)로, (0, 2)의 숫자는 (2, 2)로 가야 하는 것처럼 00 ..
글 제목에서부터 알 수 있듯이, 순열을 구하는 문제이다. 자세한 내용은 여기에서 볼 수 있다. 풀이 방법은 총 두 가지를 소개할 예정이다. 하나는 DFS, 다른 하나는 반복문을 사용한 방법이다. 첫 번째 방법 - DFS 아마 많이들 생각할 방법일 것 같다. 순열을 만들 숫자 N개를 담은 리스트를 nums이라 했을 때, N!개의 원소를 담은 리스트를 최종 리턴해야 하니까 말이다. 코드는 Discuss의 글에서 찾았고, 아래와 같다. def permute(self, nums): res = [] self.dfs(nums, [], res) return res def dfs(self, nums, path, res): if not nums: res.append(path) for i in range(len(nums)..
문제는 여기에서 볼 수 있다. 읽어보면 굉장히 간단한 문제임을 알 수 있지만, 생각보다 빠르게 실행되는 코드를 작성하기 어렵다. 문제에서는 O(log n)으로 구현해보길 권장하고 있다. 내 풀이 O(log n) 보자마자, 'Two-Pointer 문제인가?' 생각이 들었다. 그래서 아래와 같이 구현해봤다. def searchRange(self, nums: List[int], target: int) -> List[int]: result = [-1, -1] if not nums: return result if len(nums) == 1: if target == nums[0]: return [0, 0] else: return result left , right = 0, len(nums) - 1 while left
문제는 여기에서 볼 수 있다. 문제 설명 문제를 간략하게 설명하자면, 입력으로 들어오는 숫자 배열과 하나의 target 숫자가 있고 target 숫자가 배열 안에 존재하면 해당 target이 위치한 인덱스를, 존재하지 않으면 -1을 return 하는 문제이다. 단, 입력되는 숫자 배열에 몇 가지 조건이 있는데 1. 배열 안의 모든 숫자는 중복되지 않는다. 2. 배열 안의 모든 숫자는 오름차순이지만, 아래 3번의 규칙을 따른다. 3. 배열 안의 숫자들은 특정 숫자(pivot)를 기준으로 rotate 되었다. 예를 들면, [0, 1, 2, 3]이라는 배열은 0이라는 숫자를 기준으로 [2, 3, 0, 1]처럼 rotate 될 수 있고, 1이라는 숫자를 기준으로 [1, 2, 3, 0]처럼 rotate 될 수 있..
문제는 여기서 볼 수 있다. 간단히 설명하자면 여러 숫자가 포함되어 있는 배열이 주어지고, 해당 배열에서 세 개의 원소의 합이 0이 되는 경우의 수를 모두 찾는 것이다. 이것도 역시 예전에 풀어봤던 문제인데, 당시에는 브루트 포스로 풀어서 느린 성능을 보였다. 그리고 역시나 Discuss에서 굉장히 좋은 성능을 보이는 코드를 찾았었다. Discuss 코드를 보기 전에 스스로 풀어봤는데, 웬 걸! 그 코드와 같은 알고리즘을 생각해서 풀어냈다. 그런데 너무 코드가 길고 더러워서 블로그에는 예전에 찾았던 Discuss 코드를 남긴다. (분명 Discuss 어딘가에서 봤는데, 해당 글을 도저히 찾지 못하겠다 ㅠㅠ) 바로 코드 먼저 보자. class Solution: def threeSum(self, nums: ..
