minjoott-dev 님의 블로그

https://www.acmicpc.net/problem/17142 문제 파악연구소에 있는 비활성 바이러스 중 M개를 어떻게 골라서 활성 상태로 변경하여야, 가장 빠르게 모든 빈 칸으로 활성 바이러스를 전파시킬 수 있는지 알아낸다.✔️ 출력값: 모든 빈 칸에 활성 바이러스를 전파 시키는 데 걸리는 최소 시간. (단, 모든 빈 칸에 바이러스를 퍼뜨릴 수 있는 경우가 존재하지 않는다면 -1를 출력한다.)  문제 풀이Backtracking + BFSpackage main.java.Backjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class..

https://www.acmicpc.net/problem/14502문제 파악바이러스 확산을 최소화하기 위해 3개의 벽을 세울 위치를 찾아야 한다.그렇게 했을 때, 바이러스가 퍼지지 않는 안전 영역의 최대 크기를 return하라.  문제 풀이Backtracking + BFSpackage Backjoon;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class 연구소 { static int maxSafe = 0; // answer public static void main(String[] args) throws IOException { ..

https://leetcode.com/problems/permutation-sequence/description/ 문제 파악주어진 정수 n과 k에 대해, 1부터 n까지의 숫자로 만들 수 있는 모든 순열을 사전 순으로 정렬했을 때, k번째 순열을 return하기  문제 풀이순열 문제이므로, 백트래킹으로 구현한다.백트래킹class Solution { int cnt = 0; public String getPermutation(int n, int k) { return backtracking("", n, k); } String backtracking(String curr, int n, int k) { if (curr.length() == n) { ..

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java   문제 파악유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return하기  문제 풀이📌 완전탐색백트래킹을 사용하여 던전을 탐험할 수 있는 모든 순서를 살펴보고, 가능한 최선의 결과를 도출한다.백트래킹class Solution { static int ans = 0; public int solution(int k, int[][] dungeons) { backtracking(new boolean[dungeons...

https://leetcode.com/problems/word-search/ 문제 파악2차원 배열 board가 주어졌을 때, 동서남북으로 인접한 글자를 이어서 word를 만들 수 있다면 true를, 만들 수 없다면 false를 return하기 문제 풀이📌 완전탐색백트래킹백트래킹class Solution { public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i = n || nextX = m || nextY  📊 실행 결과  NO..

https://leetcode.com/problems/subsets/description/ 문제 파악중복되지 않는 정수들로 구성된 배열 nums가 주어졌을 때, 가능한 모든 부분집합을 return하기  문제 풀이📌 완전탐색백트래킹 (재귀)백트래킹class Solution { public List> subsets(int[] nums) { List> answer = new ArrayList(); backtracking(nums, 0, new ArrayList(), answer); return answer; } void backtracking(int[] nums, int startIdx, List curr, List> answer) { ans..

https://leetcode.com/problems/combinations/ 문제 파악두 개의 정수 n과 k가 주어졌을 때, [1, n] 범위의 숫자에서 k개의 숫자를 골라 가능한 조합을 모두 return하기 문제 풀이📌 완전탐색백트래킹 (재귀)백트래킹class Solution { public List> combine(int n, int k) { List> answer = new ArrayList(); backtracking(n, k, 1, new ArrayList(), answer); return answer; } void backtracking(int n, int k, int startNum, List curr, List> answer) { ..

https://leetcode.com/problems/permutations/ 문제 파악중복되지 않는 정수들로 구성된 배열 nums가 주어졌을 때, 가능한 모든 순열을 찾아 return하기 Constraints:1   문제 풀이📌 완전탐색백트래킹 (재귀)백트래킹class Solution { public List> permute(int[] nums) { List> answer = new ArrayList(); backtracking(nums, new ArrayList(), answer); return answer; } void backtracking(int[] nums, List curr, List> answer) { if (curr.si..

https://leetcode.com/problems/two-sum/description/?source=submission-ac 문제 파악더해서 target값을 가지는 두 요소값의 인덱스를 return하기주어진 input 값을 오직 하나의 솔루션만 가진다.같은 요소를 솔루션으로 가질 수 없다.Constraints:2 nums.length  문제 풀이📌 완전 탐색반복문백트래킹 (재귀)정렬 & 투포인터해시맵반복문class Solution { public int[] twoSum(int[] nums, int target) { for (int i = 0; i  📊 실행 결과Worst Case Time Complexity: 10^8  재귀class Solution { pub..