전체 글

1. 문제 설명문제 링크: 프로그래머스 118670 - 행렬과 연산요약: $R \times C$ 크기의 행렬에 두 가지 연산(ShiftRow, Rotate)을 연속해서 수행한 후의 최종 행렬을 구하는 문제입니다.ShiftRow: 모든 행을 아래로 한 칸씩 이동시킵니다. (마지막 행은 첫 번째 행으로 이동)Rotate: 행렬의 가장 바깥쪽 테두리에 있는 원소들을 시계 방향으로 한 칸씩 회전시킵니다.2. 핵심 아이디어이 문제의 핵심은 $O(1)$ 복잡도로 연산을 처리하기 위해 행렬을 3개의 덱(Deque) 구조로 분할하여 관리하는 것입니다.초기 시도 및 한계: 처음에는 System.arraycopy()를 활용해 2차원 배열을 직접 시프트하거나 회전시키는 방식을 고려했으나, 이 경우 각 연산마다 최악 $O(R..

1. 문제 설명문제 링크: 프로그래머스 42579 - 베스트앨범요약: 장르별로 가장 많이 재생된 노래를 최대 2개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 재생 횟수가 많은 장르를 먼저 수록하며, 장르 내에서는 재생 횟수가 많은 노래, 재생 횟수가 같다면 고유 번호(인덱스)가 낮은 노래를 우선하여 수록해야 합니다.2. 핵심 아이디어이 문제는 해시(HashMap)와 우선순위 큐(PriorityQueue), 그리고 정렬을 조합하여 조건에 맞게 데이터를 그룹화하고 추출하는 문제입니다.장르별 총 재생 횟수 집계 (rankMap): HashMap을 사용하여 장르별 누적 재생 횟수를 합산하고, 이를 기반으로 장르의 우선순위를 정렬합니다.장르별 노래 정렬 (pqMap): 각 장르 내에서 노래들을 재생 횟수 내림..

1. 문제 설명문제 링크: 프로그래머스 42748 - K번째수요약: 배열 array의 $i$번째부터 $j$번째까지 잘라내어 정렬했을 때, $k$번째에 있는 수를 구하는 문제입니다. 여러 개의 명령어 commands가 [i, j, k] 형태로 주어지며, 각 명령에 대한 결과를 배열에 담아 반환해야 합니다.2. 핵심 아이디어일반적으로 이 문제는 Arrays.copyOfRange()나 Arrays.sort()를 이용해 배열을 잘라내고 정렬하는 방식으로 해결합니다. 하지만 제출하신 코드는 카운팅 정렬(Counting Sort)의 원리를 활용하여 색다른 접근 방식을 보여줍니다.원소의 제한 조건 활용: 문제 조건에서 array의 원소 값은 1 이상 100 이하의 자연수입니다. 데이터의 범위를 이미 알고 있으므로 크..

1. 문제 설명문제 링크: 프로그래머스 42578 - 의상요약: 각 의상의 이름과 종류가 주어질 때, 서로 다른 옷의 조합의 수를 구하는 문제입니다. 스파이는 매일 최소 한 개의 의상을 입어야 하며, 같은 종류의 의상은 하나만 입을 수 있습니다.2. 핵심 아이디어이 문제는 해시(Hash)를 활용해 의상 종류별 개수를 파악한 뒤, 모든 가능한 의상 조합의 수를 계산하는 조합 알고리즘 문제입니다.해시 맵 분류: HashMap을 사용해 의상 종류(카테고리)별로 몇 개의 의상이 존재하는지 카운팅합니다.조합 탐색(DFS/재귀): 제출하신 코드는 종류별 의상 개수(vals)를 구한 뒤, 재귀 함수(solve)를 이용해 1개 종류를 선택하는 경우부터 모든 종류를 선택하는 경우까지의 모든 조합을 직접 탐색하며 곱과 합..

1. 문제 설명문제 링크: 프로그래머스 42748 - K번째수요약: 배열 array의 $i$번째부터 $j$번째까지 잘라내어 정렬했을 때, $k$번째에 있는 수를 구하는 문제입니다. 여러 개의 명령어 commands가 [i, j, k] 형태로 주어지며, 각 명령에 대한 결과를 배열에 담아 반환해야 합니다.2. 핵심 아이디어일반적으로 이 문제는 Arrays.copyOfRange()나 Arrays.sort()를 이용해 배열을 잘라내고 정렬하는 방식으로 해결합니다. 하지만 제출하신 코드는 카운팅 정렬(Counting Sort)의 원리를 활용하여 색다른 접근 방식을 보여줍니다.원소의 제한 조건 활용: 문제 조건에서 array의 원소 값은 1 이상 100 이하의 자연수입니다. 데이터의 범위를 이미 알고 있으므로 크..

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..