리트코드

[python] 재귀 알고리즘 - 최대공약수 GCD - 유클리드 호제법

안녕하세요. 이번 포스팅은 재귀 알고리즘에 대해서 다뤄보았습니다. 재귀는 다양한 알고리즘에서 활용이 되는데요. 특히, 재귀를 모르고 지나친다면 다른 재귀에 기반하여 풀 수 있는 고등 알고리즘에 대해 알 수 없게 된다는 점이 있습니다.  재귀로 쉽게 풀 수 있는 대표적인 알고리즘 중 하나인 최대공약수 찾는 알고리즘에 대해서 다뤄보겠습니다. 예를 들어 9 x 24 인 직사각형이 있다고 가정하겠습니다. 쉽게 범용적으로 풀 수 있는 방법 중 하나는 다음처럼 정사각형으로 분할이 될 때까지 쪼개는 방법이 있는데요. 로직 자체는 간다합니다.위 첫번째 그림처럼 9 x 24 크기의 직사각형에서 짧은 변의 길이인 9를 한 변으로 하는 정사각형으로 나눠줍니다. 그러면 2개의 9x9 정사각형이 만들어지고 하나의 9 x 6 크..

[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. (링크: https://leetcode.com/problems/trapping-rain-water/description/) 문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다. 이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다. 하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다. 풀이: 투 포인터 활용 투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..