전체 글

📖 문제 https://www.acmicpc.net/problem/3019   💡  풀이 방식• 구현, 브루트포스 1. 블록 모양에 따라 올라와야 하는 바닥면의 높이를 저장한다.2. 바닥면에 대해 블록을 끝까지 내릴 수 있는지 반복문으로 검사한다. ⇒ 각 번호에 맞는 빈 공간 수를 뺐을 때 모두 같은 값이 나오면 놓을 수 있는 자리이다!! (참고)    🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152import java.util.*;import java.io.*; public class Main {    static int C,P;    static int[] map; ..

📖 문제 https://www.acmicpc.net/problem/16509  💡  풀이 방식• BFS 필요 자료구조- 상하좌우 이동용 dx/dy배열- 대각선 이동용 cx/cy 배열- 탐색 위한 BFS용 큐- 좌표 방문 표시용 2차원 boolean형 배열  상 위치에서부터 BFS를 시작해 왕에게 도달하는 횟수를 구한다.- 만약 현재 큐에서 뽑은 위치값이 왕의 위치와 같다면, 여태 구한 이동 횟수를 출력한다.- 그렇지 않다면, 경로가 막혔는지 판단하며 탐색을 진행한다.   ㄴ 먼저 상하좌우 방향으로 한 칸 이동한다.   ㄴ 마저 이동 가능한 경우, 상하좌우 움직임에 따라 방향을 2개씩 매칭한 후 해당 방향으로 확산시키며 이동 횟수를 갱신한다.// 경로가 막혀있는지 판단용 함수private static ..

📖 문제 https://www.acmicpc.net/problem/15683  💡  풀이 방식• 시뮬레이션 + 백트래킹 + 브루트포스  각 CCTV의 타입을 받아, 각 타입에 맞춰 회전된 상태를 조합해 사각지대의 최소값을 구한다.CCTV 타입이 1( → )인 경우 : 북(0 / ↑), 남(1 / ↓), 서(2 / ←), 동(3 / →)CCTV 타입이 2( ↔ )인 경우 : 서동(23 / ↔), 북남(01 / ↕ )CCTV 타입이 3(↑→)인 경우 : 북동(03 / ↑→) , 남동(13 / ↓→) , 남서(12 / ↓←) , 북서(02 / ←↑)CCTV 타입이 4( ←↑→ )인 경우 : 북서동(023), 북남동(013), 남서동(123), 북남서 (012)CCTV 타입이 5(↕↔)인 경우 : 북남서동(..

📖 문제 https://www.acmicpc.net/problem/1967  💡  풀이 방식• DFS (트리)1. 2차원 인접 리스트 배열을 만들어 정보를 입력받는다. (양방향으로!)2. 1~N번의 모든 노드에서 DFS를 수행해 거리(가중치들의 합 = 트리의 지름)를 계산한다.for(int i = 1 ; i     [DFS 함수]현재 정점과 연결된 모든 점을 방문하며 가중치를 더하고, 이를 최댓값과 비교해 정답을 가장 큰 값으로 갱신한다.private static void dfs(int idx, int sum) { answer = Math.max(answer, sum); for(Node next : list[idx]) { if(!visited[next.idx]) { ..

📖 문제 https://www.acmicpc.net/problem/16937   💡  풀이 방식• 브루트포스1. 입력되는 정보들을 저장한다.2. 모든 스티커들에서 2개를 붙이는 경우를 탐색해 최대 넓이를 구한다.  - [스티커1 붙이기] 항상 (0,0)을 기준으로 붙인다. (목적: 다음 스티커를 붙일 수 있는 최대 칸을 남기기 위해)3. 최대 넓이를 구하면 결과로 출력하고, 못 구하면 0을 결과로 출력한다.   🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384..

📖 문제 https://www.acmicpc.net/problem/12872  💡  풀이 방식• DPDP[ i ][ j ] : i개의 음악을 플레이리스트에 넣고, j개의 음악 종류를 사용했을 때의 경우의 수 어떤 집합에서 아무거나 하나를 놓으면 된다= 어떤 집합의 원소의 수를 곱한다  음악은 플리(플레이리스트)에 넣었는지 여부에 따라 2가지 종류로 나눌 수 있다. 1) 플리에 넣지 않은 음악인 경우  - 아직 플리에 넣지 않았으므로, 같은 노래 사이에 M개의 곡이 있어야 한다는 2번 조건은 고려할 필요가 없다.  - 대신 이전 모든 경우의 수들에 추가될 수 있으므로 아래와 같은 점화식이 도출된다.dp[musicNum][savedMusicNum] += dp[musicNum - 1][savedMusicN..

📖 문제 https://www.acmicpc.net/problem/11066   💡  풀이 방식• DPDP[ from ][ to ] : from ~ to번째 챕터를 합쳤을 때 최솟값 3중 반복문을 통해 DP[1][2] ~ DP[1][K]까지의 최소 비용 값을 구한다.  private static void solve(int k) { for(int to = 2 ; to = 1 ; from--) { // 출발지 (어디서부터 묶을건지) dp[from][to] = Integer.MAX_VALUE; for(int x = from ; x    🔺 코드1234567891011121314151617181920212223242526272829303132333435363..

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제   10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net   💡  풀이 방식• BFS 일반인과 적록색약의 경우를 나눠서 BFS를 수행한다.1) 일반인의 경우, RGB를 3색을 각각 다르게 본다. R구역과 G구역과 B구역으로 나뉜 구역 수를 구하는 BFS를 수행한다.visited1 = new boolean[N][N];for(int i = 0 ; i private static void bfs1(int x, int y, char c) { Queue q = new ArrayDeque(); q.ad..