본문 바로가기

백준_JAVA46

[백준] 11403번 - 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 플로이드 워셜(Floyd - Warshall) 알고리즘에 대한 기본 개념을 이해할 수 있는 문제이다. 이전에 학습한 다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이었다면, 플로이드 - 워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하고자 할 때 사용하는 알고리즘이다. 플로이드 워셜 알고리즘의 작동 방법은 다이나믹 프로그래밍을 적용한 완전 탐색 방법으로, 정점의 갯수가 N 일 때 시간 복잡도 O(N^3)을 갖는다. 따라서 N의 크기가 너무 크다면 .. 2023. 6. 7.
[백준] 1753번 - 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘은 그래프에서 출발 정점으로부터 이동할 수 있는 모든 정점까지의 최단 거리를 구할 때 사용하는 알고리즘 중 한 종류이다. 해당 문제는 다익스트라 알고리즘에 대한 기본 개념을 이해하기에 좋다. 다익스트라 알고리즘에 대한 설명 및 문제 풀이 방법은 아래 글을 참고하자. [알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 간단하게 DFS 혹은 .. 2023. 6. 6.
[백준] 2470번 - 두 용액 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 전체 N개의 용액 중 두 용액의 특성값의 합이 0에 가장 가까운 조합을 오름차순으로 출력하시오. 조건 2 2023. 6. 5.
[백준] 11660번 - 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N x N 크기의 표가 있을 때, M번 주어지는 (x1, y1) 부터 (x2, y2)까지 합을 구하시오. 조건 1 2023. 5. 31.
[백준] 1018번 - 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 1x1 정사각형 구획으로 나뉘어져 있는 MxN 크기의 보드에 한 구획마다 흰색 또는 검은색이 무작위로 칠해져 있을 때, 인접하는 구획끼리 서로 다른 색을 갖도록 하여 8x8 크기의 체스판을 만들기 위해 다시 칠해야 하는 정사각형 구획의 최소 개수를 구하여라. 조건 만들고자 하는 체스판의 크기는 8 x 8 8 2023. 5. 31.
[백준] 11659번 - 구간 합 구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구해야 한다. 조건 1 2023. 5. 30.
[백준] 2447번 - 별 찍기 - 10 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 별 찍기 10이다. 재귀함수와 분할정복 알고리즘을 사용하여 해결할 수 있다. 분할정복에 익숙하지 않다면 아래 문제를 먼저 해결해보자. [백준] 2630번 - 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마 stonage.tistory.com 문제에서.. 2023. 5. 29.
[백준] 3273번 - 두 수의 합 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 n개의 정수로 이루어진 수열에서 수열의 요소인 Ai, Aj와 그외 주어지는 자연수 x에 대하여 Ai + Aj = x를 만족하는 (Ai, Aj)의 쌍의 갯수를 구하시오. 조건 수열의 요소를 Ai라고 할때 1 2023. 5. 29.
[백준] 1976번 - 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1번부터 N번까지의 도시가 있을 때, 입력으로 i 번째 도시와 j 번째 도시의 연결 여부가 주어질 때 여행 계획의 모든 도시를 방문할 수 있는지 확인하는 문제이다. 따라서 도시가 정점이고 도시간의 연결 정보가 정점간의 간선인 그래프로 치환하여 접근할 수 있겠다. 추가로 도시간의 연결은 양방향성을 가지므로 무방향 그래프이고 여행 계획 순서대로 여행을 하는 동안 이미 방문한 도시를 중복해서 방문하는 것이 가능하다고 하였으므로 여행 계획에 있는 도시들이 하나의 연결 .. 2023. 5. 27.

티스토리툴바