알고리즘/리트코드

📌 LeetCode [962]: Maximum Width Ramp🔗 https://leetcode.com/problems/maximum-width-ramp/문제 설명 📄주어진 배열 nums에서 가장 긴 Ramp를 찾아야 합니다. Ramp는 두 인덱스 (i, j)에 대해 다음 조건을 만족합니다:i nums[i] 목표는 가능한 Ramp 중 j - i를 최대화하는 값을 반환하는 것입니다.문제 접근 방식스택 빌드:배열을 왼쪽에서 오른쪽으로 순회하면서, 작아지는 값의 인덱스만 스택에 추가합니다.스택에는 Ramp의 시작점이 될 가능성이 있는 인덱스만 남습니다.스택 활용:배열을 오른쪽에서 왼쪽으로 순회하면서, 스택의 값과 비교해 Ramp를 계산합니다.스택의 값이 조건을 만족하면 길이를 계산하고, 더 이상 조건을..

📌 LeetCode [528]: Random Pick with Weight🔗 https://leetcode.com/problems/random-pick-with-weight/문제 설명 📄0부터 시작하는 양의 정수 배열 w가 주어집니다.각 w[i]는 i번째 인덱스의 가중치를 나타냅니다.pickIndex() 함수는 각 인덱스를 가중치에 비례한 확률로 무작위 선택하여 반환해야 합니다.문제 접근 방식w의 전체 합을 계산하여 각 가중치를 비율로 구합니다.각 가중치를 누적 합 형태로 저장하여 확률 구간을 만듭니다.무작위로 생성된 값이 해당 구간에 속하는 인덱스를 반환합니다.효율성을 높이기 위해 이분 탐색을 사용하여 인덱스를 찾는 방식으로 리팩토링할 수 있습니다.Solution 💻import randomfro..

📌 LeetCode [190]: Reverse Bits🔗 문제 링크문제 설명 📄32비트의 부호 없는 정수가 주어지면, 해당 정수의 비트를 뒤집은 값을 반환하세요.문제 접근 방식32비트 정수의 각 비트를 순차적으로 검사하며 뒤집는 방식으로 접근합니다.주어진 정수에서 비트를 오른쪽으로 이동시키며 최하위 비트를 추출합니다.추출된 비트를 결과 변수에 왼쪽으로 이동하여 반대로 삽입합니다.모든 비트를 처리한 후 결과를 반환합니다.Solution 💻class Solution: def reverseBits(self, n: int) -> int: result = 0 for _ in range(32): result = (result >= 1 return..

📌 LeetCode [539]: Minimum Time Difference🔗 문제 링크문제 설명 📄주어진 시간 리스트에서 두 시간 간의 차이가 가장 작은 값을 계산하세요.시간은 "HH:MM" 형식의 문자열로 제공됩니다.하루는 1440분이며, 경계를 넘어가는 시간 차이도 고려해야 합니다.문제 접근 방식 🚶시간을 분 단위로 변환:각 "HH:MM" 문자열을 분 단위의 정수로 변환합니다.정렬:시간 값을 정렬하여 인접한 시간 간의 차이를 계산합니다.최소 차이 계산:인접한 시간 간의 차이를 계산하며 최소값을 업데이트합니다.첫 번째와 마지막 시간의 차이를 하루의 경계로 연결하여 계산합니다.Solution 💻class Solution: def findMinDifference(self, timePoints..

📌 LeetCode [874]: Walking Robot Simulation🔗 문제 링크문제 설명 📄로봇이 무한한 XY 평면에서 (0, 0)에서 시작하여 북쪽을 바라보고 있다.명령과 장애물 배열이 주어졌을 때, 로봇이 이동 중 도달할 수 있는 최대 제곱 거리를 계산하라.명령:-2: 왼쪽으로 90도 회전-1: 오른쪽으로 90도 회전1 장애물: 특정 위치에 있는 장애물 좌표.문제 접근 방식 🚶방향 정의:북, 동, 남, 서 순으로 이동 벡터를 정의.회전 명령에 따라 방향 인덱스를 갱신.전진 명령:장애물이 없는 경우에만 이동.이동 중 최대 유클리드 거리 제곱 값을 갱신.장애물 처리:장애물 좌표를 set으로 변환하여 빠른 조회 가능.Solution 💻class Solution: def robotSi..

📌 LeetCode [53]: Maximum Subarray🔗 문제 링크문제 설명 📄배열에서 연속된 부분 배열의 합 중 가장 큰 값을 반환합니다.Solution 💻from typing import Listclass Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = float('-inf') current_sum = 0 for num in nums: current_sum = max(num, current_sum + num) max_sum = max(max_sum, current_sum) return max_sum시간 복잡도..

📌 LeetCode [1508]: Range Sum of Sorted Subarray Sums🔗 문제 링크문제 설명 📄주어진 배열 nums에서 모든 부분합을 계산하고, 이를 오름차순으로 정렬했을 때 left번째부터 right번째까지의 부분합의 합을 반환해야 합니다. 결과는 10**9 + 7로 나눈 나머지를 반환합니다.문제 접근 방식 🔍부분합 계산과 정렬:배열에서 모든 부분합을 계산하면 시간 복잡도는 O(n²)입니다.이후 이를 정렬하여 특정 구간만 선택하면 추가적으로 O(n² x log(n²))의 비용이 발생합니다.효율적인 부분합 계산:최소힙을 활용하여 가장 작은 부분합부터 정렬된 순서로 처리합니다.힙 연산으로 시간 복잡도를 O(n² x log(n))로 줄일 수 있습니다.Solution 💻impo..

📌 LeetCode [380]: Insert Delete GetRandom O(1)🔗 문제 링크문제 설명 📄다음의 연산을 평균적으로 O(1) 시간 복잡도로 지원하는 자료 구조를 설계하세요:insert(val) : 값을 삽입합니다. 값이 이미 존재하면 False를 반환하고, 그렇지 않으면 True를 반환합니다.remove(val) : 값을 삭제합니다. 값이 존재하지 않으면 False를 반환하고, 그렇지 않으면 True를 반환합니다.getRandom() : 자료 구조에서 임의의 값을 반환합니다. 각 값은 동일한 확률로 선택됩니다.문제 해결 접근 방법 🔍딕셔너리와 리스트를 조합하여 구현:딕셔너리는 값의 인덱스를 빠르게 접근하기 위해 사용합니다.리스트는 getRandom 연산에서 임의의 값을 O(1)로 ..