LeetCode 2 Add Two Numbers 풀이: 연결 리스트로 세로 덧셈 구현
역순 숫자 연결 리스트는 머리부터 읽는 순서가 세로 덧셈 순서와 같다. 길이가 다른 두 리스트와 마지막 올림까지 한 번의 순회로 처리한다.
#난이도 3
프로그래머스 문제 중 난이도 3 분류에 해당하는 풀이를 다룬다. 현재 50개의 풀이가 있다.
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 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 198 House Robber 풀이: 두 상태를 유지하는 동적 계획법
LeetCode 198 House Robber에서 이웃한 집을 함께 선택할 수 없다는 조건으로 최대 금액을 계산한다. 직전 두 상태만 유지하는 동적 계획법으로 공간을 O(1)로 줄인다.
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 143 Reorder List 풀이: 연결 리스트 분할·역순·병합
LeetCode 143 Reorder List를 빠른·느린 포인터로 나누고, 뒤쪽 리스트를 뒤집어 두 부분을 번갈아 연결한다. 노드 값은 바꾸지 않고 O(1) 추가 공간에 재배치하는 과정을 설명한다.
LeetCode 100 Same Tree 풀이: 트리 동시 순회
LeetCode 100 Same Tree에서 두 트리를 동시에 DFS로 순회하며 각 위치의 구조와 값을 비교한다. 빈 노드와 값 불일치의 처리 기준을 살펴본다.
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 62 Unique Paths 풀이: 격자 경로 동적 계획법
LeetCode 62 Unique Paths에서 각 칸에 도착하는 경로 수를 누적하는 동적 계획법을 적용한다. 한 행의 값만 유지해 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로 단어를 찾고 방문 상태를 되돌린다. 상하좌우 이동과 경로 내 셀 재사용 금지를 백트래킹으로 처리한다.
프로그래머스 불량 사용자 풀이: 비트마스크 DFS 매칭
프로그래머스 불량 사용자에서 패턴별 후보를 만들고, 한 사용자를 중복 선택하지 않도록 DFS로 배정한다. 비트마스크 집합으로 순서만 다른 조합을 하나로 센다.
프로그래머스 베스트앨범 풀이: 해시 집계와 우선순위 정렬
프로그래머스 베스트앨범에서 장르별 재생 합계를 구하고, 장르 안의 곡을 재생 수와 고유 번호로 정렬한다. 장르마다 상위 두 곡을 고르는 과정을 설명한다.
프로그래머스 섬 연결하기 풀이: 크루스칼 최소 신장 트리
프로그래머스 섬 연결하기에서 비용순으로 다리를 살펴보고 Union-Find로 사이클을 막는다. 서로 다른 연결 요소를 잇는 간선만 골라 최소 신장 트리를 만든다.
프로그래머스 디스크 컨트롤러 풀이: 대기 작업 최소 힙 스케줄링
프로그래머스 디스크 컨트롤러에서 현재 대기 중인 작업 가운데 소요 시간이 가장 짧은 작업을 최소 힙으로 고른다. 요청 시각과 유휴 시간, 평균 반환 시간을 함께 다룬다.
프로그래머스 이중우선순위큐 풀이: 두 힙과 지연 삭제
프로그래머스 이중우선순위큐에서 최소 힙과 음수로 저장한 최대 힙을 함께 사용한다. 값별 개수로 지연 삭제를 처리해 두 힙을 동기화한다.
프로그래머스 가장 먼 노드 풀이: 인접 리스트 BFS
1번 노드에서 BFS로 모든 노드까지의 최단 간선 거리를 구한다. 최댓거리와 같은 거리를 가진 노드 수를 세는 풀이를 설명한다.
프로그래머스 힌트 스테이지 풀이: 비트마스크 완전탐색
프로그래머스 힌트 스테이지에서 구매할 번들의 부분집합을 비트마스크로 탐색한다. 각 조합의 힌트 수와 비용을 계산해 최소 비용을 찾는다.
프로그래머스 호텔 방 배정 풀이: 연속 점유 구간을 합치는 유니온 파인드
최대 10^12개의 방을 배열로 만들지 않고, 배정된 방만 Union-Find로 관리한다. 각 연속 점유 구간의 오른쪽 끝을 저장해 다음 빈 방을 찾는다.
프로그래머스 도둑질 풀이: 원형 집을 두 구간으로 나누는 동적 계획법
원형 배치 때문에 양 끝집을 동시에 고를 수 없는 조건을 두 선형 DP로 나눈다. 반열린 구간과 이전 두 상태만 사용해 백만 채 입력도 추가 배열 없이 처리한다.
프로그래머스 중요한 단어를 스포 방지 풀이: 구간 처리와 해시
프로그래머스 '중요한 단어를 스포 방지'에서 단어와 스포일러 구간의 겹침을 찾고, 해시 집합으로 일반 영역의 단어와 중복을 처리한다.
프로그래머스 보석 쇼핑 풀이: 해시 슬라이딩 윈도우
프로그래머스 보석 쇼핑에서 슬라이딩 윈도우로 현재 구간의 보석 종류와 개수를 관리한다. 모든 종류를 포함하는 가장 짧은 구간과 시작 위치 조건을 찾는다.
프로그래머스 조이스틱 풀이: 알파벳 변경과 커서 이동 그리디
프로그래머스 조이스틱에서 알파벳 변경 비용과 좌우 이동 비용을 나눠 계산한다. 연속된 A 구간을 건너뛰는 경로까지 비교해 최소 조작 횟수를 찾는다.
프로그래머스 숫자 게임 풀이: 정렬과 그리디 매칭
프로그래머스 숫자 게임에서 두 팀의 숫자를 정렬하고, A팀을 이길 수 있는 가장 작은 B팀 숫자를 짝짓는다. 불필요하게 큰 수를 아껴 최대 승점을 만든다.
프로그래머스 퍼즐 게임 챌린지 풀이: 이분 탐색으로 최소 숙련도 찾기
프로그래머스 퍼즐 게임 챌린지에서 숙련도별 총 소요 시간을 판정하고 이분 탐색으로 최소 숙련도를 찾는다. 실패 횟수에 따른 시간 계산과 단조 조건을 설명한다.
프로그래머스 순위 풀이: 승패 전이 관계를 확정하는 플로이드-워셜
프로그래머스 순위에서 경기 결과를 방향 그래프로 나타내고 플로이드-워셜로 간접 승패 관계를 구한다. 승리·패배 수의 합으로 순위를 확정할 수 있는 선수를 찾는다.
프로그래머스 비밀 코드 해독 풀이: 조합 완전탐색과 교집합
프로그래머스 비밀 코드 해독에서 1부터 n까지 중 다섯 숫자를 고르는 조합을 탐색한다. 각 시도와 비밀 코드의 교집합 크기를 비교해 가능한 비밀 코드를 센다.
프로그래머스 기지국 설치 풀이: 빈 구간 길이 계산 그리디
프로그래머스 기지국 설치에서 기존 기지국 사이의 빈 구간만 살펴보고, 한 기지국의 전파 범위로 나누어 필요한 수를 구한다. 아파트를 전부 순회하지 않는 경계 처리와 올림 나눗셈을 설명한다.
프로그래머스 주식가격 풀이: 하락 시점을 찾는 단조 스택
프로그래머스 주식가격에서 아직 하락 시점을 만나지 않은 인덱스를 단조 스택에 보관한다. 가격이 처음 낮아질 때 지속 시간을 확정해 모든 시점을 O(n)에 처리한다.
프로그래머스 단속카메라 풀이: 종료 지점 기준 그리디
프로그래머스 단속카메라에서 차량 경로를 종료 지점 기준으로 정렬한다. 아직 감시되지 않은 경로의 끝에 카메라를 두어 필요한 대수를 최소화한다.
프로그래머스 여행경로 풀이: 사전순 DFS와 후위 경로 구성
프로그래머스 여행경로에서 출발지별 도착지를 역순 정렬하고 스택 기반 DFS로 항공권을 모두 사용한다. 막다른 공항을 후위에 기록해 사전순 경로를 구성한다.
프로그래머스 바이러스 파이프 풀이: 파이프 순서 DFS와 감염 BFS
프로그래머스 바이러스 파이프에서 DFS로 파이프 배치 순서를 정하고 BFS로 같은 종류의 파이프를 따라 감염을 퍼뜨린다.