2025/2/25(화)https://www.acmicpc.net/problem/15649     🔑 풀이 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;// 실버 3public class Main { private static boolean[] used; private static int N, M; private static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedReader br = ..

Backtracking백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.가장 중요한 점은 제한 조건을 위배한다면 그 노드를 제외한다는 점이다,.현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다.DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요 없는 부분을 쳐내는 행위를 백트래킹(가지치기)이라고 생각하면 된다.DFS와 Backtracking의 다른점DFS..

2025/2/24(월)https://www.acmicpc.net/problem/14502벽을 어떻게든 가장 효율적으로 둬서 0의 개수를 최대한 많이 남겨야한다!벽을 세우는 방법을 알아서 생각해야된다. [접근 방법]벽을 어떻게 하면 효율적으로 세울 수 있을까?완전탐색으로 벽까지도 모든 경우의 수를 다 채워봐야한다.시간초과가 나지 않을까하는 불안이 있었지만 문제에서 주어진 조건인 세로 N, 가로 M 크기가 작다. 또한, 문제에서 시간 제한은 2초그래서 모든 벽을 세우는 경우는 64 x 64 x 64 = 1670만개 밖에 안 나온다. (새로 세울 수 있는 벽은 3개이며, 꼭 3개를 세워야한다) 너비 우선 탐색을 돌리면서 그 때 0의 개수를 세면 된다. 모든 경우의 수에 대해 0의 개수가 가장 많은 것을 출력하..

📝 문제 https://school.programmers.co.kr/learn/courses/30/lessons/132265 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr[설명]케이크를 1번 잘라서 토핑의 개수가 같아지는 개수 구하기 [접근 방법]topping 배열에서 중복되는 토핑이 있으므로 중복을 제거해주는 hashset을 활용해 구현배열 2개를 만들어 하나의 배열은 앞에서부터 탐색, 또다른 배열은 뒤에서부터 탐색 후대각선 비교를 해서 토핑의 개수가 같은 경우를 롤케이크를 공평하게 자르는 수(answer)에 포함하기하나의 롤케이크를 잘라서 비교를 하기 때문에 하나의 HashSet를 이용-> 중간에..