Algorithm & Data Structure/백준

[JAVA] 백준 11724번 : 연결 요소의 개수

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램. 입력 - 첫째 줄에 정점의 개수 N과 간선의 개수 M. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) - 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력..

[JAVA] 백준 1260번 : DFS와 BFS

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 - 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V - 다음 M개의 줄에는 간선이 ..

[JAVA] 백준 1026번 : 보물

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거� www.acmicpc.net 문제 길이가 N인 정수 배열 A와 B, 다음과 같이 함수 S가 정의되있다. S = A[0]*B[0] + ... + A[N-1]*B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열한다. 단, B에 있는 수는 재배열 하면 안됨. S의 최솟값을 출력하는 프로그램 입력 - 첫째 줄에 N ( 50보가 작거나 같은 자연수) - 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어짐 ( 10..

[JAVA] 백준 1890번 : 점프

1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 NXN 게임판에 수가 적혀져 있다. 게임의 목표 : 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것 각 칸에 적혀 있는 수 : 현재 칸에서 갈 수 있는 거리 -> 반드시 오른쪽이나 아래로 가야함. -> 한 번 점프를 할 때, 방향을 바꾸면 안됨. -> 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두가지 경우만 존재. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 ..

[JAVA] 백준 3036번 : 링

3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 문제 - 여러개의 링이 있고 그 링들의 반지름이 주어졌을때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램 입력 - 첫째 줄에 링의 개수 N (3 ≤ N ≤ 100) - 다음 줄에는 링의 반지름 (반지름은 1과 1000를 포함하는 사이의 자연수) 출력 - 출력은 총 N-1줄을 해야 한다. - 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력 풀이 원의 둘레 공식..

[JAVA] 백준 2609번 : 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램 입력 첫째 줄에는 두 개의 자연수 (10,000이하) 출력 -첫째 줄에는 입력으로 주어진 두 수의 최대공약수를 출력 -둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력 풀이 최대공약수 문제를 풀기 위해선 유클리드 호제법 이라는 알고리즘을 이용하면 쉽다! 유클리드 호제법이란 2개의 자연수(또는 정식)의 최대공약수를 구하는 알고리즘의 하나로, 호제법이라는 말이 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 이론은 ..

[JAVA] 백준 14501번 : 퇴사

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 - N+1일째 되는 날 퇴사 - 남은 N일 동안 최대한 많은 상담을 함 - 각각의 상담은 상담을 완료하는데 걸리는 기간 : Ti - 상담을 했을 때 받을 수 있는 금액 : Pi 이때 얻을 수 있는 최대 수익을 구하는 프로그램 - N = 7인 경우에 다음과 같은 상담 일정표 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게..

[JAVA] 백준 1932번 : 정수 삼각형

1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. - 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램 - 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택가능 - 삼각형의 크기는 1 이상 500 이하이다. - 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9..