문제는 여기서 볼 수 있다. 문제가 정말 심플하면서 Dynamic Programming(이하 DP) 방식의 기초 활용법을 느낄 수 있는 문제라 생각하여 포스팅한다. 분석 문제는 아주 간단하다. n개의 계단이 있는 꼭대기까지 도달 가능한 경우의 수를 구하는 문제다. 대신 한 번에 1개 혹은 2개의 계단을 올라갈 수 있다. 처음부터 경우의 수를 따져보면 쉽게 패턴을 발견할 수 있다. (1)은 1개의 계단을 올라가는 기호, (2)는 2개의 계단을 올라가는 기호로 사용하겠다. if n == 1: 경우의 수는 아래 딱 한 가지뿐이다. - (1) if n == 2: 경우의 수는 아래 두 가지이다. - (1) (1) - (2) if n == 3: 경우의 수는 아래 세 가지이다. - (1) (1) (1) - (1) (..
LeetCode
문제는 여기에서 볼 수 있다. 고등학교 시절 자주 풀던 유형의 수학 문제와 똑같은데, m행 n열의 그리드가 있을 때 (0, 0)에 위치한 로봇이 (m-1, n-1)까지 도달하는 경로의 수를 구하는 문제이다. 풀이 1 보자마자 수험생 시절 지긋지긋하게 풀었던 수학 문제와 똑같아서 바로 공식을 적용해서 풀어봤다. m행 n열의 행렬이 있을 때, 유니크한 경로의 수를 구하는 공식은 Combination을 이용하는 것이다. 보통 (m+n-2)C(n-1) 공식으로 쉽게 구할 수 있다. 내가 수험생 시절 다녔던 수학 학원 원장님이 정말 천재여서 이러한 특정 유형의 문제에서의 공식들을 굉장히 매끄럽게 유도하고 알려주셨었다. 하고 싶은 말은 위 공식의 원리는 잘 기억이 안 남. 하여튼 완성된 내 코드는 아래와 같으며 나..
문제는 여기서 볼 수 있다. 특별한 알고리즘 기법이 필요한 문제는 아니다. 내 풀이 바로 코드 먼저 보자. 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)에서..
Easy 난이도라 만만하게 봤다가 혼났다. 딱 이런 부류의 문제를 위한 알고리즘이 있더라. 문제는 여기서 볼 수 있다. 문제 입력 값으로는 nums라는 배열이 들어오고, 배열 안에는 최소 하나의 정수가 존재한다. 배열 원소들 중 연속되는 subarray의 합이 최대가 되는 것을 찾아 return 해야 한다. 예를 들어, 입력값으로 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 들어오면 subarray 중 [4, -1, 2, 1]의 합이 6으로 합이 가장 크기 때문에 6을 return 하면 된다. 편의를 위해 배열의 길이는 N이라 가정한다. 해결 방법 - (1) Brute Force 누구나 쉽게 생각할 수 있는. 흔히 노가다라고 부르는 방법이다. 너무나 쉬운 방법이므로 따로 코드는 안 남긴다...
문제는 여기에서 볼 수 있다. 문제 일단 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)..
거의 한 달만에 포스팅하는 알고리즘 코딩 글이다. 바빴기도 하지만, 나태해진 이유도 있는 것 같다. 이 문제는 Solution이 있는 문젠데, 개인적으로 좋은 문제라고 생각되어서 Solution에 있는 풀이 중 한 방법에 대해 작성해봤다. 문제는 여기에서 볼 수 있다. 문제 문제 설명에 나오는 그림만 봐도 어떤 문제인지 알 수 있다. N개의 기둥들의 높이가 담긴 배열이 주어질 때, 하늘에서 비가 내린다고 가정하면 얼마나 많은 양의 물이 기둥들 사이에 갇히는 지에 대한 문제이다. 풀이 사실 이 문제도 두 번째 풀어보는 것인데, 두 번의 풀이 모두 Brute Force로 해결하려 했었다. 하지만, Solution만 봐도 Dynamic Programming(DP)나 Stack을 이용한 풀이 등 다양한 풀이가 ..
