본문 바로가기

분류 전체보기154

[백준] 6603번: 로또 (Java) 1. 문제설명1~49의 숫자 중에서 k(k>6)개의 수를 골라 집합S를 만들었을 때, 이 집합S에서 6가지 수를 고르는 경우를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식⇒ 모든 조합 구하기 (모든 경로 방문) → DFSDFS를 사용해서 가능한 모든 6개의 조합을 생성한다.메서드를 재귀 호출하며, 6개가 선택되면 그 조합을 저장한다.StringBuilder를 사용해 조합을 저장하고, 출력한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int[] arr = new int[6]; // 선택된 조합을 저장할 배열 static int[] nums; // 입력받은 숫자 집합 stat.. 2024. 8. 12.
[백준] 2606번: 바이러스 (Java) 1. 문제설명한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 감염된다. 1번 컴퓨터가 웜 바이러스에 걸렀을 때, 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식⇒ 네트워크 연결 → DFS노드의 수와 간선 정보를 인접행렬로 저장한다.방문 체크할 visited 배열을 생성한다.재귀 호출하는 메서드를 통해 1번과 연결된 컴퓨터를 찾는다.탐색할 노드 번호(row)를 매개변수로 받는다.행렬에서 해당 row를 탐색하며 col이 1이고, 방문하지 않은 경우count 1 증가 (결과값)해당 col로 재귀 호출 3. 최종 코드import java.io.*;public class Main { static int.. 2024. 8. 12.
[백준] 5568번: 카드 놓기 (Java) 1. 문제설명각 카드에 1이상 99 이하의 정수가 적혀져 있고, 상근이는 n장(4 ≤ n ≤10)장을 가지고 있다.그 중에서 k개를 선택해서 카드를 조합하여 만들 수 있는 정수의 개수를 구하는 문제이다.시간 제한: 1초메모리 제한: 256M 2. 접근 방식조합된 값 저장 시 중복된 값이 저장되지 않도록 HashSet을 사용한다.백트래킹 방법을 하여 가능한 정수 조합을 탐색한다.현재 카드를 고른적이 있는지 방문 체크한다. (visited[현재위치]가 alse인지)고른 카드 수(count)를 1 증가시키고, 현재까지 만들어진 조합에 현재 카드를 추가해서 재귀 호출한다.만약 현재 고른 카드 수(count)가 k이면 현재 조합을 HastSet 추가하고 리턴한다.리턴된 다음에는 방문 처리를 취소한다. (백트래킹).. 2024. 8. 9.
[백준] 17626번: Four Squares (Java) 1. 문제설명모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다.ex) 26은 5^2 + 1^2 또는 4^2 + 3^2 + 1^2자연수 n이 주어질 때, n의 제곱수 합이 최소 개수가 되는 값을 구하는 문제이다.시간 제한: 0.5초메모리 제한: 512MB 2. 접근 방식DP 방식을 사용한다. dp 배열을 사용한다. dp[i]는 숫자 i를 4개 이하의 제곱수 합으로 표현할 때 필요한 제곱수의 최소 개수를 저장한다.dp[0] = 0, dp[1] = 1로 초기화한다. 0은 제곱수가 필요 없고, 1은 1^2 하나로 표현 가능하기 때문이다.2부터 n까지 모든 숫자 i에 대해:i보다 작거나 같은 모든 제곱수(j*j)에 대해 검사한다.i에서 제곱수(j*j)를 뺀 나머지(temp)에 대한 dp 값 중 최.. 2024. 8. 9.
[백준] 22864번: 피로도 (Java) 1. 문제설명하루 한 시간 일하면 피로도가 A만큼 쌓이고 일은 B만큼 할 수 있다.만약 한 시간을 쉰다면 피로도는 C만큼 줄어든다. 피로도가 음수가 되면 0으로 바뀐다.피로도를 M이 넘지 않고 하루에 최대 일할 수 있는 시간을 구하는 문제이다.(하루는 24시간, 맨 처음 피로도는 0)시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식=> 완전탐색 방법으로 1부터 24(하루)까지 일한 경우와 하지 않은 경우의 피로도를 계산한다.for문으로 1부터 24까지(하루)한 시간 일했을 때의 피로도를 계산하여 (next)next가 최대 피로도 M보다 작거나 같으면 결과값에 B를 더하고, 피로도를 A만큼 증가시킨다.next가 최대 피로도 M보다 크면 피로도를 C만큼 감소시킨다.만약 C만큼 감소시킨 피로도가 음수.. 2024. 8. 8.
[백준] 18511번: 큰 수 구성하기 (Java) 1. 문제설명N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 문제이다.ex) N=657이고, K={1, 5, 7}일 때 답은 577시간 제한: 1초메모리 제한: 256MB 2. 접근 방식=> 재귀함수를 이용해 모든 가능한 숫자를 조합하여, (완전탐색) N보다 작거나 같은 가장 큰 수를 찾는다.K의 원소를 배열에 저장하고, 오름차순 정렬한다.재귀를 사용해서 주어진 원소를 조합해 가능한 모든 수를 만든다.만들어진 수가 n보다 크면 종료한다.만들어진 수가 n보다 작거나 같은 경우 중 최대값을 찾는다.배열을 역순으로 탐색한다. (큰 수부터 만들기 위해) 3. 최종 코드import java.io.*;import java.util.*;public class Main { s.. 2024. 8. 8.
[백준] 19532번: 수학은 비대면강의입니다 (Java) 1. 문제설명$$ ax + by = c \\ dx + ey = f $$위 연립방정식에 대한 정수 $a, b, c, d, e, f$가 주어졌을 때, $(-999 ≤ a, b, c, d, e, f ≤ 999)$ 문제의 답인 $x$와 $y$를 구하는 문제이다.시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식=> 완전탐색을 사용하여 x와 y에 -999부터 999까지 대입하여 해를 구한다.2중 for문을 이용해 x와 y에 -999부터 999까지의 수를 대입한다.두 개의 연립방정식에 맞으면 x와 y를 출력하고 프로그램 종료한다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] .. 2024. 8. 7.
반응형