반응형 실버218 [백준] 1654번 - 랜선 자르기 (Java)(○) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net K개의 길이가 다른 랜선을 가지고 있다. 이를 잘라서 같은 길이의 N개의 랜선을 만들어야 한다. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. ( 2022. 10. 6. [백준] 2805번 - 나무 자르기 (Java) https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 나무를 자르는데 총 N개의 나무를 높이 H로 잘라서 남은 길이의 합이 M이상이 되는 H의 최대값을 구하라. - N : 나무의 수 ( 1 2022. 10. 5. [백준] 1541번 - 잃어버린 괄호 (Java) 1. 첫번째 수는 무조건 양수가 온다고 했으니 그 수에서 뺀값이 가장 작으려면 뒤에 -가 붙는 수가 가장 큰수여야 한다. 2. - 기호가 나오면 그 뒤로 나오는 수들을 모두 더해서 음수로 된 최대값을 만들어야 한다. 3. - 기호가 나오기 전까지의 숫자는 계속 더해주다가 - 기호가 나오면 거기서 괄호를 쳐서 모두 더해서 빼면 된다. ex) 55-50+40 = 55 - (50 + 40) = 55 - 90 = -35 10+55-50+40 = 10+55 - (50+40) = 65 - 90 = -25 1. 3개의 구현이 필요하다. 1-1. 입력 받은 문자열을 -를 기준으로 잘라서 문자열 배열에 담는 작업 1-2. 자른 문자열을 +를 기준으로 수를 뽑아내어서 더하는 작업 1-3. 각 취합된 수를 빼는 작업 2. .. 2022. 9. 19. [백준] 2644번 - 촌수계산 (Java) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 1. 부모-자식 관계지만 거슬러 올라갈 수 있으므로 방향이 없는 트리와 같다. 2. DFS 파라미터로 정점 번호와 count를 넘겨준다. 3. Y를 찾지 못하면 flag를 둬서 -1을 출력한다. import java.util.*; /* [백준] 2644번 - 촌수계산 (Java) */ public class Main { static int N, M, X, Y; ArrayList.. 2022. 9. 5. [백준] 11725번 - 부모의 트리찾기 (Java)(○) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [첫번째] 1. 입력함수에서 인접행렬로 정점과 간선을 표현하자. 2. 방향이 없기 때문에 양쪽 모두 행렬로 표현해야 한다. 3. dfs 파라미터는 다음 정점 번호를 넘겨주자. 4. 1번의 루트 고정이므로 2번 정점부터 각 정점의 부모 노드가 뭔지 출력하면 된다. 5. 위의 출력 예제에서 2번 정점의 부모는 4번, 3번의 부모는 6번인 셈이다. 6. 1번부터 dfs 탐색을 해서 이미 방문한 노드가 부모인 셈이므로 그 번호를 출력하면 된다. 더보기 import j.. 2022. 9. 3. [백준] 4963번 - 섬의 개수 (Java)(◎) https://www.acmicpc.net/problem/4963 1. 상하좌우대각선까지 탐색해야 한다. 2. w와 h가 0 0이면 테스트케이스를 종료한다. 1. map에서 상하좌우대각선을 탐색한 후 1이면 방문처리한다. 2. 메인함수에서 for문을 돌려서 1을 발견하면 dfs를 돌리고 섬개수를 ++한다. 1. 입력함수를 TC를 while문으로 받고 w와 h가 0이면 break 하는 식으로 구현 2. 확장할 때 새 지점이 섬인지 바다인지 체크하는 구문 빼먹음. if (A[nx][ny] == 0) 더보기 import java.util.*; /* [백준] 4963번 - 섬의 개수 (Java) */ public class Main { static int w, h; static int A[][]; static .. 2022. 8. 31. [백준] 11724번 - 연결 요소의 개수 (Java)(◎) 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 1. 연결 요소의 개수는 연결된 정점 그룹의 개수라고 생각하면 된다. 2. 방향성이 없는 그래프이므로 인접행렬로 받도록 하자. 1. 그룹화를 만드는 것이 관건이다. 메인함수에서 dfs를 호출할 때 for문을 돌려서 정점 1번부터 N번까지 돌면서 호출하자. 2. 방문배열 visited[]를 적극 활용해서 이미 방문한 정점은 스킵하자. 조.. 2022. 8. 31. [백준] 1012번 - 유기농 배추 (Java)(◎) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 지렁이는 상/하/좌/우로만 연결된 배추로만 이동할 수 있으니, 상하좌우로 연결된 배추군집의 수를 구하면 된다. 2. 입력형식이 배추의 좌표이므로 이를 받아서 인접배열로 구성한다. 1. 상하좌우로 확장하면서 배추그룹을 만들면서 이동하면 된다. 2. dfs의 파라미터는 x, y 좌표를 넘겨준다. 3. 메인함수의 for문에서 1을 반견해서 dfs를 호출하면 새로운 그룹의 시작이므로 그때 count++를 해준다.. 2022. 8. 31. [백준] 1260번 - DFS와 BFS (Java)(○) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 무방향 그래프이다. 2. 방문할 정점이 여러개이면 작은 번호부터 방문하다. * DFS 1. 무방향 그래프를 표현하기 위해 vertex 배열을 사용한다. 2. DFS() 파라미터는 다음 방문할 정점 번호를 넘긴다. 3. DFS() 내부에서 for문으로 다음 방문 정점으로 확산한다. 4. 방문배열을 사용해서 방문할 정점은 스킵한다. 5. 간선이 아니면 (값이.. 2022. 8. 30. 이전 1 2 다음 반응형
