본문 바로가기
728x90

백준

 (52)
[백준] 트리의 지름 (1967번) 코드 힌트문제 이해이 코드는 트리에서 가장 긴 경로(지름)를 찾는 문제를 해결합니다.트리의 지름: 어떤 트리에서 가장 먼 두 노드 사이의 거리입니다.트리의 지름은 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 다시 가장 먼 노드를 찾는 방식으로 구할 수 있습니다.핵심 아이디어그래프 표현노드 수 N만큼의 배열을 생성하고, 각 요소를 List로 초기화합니다.인접 리스트(Adjacency List)를 사용해 노드 간의 연결 관계를 효율적으로 관리합니다.인접 리스트의 관리2차원 배열로도 연결을 표현할 수 있지만, 인접 리스트를 사용하면 연결된 노드만 관리할 수 있어 효율적입니다.각 배열의 인덱스에 .add(new Node)로 연결된 노드를 추가합니다.DFS(깊이 우선 탐색) 두 번 수행첫 번째 DFS: ..
[백준] 트리의 지름 (1967번) 코드 힌트문제 이해:목표 값 num을 만드는 연속된 자연수의 수열을 찾아야 합니다.수열의 길이(count)가 최소부터 시작해 점차 늘려가며 가능한 경우를 찾습니다.최대 길이 100까지 시도하고, 목표 값을 만드는 수열이 없으면 -1을 출력합니다.핵심 아이디어:주어진 숫자열의 중앙값(middle)을 중심으로 시작점을 계산합니다.길이가 짝수인 경우와 홀수인 경우를 나눠 시작 위치를 조정합니다.연속된 숫자들의 합이 목표 값과 같으면 그 수열을 출력합니다.알고리즘 흐름:수열의 중앙값을 기준으로 시작점 계산.연속된 숫자열의 합과 목표 값(num)을 비교.길이를 늘려가며(최대 100까지) 모든 경우 탐색.정답은 더보기 클릭더보기import java.util.*;class Main { public static ..
[백준] 명령 프롬프트 (1032번) 코드 힌트문제 이해:여러 문자열이 주어졌을 때, 모든 문자열에서 같은 위치의 문자가 동일한 경우 그 문자를 유지합니다.하지만 다른 문자가 있는 경우 해당 위치를 '?'로 바꿉니다.아이디어:첫 번째 문자열을 비교 기준으로 사용합니다.두 번째 문자열부터 문자 하나하나를 비교하며 다른 문자가 있으면 해당 위치에 '?'를 설정합니다.문자열 비교와 수정:StringBuilder를 사용한 이유는 문자열을 수정할 수 있기 때문입니다.String은 불변 객체이므로 StringBuilder가 성능적으로 유리합니다. 정답은 더보기 클릭더보기import java.util.*;public class Main { public static void main(String[] args) { Scanner in = ..
[백준] Z (1074번) 코드 힌트Z-모양 탐색:이 문제는 Z-모양으로 배열을 탐색하는 순서를 찾는 문제입니다.2차원 배열을 크기를 절반씩 줄여가며 재귀적으로 탐색합니다.배열 분할:각 호출에서 배열을 4개의 사분면으로 나누고, 목표 좌표가 속한 사분면만 재귀적으로 탐색합니다.나머지 사분면은 탐색하지 않고 그 영역의 칸 수만 더합니다.방문 순서 누적:탐색된 칸 수를 누적하여 목표 위치의 방문 순서를 계산합니다.기저 조건:재귀 호출의 기저 조건은 배열의 크기가 1일 때입니다. 이때 num을 출력합니다.  정답은 더보기 클릭더보기import java.util.*;class Main { static int num = 0; // 방문 순서를 저장하는 변수 static int r, c; // 목표 위치의 행(r), 열(..
[백준] 뱀과 사다리 게임 (16928번) 코드 힌트입력 처리사다리와 뱀의 개수를 입력받고, 각 사다리와 뱀의 시작 위치와 도착 위치를 배열 board에 저장합니다. 사다리와 뱀은 동일한 방식으로 처리됩니다.보드 초기화board 배열에서 시작 위치에 도착 위치가 설정되지 않은 경우, 그 위치는 자기 자신으로 설정하여 기본 이동을 가능하게 합니다. 이는 뱀이나 사다리가 없는 경우입니다.BFS 탐색큐를 사용하여 BFS(너비 우선 탐색) 방식으로 게임 보드를 탐색합니다. 큐에는 현재 위치와 그 위치에 도달하기 위한 이동 횟수를 저장합니다.주사위의 결과(1~6)를 기반으로 다음 위치를 계산하고, 해당 위치가 아직 방문하지 않았다면 큐에 추가합니다.종료 조건위치가 100에 도달했을 때, 이동 횟수를 비교하여 최소값을 업데이트합니다. BFS 특성상, 처음으..
[백준] 감소하는 수 (1038번) 코드 힌트 감소하는 숫자란?감소하는 숫자는 각 자리 숫자가 왼쪽에서 오른쪽으로 갈수록 작은 숫자들로 이루어진 숫자입니다. 예를 들어, 321, 520, 10 등이 있습니다. 이 코드의 목적은 입력받은 n번째 감소하는 숫자를 찾아 출력하는 것입니다.감소하는 숫자의 개수는 제한적입니다. 가장 큰 감소하는 숫자는 9876543210이고, 이러한 감소하는 숫자의 최대 개수는 1022개입니다.숫자 생성 방법:처음에는 0부터 9까지의 숫자를 시작으로 각 숫자를 확장해 나갑니다. 확장 시, 숫자의 마지막 자릿수보다 작은 숫자들만 추가로 붙여야 감소하는 숫자가 됩니다.예를 들어, 숫자 5를 시작으로 할 때, 54, 53, 52, 51, 50과 같이 마지막 자릿수 5보다 작은 숫자들을 뒤에 붙여서 새로운 숫자를 만들 수..
[백준] 균형잡힌 세상 (4949번) 코드 힌트:입력 처리사용자는 여러 줄의 문자열을 입력합니다. 입력된 문자열이 .으로 시작하지 않을 때까지 반복적으로 처리합니다.input.replaceAll("[a-zA-Z.]*", "")와 input.replaceAll("\\s++", "")를 통해 괄호 외의 문자와 공백을 제거한 후 문자열을 처리합니다.스택을 이용한 괄호 짝 검사각 문자열을 순회하며 열린 괄호 ( 또는 [는 스택에 추가합니다.닫힌 괄호 ) 또는 ]를 만날 경우, 스택의 최상단에 있는 열린 괄호와 짝이 맞는지 확인합니다.짝이 맞으면 스택에서 제거하고, 그렇지 않으면 isAble을 false로 설정해 잘못된 괄호 짝임을 표시합니다.결과 출력문자열 순회가 끝난 후, isAble이 true이고 스택이 비어있으면 괄호가 올바르게 닫혔으므로 "..
[백준] 보물 (1026번) 코드 힌트목표:두 배열의 원소를 재배열하여, 각 원소끼리 곱한 값들의 합이 최소가 되도록 계산하는 문제입니다.정렬 방식:arr1은 오름차순으로 정렬하고, arr2는 내림차순으로 곱셈을 진행합니다. 이렇게 하면, 큰 값과 작은 값이 곱해져 전체 곱셈 결과를 최소화할 수 있습니다.곱셈과 합산:arr1의 작은 값과 arr2의 큰 값을 곱해가며, 각 곱셈 결과를 result 변수에 누적하여 최소 값을 얻습니다.배열 크기와 정렬:배열의 크기 n을 입력받고, 두 배열을 각각 정수 배열로 변환한 후, 정렬을 수행한 뒤 대응하는 원소들을 곱합니다.정답은 더보기 클릭더보기import java.util.*;class Main { public static void main(String[] args) { i..
728x90

티스토리툴바