[백준] 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를 초과하면 새로운 구간 시작이렇게 나누어진 구간의 ..

[프로그래머스] 징검다리 📌 풀이 과정n개의 바위를 제거한 후에 만들 수 있는 "바위 사이의 최소 거리들 중 최댓값"을 구하는 문제이다.쉽게 말해, 바위를 제거해서 바위 사이 간격을 최대한 크게 두면서도그 중에서 제일 작은 가격이 얼마인지 구하면 된다.제거할 바위의 조합을 구해서 완탐으로 풀어도 될 것 같은데... 시간 초과가 난다 ㅇㅋ그렇다면 이 문제를 어떻게 이분탐색으로 풀 수 있을까..!!!먼저 왜 이분 탐색을 사용해야하는지 알아보자.왜 이분 탐색을 쓸까?0부터 도착점까지 모든 거리를 시도해보면 너무 오랜 시간이 걸리게 된다.중간값부터 시도하면서 범위를 절반씩 좁혀가는 게 효율적이게 된다.int low = 0 # 최소 간격의 가능한 최솟값 (바위 사이가 붙어있는 경우)int high = dist..

[SWEA] 2382. 미생물 격리 📌 풀이 과정미생물 군집의 정보를 입력받아 저장해야 하는데미생물 수가 큰 순서대로 정렬하도록 PriorityQueue를 사용한다.우선순위 큐를 사용하면서 두 개 이상의 군집이 한 셀에 모이는 경우는 미생물 수를 합치는 로직만 구현해주면 된다. 1. 매 시간마다 이동 후의 군집 상태를 저장하기 위해 map 배열을 초기화 한다.2. 각 미생물 군집을 꺼내서 현재 방향에 맞게 이동한다.3. 이동 후 군집 상태를 다시 우선순위 큐에 넣는다.이동 후, 격자의 경계에 도달하면 미생물 수를 절반으로 줄이고 이동 방향을 반대로 바꿉니다.이동한 위치에 다른 군집이 존재하면 미생물 수를 합칩니다.4. 이동 후의 군집 상태를 다시 우선순위 큐에 넣는다.  ✨ 제출 코드import jav..

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

[SWEA] 8275. 햄스터 📌 풀이 과정1. 각 우리에 0부터 X마리까지 가능한 햄스터 수를 배치하기 위해 중복 순열을 생성한다.2. (idx == N)이 되면 해당 순열이 경근이가 기록한 햄스터의 수에 모두 만족하는지 확인한다.3. 조건을 모두 만족하면 현재 배치된 총 햄스터 수를 계산해, 기존 최대 햄스터 수를 갱신한다.    조건을 하나라도 만족하지 못하는 경우 탐색을 종료하고, 다음 순열로 넘어간다. ✨ 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public clas..