BOJ

[백준] 2448번 : 별 찍기 - 11 Gold4(골드4) - JAVA[자바]

[Gold IV] 별 찍기 - 11 - 2448 문제 링크 성능 요약 메모리: 234796 KB, 시간: 476 ms 분류 재귀 제출 일자 2024년 1월 19일 00:23:23 문제 설명 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 접근 방법 1. 주어진 예시를 본다면 N이 3일 때 3층짜리 삼각형이고 맨 아랫줄은 6개의 공간이 생기는 것을 알 수 있다. 2. 출발점에서 시작하여 밑변의 길이를 2로 나누면 아래층의 시작점을 나눌 수 있다. 3. 밑변의 길이를 2로 나눈 것을 한번 더 나눠준다면(높이는 N이고 너..

[백준] 17073번 : 나무 위의 빗물 Gold5(골드5) - JAVA[자바]

[Gold V] 나무 위의 빗물 - 17073 문제 링크 성능 요약 메모리: 131348 KB, 시간: 480 ms 분류 그래프 이론, 그래프 탐색, 수학, 트리 제출 일자 2024년 1월 17일 22:07:48 문제 설명 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 1번 정점을 루트로 하는 어떤 트리를 나타낸 모습이다. 사실 이 트리는 영훈이가 뒷마당에서 기르고 있는 나무이다. 어제는 비가 왔기 때문에, 트리의 1번 정점에는 W만큼의 물이 고여 있다. 1번 정점을 제외한 모든 정점에는 아직 물이 고여 있지 않은 상태이다. 이제 매초마다 모든 정점은 아래의 작업을 순서대로 반복한다. 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면..

[백준] 11404번 : 플로이드 Gold4(골드4) - JAVA[자바]

[Gold IV] 플로이드 - 11404 문제 링크 성능 요약 메모리: 42752 KB, 시간: 344 ms 분류 플로이드–워셜, 그래프 이론, 최단 경로 제출 일자 2024년 1월 17일 00:19:23 문제 설명 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발..

[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바]

[Silver I] 케빈 베이컨의 6단계 법칙 - 1389 문제 링크 성능 요약 메모리: 11952 KB, 시간: 92 ms 분류 너비 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 제출 일자 2024년 1월 16일 23:22:42 문제 설명 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되..

[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바]

[Silver I] 경로 찾기 - 11403 문제 링크 성능 요약 메모리: 17864 KB, 시간: 296 ms 분류 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 제출 일자 2024년 1월 16일 22:37:22 문제 설명 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제..

[백준] 14675번 : 단절점과 단절선 Silver1(실버1) - JAVA[자바]

[Silver I] 단절점과 단절선 - 14675 문제 링크 성능 요약 메모리: 57668 KB, 시간: 404 ms 분류 단절점과 단절선, 그래프 이론, 트리 제출 일자 2024년 1월 16일 21:03:54 문제 설명 그래프 이론에서 단절점(cut vertex)과 단절선(bridge)은 다음과 같이 정의 된다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단절선이라 한다. 이 단절점과 단절선을 우리는 트리(tree)에서 구하려고 한다. 그래프 이론에서 트리(tree)의 정의는 다음과 ..

[백준] 1068번 : 트리 Gold5(골드5) - JAVA[자바]

[Gold V] 트리 - 1068 문제 링크 성능 요약 메모리: 11564 KB, 시간: 76 ms 분류 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리 제출 일자 2024년 1월 16일 00:09:22 문제 설명 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 ..

[백준] 9934번 : 완전 이진 트리 Silver1(실버1) - JAVA[자바]

[Silver I] 완전 이진 트리 - 9934 문제 링크 성능 요약 메모리: 11972 KB, 시간: 88 ms 분류 재귀, 트리 제출 일자 2024년 1월 15일 23:29:19 문제 설명 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다. 깊이가 2와 3인 완전 이진 트리 상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게..