본문 바로가기

전체 글158

[백준] 7578번: 토마토 (Java) 1. 문제설명토마토는 격자 모양 상자의 칸에 하나씩 보관된다. 익은 토마토의 인접한(상하좌우) 곳에 있는 익지 않은 토마토들만 익은 토마토의 영향을 받아 익게 된다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제이다.만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력, 토마토가 모두 익지 못하는 상황이면 -1을 출력한다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식⇒ 모든 토마토가 익는 최소 시간을 구하는 문제 → BFS토마토 정보를 담은 `int[][] box`를 사용한다.상하좌우로 이동할 수 있는 배열(dx, dy)을 사용한다.익은 토마토를 큐에 추가한다. (위치 정보)큐가 빌 때까지큐에서 값을 꺼내, 이 위치의 상하좌우를 탐색한다. (`.. 2024. 8. 13.
[백준] 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.
반응형