본문 바로가기

분류 전체보기144

[Java] 백준 11724번 연결 요소의 개수 https://www.acmicpc.net/problem/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 문제 설명 방향 없는 그래프에서 연결 요소의 개수 구하기 N : 정점의 개수(1 ≤ N ≤ 1,000) M : 간선의 개수 (0 ≤ M ≤ N×(N-1)/2) u,v : 양 끝점 재귀를 통한 DFS로 탐색하여 풀었고 방문 여부가 false일때까지 검사하여 cnt를 증가해준다. import java.util.ArrayList; imp.. 2020. 5. 22.
[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 = A [0]*B [0] +... + A [N-1]*B [N-1] 배열 A를 재배열해서 S를 최솟값으로 만들기. (단, B의 수는 재배열하면 안 됨) S의 최솟값 출력하기 우선 코드를 생각하지 않고 이론적으로 생각해보면 쉽게 풀린다. S는 배열 A, B의 원소를 각각 곱한 합이기 때문에 최솟값을 구하기 위해 S = 가장 큰 값 * 가장 작은 값 +.. 2020. 5. 20.
[Java] 백준 1890번 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 설명 N : 게임 판의 크기 게임판에 쓰인 수만큼 오른쪽 혹은 아래쪽으로만 점프 가능 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 이동할 수 있는 경로의 개수 구하기 단, 가장 오른쪽 아래 칸 수는 0 (종착점) 오른쪽으로 이동했을 때와 아래칸으로 이동했을 때 두 가지 경우로 나누어 생각하면 쉽게 규칙을 찾을 수 있다. graph [][] : 게임판 , dp [][] : 경로의 수라고 하자.. 2020. 5. 20.
[Java] 백준 DFS와 BFS 그래프 정점과 간선으로 이루어진 자료구조 G = ( V, E ) 그래프 탐색 간선을 통해 모든 정점을 방문하는 것 그래프 탐색 방법 - 깊이 우선 탐색 DFS - 너비 우선 탐색 BFS 깊이 우선 탐색 DFS 깊이 우선 탐색은 그래프에서 노드의 자식들을 우선 탐색하는 방법이다. 위 그림을 보면 DFS는 1, 2, 4, 5, 3, 6, 7 순으로 탐색한다. DFS는 재귀함수나 스택 자료구조를 사용한다. 모든 노드를 방문하는 경우에 깊이 우선 탐색 방법을 선택한다. 검색 속도는 BFS보다 느리다. 너비 우선 탐색 BFS 너비 우선 탐색은 인접 노드를 먼저 탐색하는 방법이다. 위 그림에서 BFS는 1, 2, 3, 4, 5, 6, 7 순으로 탐색한다. BFS는 큐 자료구조를 사용한다. 두 노드 사이 최단 경로나.. 2020. 5. 18.
[Java] 백준 2609번 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 설명 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수 출력하는 프로그램 작성 최대 공약수를 구하는 코드는 다음과 같다. public static int gcd(int a, int b){ while(b!=0){ int r = a%b; a= b; b= r; } return a; } 최소 공배수는 구한 최대 공약수에서 최대 공약수로 나누어진 몫들의 값을 곱해주면 된다. 따라서, import java.util.Scanner; public class Main {.. 2020. 5. 16.
[Java] 백준 3036번 링 https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 문제 설명 N개의 링이 접하도록 놓여있을때 첫번째 링을 한바퀴 돌리면 나머지 링이 몇바퀴 돌아가는지 구하기 반지름은 1~1000까지 자연수 최대공약수를 나누고 각각의 수를 최대공약수로 나누어 출력하는 간단한 수학적 개념의 문제이다. 최대 공약수를 구하는 코드는 다음과 같다. public static int gcd(int a, int b){ while(b!=0){ int r = a%b; a= b; b= r; .. 2020. 5. 16.

티스토리툴바