알고리즘/리트코드

📌 LeetCode [424]: Longest Repeating Character Replacement🔗 문제 링크문제 설명 📄문자열 s와 정수 k가 주어졌습니다.k번까지 문자를 변경할 수 있을 때, 동일한 문자를 포함하는 가장 긴 부분 문자열의 길이를 반환해야 합니다.변경은 문자열 s의 어떤 문자를 선택하여 다른 대문자 영어 알파벳으로 교체하는 작업입니다.문제 접근 방식 📋슬라이딩 윈도우 활용:문자열의 두 포인터 l과 r을 사용해 윈도우를 확장하거나 축소합니다.부분 문자열 길이와 문자 빈도를 유지하면서 조건을 만족하도록 윈도우를 조정합니다.조건 확인:윈도우 내에서 최빈 문자 외의 문자 개수가 k를 초과하면 윈도우의 왼쪽 포인터(l)를 이동시킵니다.최적화:최빈 문자 개수(max_freq)를 슬라이..

📌 LeetCode [2570]: Merge Two 2D Arrays by Summing Values🔗 문제 링크문제 설명 📄두 개의 2D 배열 nums1과 nums2가 주어졌습니다.각 배열은 [id, value]의 쌍으로 이루어져 있으며, 정렬된 상태입니다.동일한 id 값을 가진 value를 더한 후, 결과를 [id, sum]의 형태로 정렬된 배열로 반환해야 합니다.문제 접근 방식 📋딕셔너리를 이용한 병합:두 배열의 모든 요소를 순회하며, 각 id를 키로 저장하고 value를 더합니다.Python의 defaultdict를 활용하여 초기화 과정을 간소화합니다.결과 생성:딕셔너리의 키를 기준으로 정렬한 후, [id, sum]의 형태로 배열을 생성합니다.시간 최적화:두 배열을 합친 후 병합하는 방식으..

📌 LeetCode [88]: Merge Sorted Array🔗 문제 링크문제 설명 📄두 개의 정렬된 배열 nums1과 nums2가 주어졌습니다.nums1의 크기는 m + n이며, 처음 m개의 요소는 유효하고 나머지는 0으로 비워져 있습니다.nums2는 크기가 n인 정렬된 배열입니다.nums1과 nums2를 병합하여 정렬된 하나의 배열로 만들어야 하며, 제자리에서(in-place) 수정해야 합니다.문제 접근 방식 📋두 포인터를 활용:배열 nums1의 끝에서부터 값을 채워 넣습니다.nums1의 유효한 요소를 가리키는 포인터 left와 nums2의 요소를 가리키는 포인터 index를 사용합니다.가장 큰 값을 뒤에서부터 채워넣으며 nums1의 공간을 채웁니다.반복 조건:index >= 0인 동안 두 ..

📌 LeetCode [21]: Merge Two Sorted Lists🔗 문제 링크문제 설명 📄두 개의 정렬된 단일 연결 리스트 list1과 list2가 주어졌을 때, 두 리스트를 병합하여 정렬된 단일 연결 리스트로 반환하는 문제입니다.새로운 리스트는 두 리스트의 노드를 재사용하여 구성해야 합니다.문제 접근 방식 📋더미 노드 사용:병합 결과를 저장할 새로운 연결 리스트의 시작점을 잡기 위해 더미 노드(answer)를 생성합니다.현재 위치를 추적하기 위해 current 포인터를 사용합니다.리스트 병합:두 리스트를 순회하며, list1.val과 list2.val을 비교합니다.작은 값을 가진 노드를 결과 리스트에 추가하고, 해당 리스트를 다음 노드로 이동시킵니다.잔여 노드 처리:두 리스트 중 하나가 먼..

📌 LeetCode [73]: Set Matrix Zeroes🔗 문제 링크문제 설명 📄2D 행렬 matrix가 주어졌을 때, 요소가 0인 위치의 행과 열 전체를 0으로 바꾸는 문제입니다.행렬을 제자리에서(in-place) 수정해야 하며, 추가적인 공간 사용을 최소화해야 합니다.문제 접근 방식 📋0 위치 기록:2중 루프를 통해 행렬을 순회하며, 값이 0인 좌표를 기록합니다.좌표는 stack에 저장하여 나중에 접근합니다.0 확장:기록된 좌표를 기준으로, 해당 좌표의 행과 열 전체를 0으로 설정합니다.각 방향(왼쪽, 오른쪽, 위, 아래)을 개별적으로 처리하며, 경계 조건을 확인합니다.제자리 수정:행렬을 직접 수정하여 공간 복잡도를 최소화합니다.Solution 💻class Solution: def..

📌 LeetCode [62]: Unique Paths🔗 문제 링크문제 설명 📄로봇이 (m \times n) 격자의 왼쪽 위에서 오른쪽 아래로 이동하려고 합니다.로봇은 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.격자에서 오른쪽 아래로 가는 데 필요한 고유 경로의 수를 반환하는 문제입니다.문제 접근 방식 📋동적 계획법(DP) 사용:DP 배열 dp[i][j]는 (i, j)까지의 고유 경로 수를 저장합니다.초기화:시작점 (dp[0][0] = 1): 시작점에서의 경로 수는 1입니다.첫 번째 행과 첫 번째 열은 각각 오른쪽/아래로만 이동 가능하므로 (dp[i][0] = 1), (dp[0][j] = 1)로 초기화됩니다.DP 점화식:각 셀 (dp[i][j])는 왼쪽에서 오는 경로와 위쪽에서 오는 경로의 합입니..

📌 LeetCode [200]: Number of Islands🔗 문제 링크문제 설명 📄2D 그리드 맵이 주어질 때, '1'(육지)로 연결된 섬의 개수를 반환하는 문제입니다. 섬은 상하좌우로 연결된 '1'들로 구성됩니다. '0'(물)은 육지를 분리합니다.문제 접근 방식 📋BFS를 사용한 탐색:그리드의 모든 셀을 순회하며, 새로운 '1'을 발견할 때마다 BFS를 시작합니다.BFS는 큐를 사용하여 인접한 모든 '1'을 탐색하고, 방문한 셀을 visited에 기록합니다.방문 기록:이미 방문한 셀은 다시 탐색하지 않도록 visited 집합을 사용하여 체크합니다.섬의 개수 계산:새로운 '1'을 발견할 때마다 섬의 개수를 증가시킵니다.Solution 💻from collections import dequec..

📌 LeetCode [3]: Longest Substring Without Repeating Characters🔗 문제 링크문제 설명 📄문자열 ( s )가 주어졌을 때, 중복되지 않은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 반환하는 문제입니다.문제 접근 방식 📋슬라이딩 윈도우와 deque 활용:중복 문자가 발견될 때까지 앞쪽 문자들을 제거하며, 중복이 없도록 유지합니다.deque는 현재 윈도우의 문자들을 저장하며, set은 중복 검사를 위해 사용합니다.반복문으로 윈도우 탐색:문자열의 각 문자를 순회하며, 중복이 발생하면 deque의 앞쪽 문자를 제거합니다.매 단계마다 현재 윈도우의 길이를 갱신합니다.최대 길이 반환:탐색이 끝난 후 최대 길이를 반환합니다.Solution 💻from col..