문제 파악 이 문제는 1번 노드에서 시작해서 다른 모든 노드로의 최단 거리를 구한 뒤,가장 멀리 떨어진 노드가 몇 개인지 찾는 문제다. 즉, “최대 거리값”을 구하고, 그 거리값을 갖는 노드의 개수를 세어야 한다. 접근 방법 그래프는 n개의 노드와 edge로 주어진다.간선은 양방향이므로 인접 리스트로 관리한다.최단 거리를 구하기 위해 BFS(너비 우선 탐색)를 사용한다.BFS는 시작점에서부터 가까운 순으로 탐색하기 때문에, 방문 순서대로 거리를 채울 수 있다.BFS가 끝나면 dist[] 배열에 각 노드까지의 최단 거리가 기록된다.그 후 dist[]를 돌면서 최대 거리와 그 개수를 찾는다.코드 구현import java.util.*;class Solution { static int[] dist; ..

문제 파악 프로그래머스의 “상품 별 오프라인 매출 구하기” 문제는상품 테이블(PRODUCT)과 오프라인 판매 테이블(OFFLINE_SALE)을 활용해 상품별 총 매출액을 구하는 문제다. PRODUCT 테이블에는 상품 ID(PRODUCT_ID), 상품 코드(PRODUCT_CODE), 가격(PRICE) 정보가 있다.OFFLINE_SALE 테이블에는 상품 ID(PRODUCT_ID), 판매량(SALES_AMOUNT) 정보가 있다. 매출액은 PRICE * SALES_AMOUNT 의 합으로 계산해야 하며,출력은 PRODUCT_CODE, SALES(총 매출액) 컬럼으로 구성해야 한다. 정렬 조건은 다음과 같다. 매출액(SALES) 내림차순매출액이 같으면 PRODUCT_CODE 오름차순 접근 방법 1. 매출액은 가격..

문제 파악 이 문제는 N×N 크기의 지도에서 0은 바다, 1은 육지로 주어졌을 때, 상하좌우로 연결된 육지를 하나의 섬으로 정의하고, 지도에 존재하는 모든 섬의 **면적(넓이)**을 구해 출력하는 문제다. 섬의 면적 = 연결된 육지 칸의 개수섬이 여러 개일 수 있으며, 각각의 면적을 구해 출력해야 한다.출력 형식은 #테스트케이스번호 면적1 면적2 ... 이다.좌표 크기는 최대 100×100으로, DFS/BFS로 충분히 탐색 가능하다. 접근 방법 입력 처리BufferedReader와 StringTokenizer를 사용해 빠르게 그리드 데이터를 읽어온다.지도는 int[N][N] 배열로 저장한다.탐색 준비visited[N][N] 배열을 두어 이미 방문한 육지를 다시 세지 않도록 한다.상하좌우 방향을 dr, d..

문제 파악 이 문제는 마을(노드)과 길(간선) 정보를 입력받아, 특정 K개의 마을에서 출발할 때 연결된 마을들을 출력하는 문제다. 마을의 개수 N은 최대 10,000개길의 개수 M은 최대 50,000개출력해야 하는 시작 마을의 개수 K는 최대 100개 즉, 입력 크기가 크기 때문에 효율적인 그래프 저장 방식이 필요하며, 단순 배열보다는 인접 리스트를 사용하는 것이 적절하다. 접근 방법 입력 처리:BufferedReader와 StringTokenizer를 사용해 빠르게 입력을 처리했다. Scanner는 간단하지만 대량의 입력에서는 속도가 느리므로 적합하지 않았다.그래프 표현:초기에는 1-based 인덱스를 가정하고 N+1 크기를 할당했으나, 문제 입력을 다시 확인한 후 0-based에 맞게 수정했다.그래프..

완전 탐색은 과정을 이해하기 쉽도록 의사결정 트리(possibility tree)를 사용한다.따라서, 완전탐색과 의사결정 트리가 무엇인지 먼저 살펴본다!완전탐색완전탐색(Exhaustive Search)은 정답이 될 가능성이 있는 모든 후보를 탐색해서 정답을 찾는 알고리즘이다.의사결정 트리의사결정 트리는 문제를 해결하는 모든 경우의 수를 트리 형태로 나타낸 것이다.이를 깊이 우선 탐색(DFS) 방식으로 탐색하면 가능한 모든 경우를 빠짐없이 확인할 수 있다. => 즉, 완전탐색은 의사결정 트리를 DFS 기반으로 순회하는 과정과 동일!!- 의사결정 트리의 특징가능한 모든 경우를 표현한다.모든 선택지를 고려해야 하니까, 트리 구조로 나타내서 더 직관적으로 이해할 수 있다.DFS 방식으로 탐색한다.한 가지 경우를..

1. 문제 이해이 문제는 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다.덧셈의 순서가 다르면 다른 경우로 카운트한 개의 수를 여러 번 사용할 수 있음예제 분석예제 입력 120 2 예제 출력 121 설명:K = 2 이므로 두 개의 수를 더해서 N = 20을 만들어야 함.가능한 경우: (0+20), (1+19), (2+18), ..., (20+0) → 21가지예제 입력 26 4 예제 출력 284 설명:K = 4 이므로 네 개의 수를 더해서 N = 6을 만들어야 함.가능한 경우: (0+0+0+6), (0+0+1+5), ... 등 84가지✅ 제한 조건1 ≤ N ≤ 2001 ≤ K ≤ 200경우의 수를 1,000,000,000(10억)으로 나눈 나머지 출력2. 접근 방식 (DP..