[백준] 1285. 동전 뒤집기 📌 풀이 과정동전의 상태가 앞(H), 뒤(T) 2가지 뿐이기 때문에 각 위치를 2진수로 표현이 가능하다.H = 0, T = 1로 설정하고 문제를 풀었다.그리고 각 행과 열은 뒤집느냐, 뒤집지 않느냐 두가지 경우로 나눠지기에행을 먼저 완전탐색한 이후에, 열 기준으로 T의 갯수를 카운트해 뒤집을지 말지 판단을 하면 된다. 1. 동전 상태를 비트로 저장N개의 행을 정수 배열 coin[]에 저장해서 각 행을 하나의 N비트 정수로 표현했다.예를 들어 `HTT(앞면, 뒷면, 뒷면)`인 경우H → 0T → 01T → 011 (2진수) = 3 (10진수) 2. 행을 뒤집는 연산비트를 사용하기 때문에 행을 뒤집는다는 것은 각 비트를 반전시키는 것과 같기 때문에  NOT 연산 `~`을 사..

[백준] 12869. 뮤탈리스크 📌 풀이 과정처음엔 완전 탐색으로 풀 수 있겠지? 하는 생각에 풀었다가 시간 초과가 떴다.알고리즘 유형을 확인해보니.... DP를 활용한 BFS 로직을 작성해야 함을 깨달았다...더보기기존 완탐으로 작성한 코드는 시간 초과!!!!제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main{ static int N, min; static int[] SCV; static Li..

[백준] 1520. 내리막길 📌 풀이 과정DFS로 4방향 + 내리막길로만 탐색하고, 백트래킹으로 풀었지만네 어김없이 시간초과가 뜬다.시간복잡도를 고려하는 방법에 대해서 공부할 필요가 있음을 느낀다..DFS로 모든 가능한 경로를 탐색한다.But, 이미 계산한 위치의 경로 수를 재사용하여 중복 계산을 방지해야 한다.`dp[x][y]` = 현재 위치(x, y)에서 도착지점(M-1, N-1)까지의 경로의 수`dfs(x, y)` = 현재 위치(x, y)에서 출발하여 도착점까지 가는 경로의 수를 반환한다. (0, 0)에서 시작해 가능한 모든 내리막길로 이동한다.아직 계산되지 않은 위치인 경우 DFS를 통해 경로를 계산한다. `dp[x][y] == -1`이미 계산된 곳으로, 해당 위치에서 가는 경로 수를 재사용한다..

[백준] 1074. Z 📌 풀이 과정 초기 접근 방식2^(N-1) × 2^(N-1) 크기의 2차원 배열을 만들어서 Z순서를 기록하고 (r,c)의 값을 찾는 방식으로 접근했다.하지만 N = 15인 경우, 2^14 × 2^14 크기의 배열이 필요하기 때문에 메모리 초과가 발생했다.하하!!! 크리스마스 이브날에 푼 문제라 그런지 어떻게 재귀로 이끌어내야 할지 머리가 안돌아갔다... 분할 정복N = 2 인 경우0123 N = 3 인 경우0145236789121310111415 N = 4 인 경우 N이 1 커질 때마다 사분면의 크기는 2배씩 커지고배열을 4등분한 각 사분면은 이전 크기의 Z 방문 순서를 그대로 따른다는 것을 알 수 있다. 1. 현재 좌표 (r, c)가 어느 사분면에 위치하는지 계산한다.r와 c ..

[백준] 2096. 내려가기📌 풀이 과정3개의 열과 N개의 행으로 이루어진 숫자판이 주어진다.맨 윗줄에서 시작하여 맨 아랫줄로 내려오면서 합계의 최댓값과 최솟값을 구해야 한다.단, 한 칸 아래로 이동할 때, 같은 열 또는 인접한 열로만 이동 가능하다.처음에는 각 열에서 이동 가능한 경우의 수를 모두 고려한완전 탐색으로 코드를 작성했지만.. 시간 초과가 떴다...완전 탐색으로 풀면 3^N의 연산을 해야 하며, 이는 시간 제한(1초) 내에 처리할 수 없는 연산량이었다.따라서, DP를 사용해야 한다!!!! 🥹디피.. 싫어.... ❤️‍🔥 점화식최댓값과 최솟값을 각각 계산해야 하기 때문에 두 개의 DP 배열을 사용했다.maxD[x][y]: x행, y열까지 내려왔을 때 얻을 수 있는 최대 합minD[x][y..

[백준] 13397. 구간 나누기 2📌 풀이 과정배열을 M개 이하의 구간으로 나눌 때, 각 구간의 점수(최댓값-최솟값)의 최댓값 중 최솟값을 구하는 문제다.이 문제도 이분 탐색을 활용하는 문제인건 파악했으나.. 코드 작성하기 까지 조금 헤맸다. 이분 탐색을 활용하는 이유구하고자 하는 것이 최댓값의 최솟값특정 값으로 가능한지 여부를 판단할 수 있다. (Yes/No 문제)값이 커질수록 구간을 M개 이하로 나누기 쉽다.이분 탐색 범위최소값: 0 (구간의 점수가 가질 수 있는 최솟값)최대값: 배열의 최댓값 - 최솟값 (전체 배열에서 가능한 최대 점수) 판단 방법mid값을 구간의 최대 점수라 하자.배열을 순회하면서 현재 구간의 점수(최댓값 - 최솟값)이 mid를 초과하면 새로운 구간 시작이렇게 나누어진 구간의 ..

[백준] 16236. 아기상어비슷한 유형으로 [SWEA] 2382. 미생물 격리 문제를 추천! 📌 풀이 과정처음 아기 상어 위치에서 BFS를 수행해 아기상어의 크기보다 작은 물고기를 찾는다.1. 거리가 가장 가까운 물고기2. 거리가 같다면 가장 위쪽에 위치한 물고기3. 위쪽까지 같다면 가장 왼쪽에 위치한 물고기현재 먹을 수 있는 물고기에 대한 탐색이 끝나면 아기상어는 이러한 우선순위로 물고기를 선택해야 하는데우선순위에 따라 쉽게 선택하기 위해서 PriorityQueue를 사용한다. 다음으로, 물고기를 먹을 때마다 아기 상어의 물고기를 먹은 횟수를 증가시키고,크기 조건이 맞다면 아기상어의 크기를 증가시킨다. ✨ 제출 코드import java.io.BufferedReader;import java.io.IO..

[백준] 2636 치즈2636. 치즈 - 골드4📌 풀이 과정 외부 공기 (0,0) 위치를 시작점으로 bfs 탐색을 시작한다.현재 탐색할 대상인 위치가 1. 공기인 경우(0)큐에 넣어 다음 탐색에서도 이 공기와 연결된 좌표를 계속해서 탐색해 나갈 수 있도록 한다. 2. 치즈인 경우(1)탐색 중 이 좌표가 치즈라면, 외부 공기와 접촉한 것이므로 녹여야 한다.치즈를 공기(0)로 바꾸어 녹인 뒤, 남은 치즈 개수를 감소 시킨다. cheese--여기서 중요 포인트!!!녹인 치즈는 큐에 넣지 않는다.큐에 넣게 되면 새로 녹은 공기가 내부 공기와 접촉할 위험이 있기 때문에안쪽에 있는 치즈가 의도치 않게 녹을 수 있다.  ✨ 제출 코드package beakjoon;import java.io.BufferedReader..

[백준] 17472. 다리 만들기 2 📌 풀이 과정문제를 읽고 풀 엄두가 나지 않는다면 시리즈 1부터 푸는 것을 추천합니다..[백준] 2146. 다리 만들기 이 문제는 여러개의 섬을 다리로 연결해 하나의 연결된 그래프를 만들고, 그 총 다리 길이의 최소값을 찾는 최소 신장 트리(MST) 문제이다. BFS를 통해 각 섬을 구분한 후 섬 사이에 연결 가능한 다리를 계산한다. 최소값이 될 수도 있는 다리들을 우선순위 큐에 저장한 다음, 크루스칼 알고리즘을 통해 MST를 구현해 모든 섬이 하나로 연결되도록 하면 된다. 문제 조건1. 다리의 방향이 바뀌면 안된다. 무조건 가로 or 세로2. 다리의 길이는 2 이상이어야 한다.모든  섬을 연결하는 다리 길이의 최솟값을 구해야 한다. 입력 값에서 섬은 모두 1로 ..

[백준] 17136. 색종이 붙이기 📌 풀이 과정큰 색종이를 먼저 붙이는 것이 효율적이므로큰 색종이로 덮을 수 있는 범위를 줄이고, 남은 작은 영역에 더 작은 색종이를 붙이도록 해야한다.그리고 색종이를 붙이는 과정에서 잘못된 선택일 경우, 다시 돌아와서 더 작은 색종이를 붙이는 로직이 필요하다.즉, 색종이를 붙이는 순서에 따라 최종 결과가 달라지기 때문에 모든 경우를 시도하는 백트래킹이 필요하다. 1️⃣ DFS 탐색(x, y) 좌표에서 색종이를 붙이면서 최소한의 색종이를 찾기 위해 재귀적으로 탐색한다.기저 조건: x >= 10에 도달하면 모든 칸을 탐색한 것이므로, 사용한 색종이 개수(usedPapers)를 최솟값으로 갱신한다.(y >= 10)일 때는 한 행을 다 탐색한 것이므로 다음 행으로 이동한다...