Algorithm

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중 반복문을..

427. Construct Quad Tree 이 문제는 보자마자 전형적인 분할 정복 문제라는 것이 보였고, 4개 분면으로 나눠가며 grid의 특정 범위 내의 모든 수가 같은 케이스에는 isLeaf 값을 참으로 갖는 node를 반환하는 식으로 한다면, size가 1x1인 grid 범위가 될 때 같은 베이스 케이스도 필요 없이 통과할 수 있다 생각해 아래 코드와 같이 작성했습니다.class Solution { public Node construct(int[][] grid) { return construct(grid, 0, 0, grid.length, grid[grid.length-1].length); } public Node construct(int[][] grid, int to..