본문 바로가기

백준

 (54)
[백준] DFS와 BFS (1260번) 문제 이해이 코드는 그래프 탐색 문제로, DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 인접 행렬로 구현합니다.그래프의 각 노드는 1부터 시작하며, 주어진 노드로부터 연결된 모든 노드를 순서대로 탐색합니다.입력으로 주어지는 간선 정보를 통해 무방향 그래프를 구성하고, 두 가지 탐색 방법으로 탐색 결과를 출력합니다.핵심 아이디어그래프를 인접 행렬로 표현:노드 간의 연결을 2차원 배열에 저장합니다.만약 두 노드가 연결되어 있다면 해당 위치에 1을 표시합니다.DFS(깊이 우선 탐색):한 노드에서 출발해 인접 노드를 재귀적으로 방문합니다.재귀 호출을 사용해 그래프의 모든 연결된 노드를 탐색합니다.BFS(너비 우선 탐색):큐(Queue)를 사용해 노드들을 순서대로 탐색합니다.한 노드에서 출발해 같은 레벨의..
[백준] 토너먼트 (1057번) 힌트문제 이해이 문제는 이진 트리 구조에서 두 개의 노드가 주어질 때, 이 두 노드가 부모 노드를 통해 만나는 경로를 찾는 문제입니다.주어진 노드가 서로 만나기 위해서는 서로의 부모 노드로 이동해야 하며, 이 과정에서 몇 번의 이동이 필요한지를 계산합니다.핵심 아이디어부모 노드 계산:이진 트리에서 부모 노드는 다음과 같이 계산할 수 있습니다:부모 노드 = (자식 노드 - 1) / 2 + 1이 공식을 사용하여 두 위치(pos1, pos2)의 부모 노드를 반복적으로 계산합니다.만나는 조건:두 위치가 동일할 때까지 부모 노드로 이동합니다.이동하는 횟수를 카운트하여 최종 결과를 출력합니다.알고리즘 흐름사용자로부터 노드 수와 두 위치를 입력받습니다.두 위치가 서로 다를 때까지 부모 노드로 이동합니다.이동한 라운드..
[백준] 트리의 지름 (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보다 작은 숫자들을 뒤에 붙여서 새로운 숫자를 만들 수..

티스토리툴바