전체 글

1. 문제 설명문제 링크: LeetCode 124 - Binary Tree Maximum Path Sum요약: 이진 트리의 노드들을 연결하는 경로 중 노드 값들의 합이 최대가 되는 경로를 찾는 문제입니다. 경로는 반드시 루트를 지날 필요가 없으며, 어느 노드에서 시작하여 어느 노드에서 끝나도 상관없지만 경로 내 노드는 중복될 수 없습니다.2. 핵심 아이디어이 문제는 트리의 각 노드를 '경로의 정점(Peak)'으로 가정하고 재귀(DFS)를 통해 상향식(Bottom-up)으로 해결합니다.독립적인 경로 vs 연장 가능한 경로:어떤 노드에서 부모 노드로 전달할 값은 '해당 노드와 왼쪽 자식 중 큰 값' 또는 '해당 노드와 오른쪽 자식 중 큰 값'이어야 합니다. (한 갈래로만 연결 가능)반면, 현재 노드를 정점으..

1. 백트래킹이란?백트래킹(Back-Tracking)은 모든 경우의 수를 탐색하는 브루트포스(Brute Force)와 유사하지만, 탐색 과정에서 '답이 될 가능성'을 실시간으로 판단한다는 점에서 차이가 있습니다.순차적 생성: 답을 한 번에 완성하는 것이 아니라, 여러 단계(Step)에 걸쳐 순차적으로 답을 만들어 나갑니다.가지치기(Pruning): 현재 단계에서 다음 단계로 넘어갈 때, 해당 경로가 답으로 갈 수 없다고 판단되면 더 이상 탐색하지 않고 즉시 뒤로 돌아갑니다.효율성: 가지치기를 통해 오답 경로에 소모되는 리소스 낭비를 획기적으로 줄일 수 있습니다.2. 구현 방식백트래킹은 주로 DFS 형식을 빌려 재귀적으로 구현합니다. 유효한 상태를 찾아 깊게 탐색하다가, 막다른 길에 다다르면 이전 상태로 ..

1. 문제 설명문제 링크: LeetCode 51 - N-Queens요약: $n \times n$ 체스판에 $n$개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 찾는 문제입니다. 퀸은 같은 행, 열, 그리고 양방향 대각선 위에 있는 기물을 공격할 수 있습니다.2. 핵심 아이디어이 문제는 대표적인 백트래킹(Backtracking) 문제입니다. 모든 위치를 다 시도해보되, 퀸을 놓을 수 없는 조건이 되면 즉시 되돌아가서 다른 경로를 탐색합니다.행별 배치: 퀸은 같은 행에 존재할 수 없으므로, 0번 행부터 $n-1$번 행까지 한 행에 하나씩 퀸을 배치하며 내려갑니다.공격 가능 여부 체크: 현재 위치(row, col)에 퀸을 놓을 수 있는지 판단하기 위해 기존에 배치된 퀸들과 비교합니다.같은 열: q..

1. 문제 설명문제 링크: LeetCode 402 - Remove K Digits요약: 주어진 숫자 문자열 num에서 k개의 숫자를 제거하여 만들 수 있는 가장 작은 수를 구하는 문제입니다. 결과값에서 앞자리에 오는 0은 제거해야 하며, 빈 문자열이 될 경우 "0"을 리턴해야 합니다.2. 핵심 아이디어가장 작은 수를 만들기 위해서는 앞자리에 최대한 작은 숫자가 위치해야 합니다. 이를 위해 그리디(Greedy) 알고리즘과 단조 증가 스택(Monotonic Stack) 논리를 활용합니다.비교와 제거: 숫자를 순차적으로 확인하며, 현재 숫자보다 바로 앞의 숫자가 더 크다면 앞의 숫자를 제거합니다. 이 과정을 k번 반복하여 큰 숫자가 앞자리에 오지 못하게 막습니다.스택의 활용: StringBuilder를 스택처..

1. 문제 설명문제 링크: LeetCode 1775 - Closest Dessert Cost요약: 주어진 예산 내에서 target 금액에 가장 가까운 디저트 비용을 만드는 문제입니다.하나의 Base(필수)를 선택해야 합니다.여러 종류의 Topping(선택)을 추가할 수 있으며, 각 토핑은 최대 2개까지 사용 가능합니다.target과의 차이가 동일한 비용이 여러 개라면, 더 낮은 비용을 선택합니다.2. 핵심 아이디어이 문제는 선택의 가짓수가 제한적이고(토핑당 0, 1, 2개), 모든 경우를 탐색해도 시간 내에 해결 가능한 백트래킹(Backtracking) 문제입니다.완전 탐색: 모든 베이스 비용에 대해 각각 토핑을 추가하는 모든 경우의 수를 확인합니다.상태 정의: dfs(index, currentCost)..

1. 문제 설명문제 링크: 백준 2979번 - 트럭 주차요약: 세 대의 트럭이 주차된 시간대에 따라 주차 요금을 계산하는 문제입니다. 주차된 트럭의 대수(1대, 2대, 3대)에 따라 한 대당 부과되는 요금이 달라지며, 각 트럭의 입차 시간과 출차 시간이 주어질 때 총 주차 요금을 구해야 합니다.2. 핵심 아이디어이 문제를 처음 봤을때 인터벌 그래프 문제로 생각하고 봤는데 구간도 노드도 작아 시뮬레이션으로 접근했습니다. 핵심은 특정 시각에 주차장에 차가 몇 대 있는지 파악하는 것입니다.요금 처리: 1대일 때 A, 2대일 때 B, 3대일 때 C원이며 이는 '한 대당' 요금입니다. 코드에서는 계산의 편의를 위해 **(요금 * 대수)**를 미리 계산하여 배열에 저장합니다.시점 관리: 각 트럭의 입차 시간과 출차..

1. 문제 설명문제 링크: 백준 10808번 - 알파벳 개수요약: 알파벳 소문자로만 이루어진 단어 S가 주어졌을 때, 각 알파벳이 단어에 몇 개 포함되어 있는지 구하는 프로그램을 작성하세요. 출력은 'a'부터 'z'까지의 개수를 공백으로 구분하여 출력합니다.2. 핵심 아이디어이 문제의 핵심은 알파벳 문자를 배열의 인덱스로 변환하는 것입니다.배열 생성: 알파벳 소문자는 총 26개입니다. 따라서 크기가 26인 정수 배열 int[] cnt = new int[26]을 생성합니다. (0번 인덱스는 'a', 25번 인덱스는 'z'를 의미하게 됩니다.)아스키코드 활용: 컴퓨터는 문자를 숫자로 처리합니다. 소문자 'a'의 아스키코드 값을 문자에서 빼주면 해당 문자의 순서를 0~25 사이의 숫자로 얻을 수 있습니다.'a..

1. 문제 설명문제 링크: 백준 2309번 - 일곱 난쟁이요약: 아홉 명의 난쟁이 중 진짜 일곱 명의 난쟁이를 찾아야 합니다. 일곱 명의 키의 합은 정확히 100입니다. 아홉 명의 키가 주어졌을 때, 진짜 일곱 명을 찾아 키를 오름차순으로 출력하는 프로그램을 작성하세요.2. 핵심 아이디어이 문제의 핵심은 전체 아홉 명 중 가짜 두 명을 골라내는 것입니다.발상의 전환: 아홉 명 중 일곱 명을 골라 합을 구하는 조합(Combination)을 생각할 수도 있지만, 반대로 (전체 9명의 합) - (가짜 2명의 합) = 100이 되는 두 명을 찾는 것이 훨씬 효율적입니다.전체 탐색(Brute Force): 아홉 명 중 두 명을 고르는 경우의 수는 대략 36가지(9C2) 정도로 매우 적습니다. 따라서 2중 반복문을..