LeetCode 2 Add Two Numbers 풀이: 연결 리스트로 세로 덧셈 구현
역순 숫자 연결 리스트는 머리부터 읽는 순서가 세로 덧셈 순서와 같다. 길이가 다른 두 리스트와 마지막 올림까지 한 번의 순회로 처리한다.
#LeetCode
프로그래머스 문제 중 LeetCode 분류에 해당하는 풀이를 다룬다. 현재 42개의 풀이가 있다.
LeetCode 121 Best Time to Buy and Sell Stock 풀이: 최저가를 유지하는 그리디
LeetCode 121 Best Time to Buy and Sell Stock을 한 번 훑으며 최저 매수가와 최대 이익을 갱신한다. 매수일이 매도일보다 앞서야 하는 조건을 지키면서 O(n) 시간과 O(1) 공간에 푸는 방법을 설명한다.
LeetCode 704 Binary Search 풀이: 정렬 배열 이분 탐색
LeetCode 704 Binary Search를 정렬된 배열에서 이분 탐색으로 푼다. 닫힌 구간의 불변식과 경계 갱신을 확인하고, O(log n) 시간과 O(1) 공간으로 목표값의 인덱스를 찾는다.
LeetCode 853 Car Fleet 풀이: 도착 시간을 비교하는 그리디
목적지에 가까운 차부터 도착 시간을 계산해 앞 차와 합쳐지는지 판별한다. 위치순 정렬과 도착 시간의 단조성을 이용해 O(n log n)에 플릿 수를 구한다.
LeetCode 70 Climbing Stairs 풀이: 1차원 동적 계획법
LeetCode 70 Climbing Stairs에서 마지막 이동이 한 칸인지 두 칸인지 나눠 점화식을 세운다. 피보나치 형태의 상태 전이를 이용해 O(1) 공간으로 계단 오르는 방법의 수를 구한다.
LeetCode 133 Clone Graph 풀이: 방문 매핑을 사용하는 그래프 DFS
LeetCode 133 Clone Graph를 원본 노드와 복제 노드의 매핑을 이용한 DFS로 푼다. 복제 노드를 이웃 탐색 전에 저장해 순환을 처리하고 독립된 그래프를 만드는 과정을 다룬다.
LeetCode 322 Coin Change 풀이: 최소 동전 수를 구하는 동적 계획법
LeetCode 322 Coin Change를 금액별 최소 동전 수를 저장하는 상향식 동적 계획법으로 푼다. 그리디가 실패하는 이유와 만들 수 없는 금액의 처리를 설명한다.
LeetCode 39 Combination Sum 풀이: 중복 없는 백트래킹 조합 탐색
LeetCode 39 Combination Sum에서 후보를 반복해서 고르는 백트래킹을 살펴본다. 현재 인덱스를 유지해 순서만 다른 중복 조합을 막고, 정렬된 후보로 탐색을 가지친다.
LeetCode 11 Container With Most Water 풀이: 짧은 쪽을 이동하는 투 포인터
LeetCode 11 Container With Most Water를 양끝 포인터로 푼다. 짧은 쪽의 선을 옮겨야 넓이가 더 커질 가능성이 생기는 이유와 O(n) 풀이를 설명한다.
LeetCode 217 Contains Duplicate 풀이: 해시 집합으로 중복 검사
LeetCode 217 Contains Duplicate에서 이미 확인한 값을 해시 집합에 기록해 중복을 찾는다. 정렬 없이 평균 O(n) 시간, O(n) 공간으로 판정하는 방법을 소개한다.
LeetCode 739 Daily Temperatures 풀이: 단조 스택으로 다음 따뜻한 날 찾기
LeetCode 739 Daily Temperatures에서 더 따뜻한 날을 기다리는 인덱스를 단조 스택에 둔다. 현재 온도가 높아질 때 답이 확정되는 날짜들을 처리해 O(n)에 결과를 구한다.
LeetCode 2013 Detect Squares 풀이: 좌표 빈도 해시
LeetCode 2013 Detect Squares에서 좌표별 점의 개수를 중첩 해시에 저장한다. 쿼리 점과 대각선을 이루는 후보와 중복 점의 빈도를 이용해 축에 평행한 정사각형 수를 센다.
LeetCode 287 Find the Duplicate Number 풀이: 플로이드 순환 탐지
LeetCode 287 Find the Duplicate Number에서 배열 값을 다음 인덱스로 해석해 플로이드 순환 탐지를 적용한다. 배열을 바꾸지 않고 O(1) 추가 공간으로 중복 값을 찾는다.
LeetCode 22 Generate Parentheses 풀이: 유효한 접두사만 만드는 백트래킹
닫는 괄호가 여는 괄호 수를 넘지 않는다는 접두 불변식으로 잘못된 문자열 가지를 미리 자른다. n쌍의 괄호 조합만 한 번씩 생성하는 백트래킹을 설명한다.
LeetCode 49 Group Anagrams 풀이: 문자 빈도 해시로 애너그램 그룹화
LeetCode 49 Group Anagrams에서 각 단어의 문자 빈도를 튜플 키로 바꿔 애너그램을 묶는다. 정렬 없이 O(mn) 시간에 그룹을 만드는 방법을 살펴본다.
LeetCode 198 House Robber 풀이: 두 상태를 유지하는 동적 계획법
LeetCode 198 House Robber에서 이웃한 집을 함께 선택할 수 없다는 조건으로 최대 금액을 계산한다. 직전 두 상태만 유지하는 동적 계획법으로 공간을 O(1)로 줄인다.
LeetCode 875 Koko Eating Bananas 풀이: 가능 여부 판정 이분 탐색
LeetCode 875 Koko Eating Bananas에서 주어진 속도로 제한 시간 안에 먹을 수 있는지 판정한다. 이분 탐색으로 필요한 최소 시간당 섭취량을 찾는다.
LeetCode 703 Kth Largest Element in a Stream 풀이: 크기 k 최소 힙
LeetCode 703 Kth Largest Element in a Stream에서 상위 k개만 최소 힙에 유지한다. 새 값이 들어오면 힙 크기를 조절해 k번째 큰 값을 O(log k)에 확인한다.
LeetCode 141 Linked List Cycle 풀이: 플로이드의 순환 탐지 알고리즘
LeetCode 141 Linked List Cycle에서 느린 포인터와 빠른 포인터가 만나는지 확인한다. 플로이드 순환 탐지로 O(1) 추가 공간에 연결 리스트의 순환을 판별한다.
LeetCode 104 Maximum Depth of Binary Tree 풀이: 반복형 DFS
LeetCode 104 Maximum Depth of Binary Tree를 스택 기반 반복형 DFS로 푼다. 빈 트리와 편향 트리의 깊이를 처리하고 최대 깊이를 계산한다.
LeetCode 23 Merge k Sorted Lists 풀이: 최소 힙으로 k개 연결 리스트 병합
LeetCode 23 Merge k Sorted Lists에서 각 리스트의 현재 노드만 최소 힙에 둔다. 최솟값을 꺼내고 그 리스트의 다음 노드를 추가해 O(N log k)에 정렬 목록을 병합한다.
LeetCode 21 Merge Two Sorted Lists 풀이: 더미 노드와 두 포인터 병합
LeetCode 21 Merge Two Sorted Lists에서 두 리스트의 현재 노드 중 작은 쪽을 차례로 연결한다. 더미 노드로 시작 예외를 줄이고 남은 노드를 이어 붙이는 반복형 풀이를 다룬다.
LeetCode 155 Min Stack 풀이: 보조 스택으로 최솟값 O(1) 조회
LeetCode 155 Min Stack을 값 스택과 최솟값 보조 스택으로 구현한다. 중복된 최솟값도 처리하면서 push, pop, top, getMin을 O(1)에 수행한다.
LeetCode 567 Permutation in String 풀이: 문자 빈도 슬라이딩 윈도우
LeetCode 567 Permutation in String에서 s1과 같은 길이의 창을 움직이며 26개 문자 빈도를 비교한다. 나가고 들어오는 문자만 갱신해 O(n) 시간과 O(1) 공간에 순열 부분 문자열을 찾는다.
LeetCode 46 Permutations 풀이: 사용 여부를 관리하는 백트래킹
LeetCode 46 Permutations에서 사용하지 않은 원소를 하나씩 고르는 백트래킹을 다룬다. 선택을 되돌리며 모든 순서를 중복 없이 생성한다.
LeetCode 238 Product of Array Except Self 풀이: 접두사·접미사 곱 누적
LeetCode 238 Product of Array Except Self에서 나눗셈 없이 접두사 곱과 접미사 곱을 결합한다. 결과 배열을 재사용해 0이 포함된 입력도 O(n) 시간과 O(1) 추가 공간에 처리한다.
LeetCode 143 Reorder List 풀이: 연결 리스트 분할·역순·병합
LeetCode 143 Reorder List를 빠른·느린 포인터로 나누고, 뒤쪽 리스트를 뒤집어 두 부분을 번갈아 연결한다. 노드 값은 바꾸지 않고 O(1) 추가 공간에 재배치하는 과정을 설명한다.
LeetCode 206 Reverse Linked List 풀이: 포인터 방향을 뒤집는 반복문
LeetCode 206 Reverse Linked List에서 각 노드의 next를 이전 노드로 바꾼다. 다음 노드를 먼저 저장해 연결을 잃지 않고 O(n) 시간과 O(1) 공간에 리스트를 뒤집는다.
LeetCode 100 Same Tree 풀이: 트리 동시 순회
LeetCode 100 Same Tree에서 두 트리를 동시에 DFS로 순회하며 각 위치의 구조와 값을 비교한다. 빈 노드와 값 불일치의 처리 기준을 살펴본다.
LeetCode 74 Search a 2D Matrix 풀이: 2차원 배열을 평탄화한 이분 탐색
LeetCode 74 Search a 2D Matrix에서 행렬을 하나의 정렬된 배열처럼 보고 이분 탐색한다. 가상 1차원 인덱스를 행·열 좌표로 바꿔 O(log(mn)) 시간과 O(1) 공간에 target을 찾는다.
LeetCode 572 Subtree of Another Tree 풀이: 이진 트리 DFS와 구조 비교
LeetCode 572 Subtree of Another Tree에서 root의 각 노드를 시작점으로 삼아 subRoot와 구조·값을 비교한다. 부분 트리 탐색과 트리 동일성 검사를 나눠 구현한다.
LeetCode 130 Surrounded Regions 풀이: 경계 연결 영역을 보존하는 BFS
LeetCode 130 Surrounded Regions에서 가장자리의 O와 연결된 영역을 BFS로 표시하고, 남은 O를 X로 바꾼다. 격자를 제자리에서 수정해 O(mn) 시간에 처리한다.
LeetCode 981 Time Based Key-Value Store 풀이: 키별 시간 배열과 이분 탐색
LeetCode 981 Time Based Key-Value Store에서 키별 timestamp 이력을 저장하고, 조회 시각 이하의 가장 최근 기록을 이분 탐색으로 찾는다. set은 평균 O(1), 키별 기록이 k개일 때 get은 O(log k)다.
LeetCode 347 Top K Frequent Elements 풀이: 빈도 버킷 정렬
LeetCode 347 Top K Frequent Elements에서 해시로 빈도를 세고 빈도별 버킷에 값을 모은다. 비교 정렬이나 힙 없이 O(n) 시간에 상위 k개 원소를 찾는다.
LeetCode 167 Two Sum II 풀이: 정렬 배열 양끝 투 포인터
LeetCode 167 Two Sum II에서 정렬된 배열의 양끝 포인터를 움직여 target을 찾는다. 합의 크기에 따라 후보를 줄여 O(n) 시간과 O(1) 공간에 1-based 인덱스를 반환한다.
LeetCode 62 Unique Paths 풀이: 격자 경로 동적 계획법
LeetCode 62 Unique Paths에서 각 칸에 도착하는 경로 수를 누적하는 동적 계획법을 적용한다. 한 행의 값만 유지해 O(n) 공간으로 최적화한다.
LeetCode 242 Valid Anagram 풀이: 문자 빈도 배열 비교
LeetCode 242 Valid Anagram에서 한 빈도 배열에 첫 문자열은 더하고 둘째 문자열은 뺀다. 소문자 영어 조건을 이용해 정렬 없이 O(n) 시간, O(1) 공간에 판정한다.
LeetCode 125 Valid Palindrome 풀이: 양끝 투 포인터 문자열 판정
LeetCode 125 Valid Palindrome에서 양끝 포인터로 문자를 비교하며 특수문자는 건너뛴다. 대소문자를 무시하고 숫자를 포함하는 조건을 한 번의 순회로 처리한다.
LeetCode 20 Valid Parentheses 풀이: 괄호 짝과 순서를 확인하는 스택
LeetCode 20 Valid Parentheses에서 여는 괄호를 스택에 쌓고 닫는 괄호의 짝과 순서를 확인한다. 한 번 순회해 O(n) 시간과 O(n) 공간에 중첩 구조를 검증한다.
LeetCode 36 Valid Sudoku 풀이: 행·열·박스 해시 검증
LeetCode 36 Valid Sudoku에서 한 번의 격자 순회로 행·열·3×3 박스별 중복을 검사한다. 박스 인덱스를 계산해 해시 집합으로 숫자 충돌을 판별한다.
LeetCode 139 Word Break 풀이: 문자열 분할을 확인하는 동적 계획법
LeetCode 139 Word Break에서 각 접두사를 사전 단어로 만들 수 있는지 동적 계획법으로 판정한다. 상태 정의와 set 조회, 문자열 슬라이싱 비용을 살펴본다.
LeetCode 79 Word Search 풀이: 방문 복원 백트래킹 DFS
LeetCode 79 Word Search에서 모든 시작점부터 DFS로 단어를 찾고 방문 상태를 되돌린다. 상하좌우 이동과 경로 내 셀 재사용 금지를 백트래킹으로 처리한다.