와드의 블로그

문제겹치지 않는 구간들이 시작점 기준으로 오름차순 정렬된 배열 intervals와 새로운 구간 newInterval이 주어집니다. newInterval을 intervals에 올바른 위치에 삽입하고, 겹치는 구간이 있다면 모두 병합하여 새로운 구간 배열을 반환하는 프로그램을 작성하는 문제입니다.제한사항 (Constraints)0 intervals[i].length == 20 intervals는 starti를 기준으로 오름차순 정렬되어 있습니다.newInterval.length == 20 링크: https://leetcode.com/problems/insert-interval풀이: 3단계 while문을 활용한 완벽한 구간 분리 및 병합복잡한 if문 분기 대신, 탐색 과정을 시간 순서에 따라 정확히 3단계로 ..

문제이진 탐색 트리(BST)의 루트 노드와 트리 내의 두 노드 p, q가 주어질 때, 두 노드의 최소 공통 조상(Lowest Common Ancestor, LCA)을 찾는 프로그램을 작성하는 문제입니다. 최소 공통 조상이란, 트리 내의 어떤 노드 T가 p와 q를 모두 자손으로 가지면서 가장 깊은(낮은) 위치에 있는 노드를 의미합니다. (노드 자기 자신도 자손으로 간주합니다.)입력: 이진 탐색 트리의 루트 노드 root, 탐색 대상 노드 p, q출력: 두 노드의 최소 공통 조상 노드를 반환합니다.링크: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree풀이: 이진 탐색 트리(BST)의 대소 관계 속성 활용이진 탐색 트리는..

문제2차원 정수 배열 image와 시작 좌표 sr, sc, 그리고 새로운 색상 color가 주어집니다. image는 화면의 픽셀을 나타내며 각 값은 픽셀의 색상입니다. 시작 픽셀 (sr, sc)에서 출발하여 상하좌우 4방향으로 연결되어 있으면서 시작 픽셀과 같은 색상을 가진 모든 픽셀의 색상을 새로운 색상(color)으로 변경하는 '플러드 필(Flood Fill)' 작업을 수행하는 문제입니다. 그림판의 '색 채우기' 기능과 동일하게 동작합니다.입력: 2차원 배열 image (크기 1 이상 50 이하), 시작 좌표 sr, sc, 새로운 색상 color출력: 플러드 필 작업이 완료된 2차원 배열 image링크: https://leetcode.com/problems/flood-fill풀이 1: Queue와 방..

문제주어진 이진 트리의 루트 노드(root)가 주어질 때, 이 트리의 좌우를 반전(Invert)시켜서 반환하는 프로그램을 작성하는 문제입니다. 즉, 트리에 있는 모든 노드의 왼쪽 자식과 오른쪽 자식의 위치를 서로 바꾸어야 합니다.입력: 이진 트리의 루트 노드 root (노드의 개수는 0개에서 100개 사이)출력: 좌우가 반전된 트리의 루트 노드링크: https://leetcode.com/problems/invert-binary-tree풀이: 재귀(Recursion)를 활용한 하향식 스왑(Swap)트리의 특성을 활용하여, 부모 노드에서 자식 노드로 내려가며 재귀적으로 왼쪽과 오른쪽 서브트리를 교환하는 직관적인 풀이입니다. 이전의 '두 정렬 리스트 병합' 문제에서 재귀를 사용하셨던 것과 마찬가지로, 트리의 ..

문제오름차순으로 정렬된 두 개의 연결 리스트 list1과 list2의 헤드(head)가 주어집니다. 이 두 리스트의 노드들을 엮어서 하나의 정렬된 새로운 연결 리스트로 병합하고, 그 병합된 리스트의 헤드를 반환하는 프로그램을 작성하는 문제입니다.입력: 정렬된 연결 리스트 list1, list2 (각 리스트의 노드 개수는 0개에서 50개 사이)출력: 두 리스트가 병합되어 정렬된 새로운 연결 리스트의 헤드링크: https://leetcode.com/problems/merge-two-sorted-lists풀이: 재귀(Recursion)를 활용한 직관적인 노드 연결반복문(while)과 임시 노드(dummy node)를 사용하여 연결하는 방식도 있지만, 재귀를 사용하면 코드를 훨씬 짧고 직관적으로 작성할 수 있습..

문제정수 배열 nums가 주어질 때, 연속된 부분 배열(Subarray) 중 그 합이 가장 큰 부분 배열을 찾아 그 합을 반환하는 프로그램을 작성하는 문제입니다.입력: 정수 배열 nums (1 출력: 연속된 부분 배열의 최대 합링크: https://leetcode.com/problems/maximum-subarray풀이: DP 탐색배열을 한 번 순회하면서 연속된 구간의 합을 추적합니다.상태 정의: 1차원 배열 d[i]를 i번째 원소를 마지막으로 하는 연속 부분 배열의 최대 합으로 정의합니다.초기화: 첫 번째 원소는 그 자체로 부분 배열이 되므로 d[0] = nums[0]으로 초기화하고, 전체 최댓값 ans도 d[0]으로 설정합니다.점화식 도출: i번째 원소에서 선택할 수 있는 경우는 두 가지입니다.이전까..

문제오름차순으로 정렬된 정수 배열 nums와 찾고자 하는 목표값 target이 주어집니다. 배열에서 target을 검색하여 그 인덱스를 반환하는 프로그램을 작성하는 문제입니다. 만약 배열에 target이 존재하지 않는다면 -1을 반환해야 합니다. 알고리즘은 반드시 O(log N)의 시간 복잡도로 작성되어야 합니다.입력: 오름차순 정렬된 정수 배열 nums (1 출력: target의 인덱스 (존재하지 않으면 -1)링크: https://leetcode.com/problems/binary-search풀이: 정렬된 배열에서의 O(log N) 탐색배열이 이미 오름차순으로 정렬되어 있다는 조건을 활용하여, 탐색 범위를 매번 절반으로 줄여나가는 이진 탐색(Binary Search)의 가장 정석적이고 완벽한 구현입니다..

문제두 개의 문자열 s와 t가 주어질 때, t가 s의 애너그램(Anagram)인지 판별하는 프로그램을 작성하는 문제입니다. 애너그램이란 단어나 문장의 철자 순서를 바꾸어 다른 단어나 문장으로 만드는 것을 말합니다. 즉, 두 문자열이 구성하는 알파벳의 종류와 개수가 완벽하게 동일해야 합니다.입력: 알파벳 소문자로만 이루어진 문자열 s와 t (1 출력: t가 s의 애너그램이면 true, 아니면 false 반환링크: https://leetcode.com/problems/valid-anagram풀이: 알파벳 카운팅 배열을 활용한 O(N) 최적화 탐색두 문자열을 정렬한 뒤 비교하는 방식(시간 복잡도 O(N log N)) 대신, 알파벳의 개수가 26개로 고정되어 있다는 점을 활용하여 길이가 26인 정수 배열을 사용..

문제어떤 주식의 매일의 가격을 나타내는 배열 prices가 주어집니다. prices[i]는 i번째 날의 주식 가격입니다. 주식을 단 한 번 사고 단 한 번 팔아서 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하는 문제입니다. 만약 어떤 이익도 얻을 수 없다면 0을 반환해야 합니다.입력: 주식 가격을 담은 정수 배열 prices (길이 1 이상 100,000 이하, 각 가격은 0 이상 10,000 이하)출력: 얻을 수 있는 최대 이익 (이익이 없으면 0 반환)링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock풀이: 저점 매수 및 고점 매도 (O(N) 탐색)이중 반복문을 사용하여 모든 매수/매도 타이밍을 검사하면 시간 복잡도가 O(N^2)..

문제주어진 문자열 s가 팰린드롬(앞뒤로 읽어도 똑같은 문자열)인지 판별하는 프로그램을 작성하는 문제입니다. 단, 문자열에서 영문자와 숫자만 고려하며 대소문자는 구분하지 않습니다.입력: 인쇄 가능한 ASCII 문자로 이루어진 문자열 s (1 출력: 팰린드롬이면 true, 아니면 false 반환링크: https://leetcode.com/problems/valid-palindrome풀이 1: StringBuilder를 활용한 문자열 정제 및 비교정규 표현식(Regex)에 의존하지 않고, 아스키코드(ASCII) 값을 직접 활용하여 유효한 문자만 걸러낸 뒤 한 번에 비교하는 직관적인 풀이입니다.문자열 정제 (알파벳 및 숫자 필터링):입력 문자열을 순회하며 소문자나 숫자인 경우 그대로 StringBuilder에 ..