코테/백준

📖 문제 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..

📖 문제  2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net   💡  풀이 방식• DPDP[K][N] : 숫자 K개를 사용해 N을 만들 수 있는 경우의 수 1. 초기화숫자 K개로 0을 만드는 경우의 수는 항상 1개이다.for(int i = 1 ; i   2. 점화식 찾기표를 그리다 보면, 한 칸은 해당 칸의 위쪽 값과 왼쪽 값을 합한 값으로 채우는 규칙을 발견할 수 있다.그렇기 떄문에 점화식이 아래와 같이 성립된다. for(int i = 1 ; i     🔺 코드1234567891011121314151617181920212223242526272829import java.io.*; public class Main {    static f..

📖 문제  17141번: 연구소 2인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS필요 자료구조- 인접한 4방향 칸 탐색용 dx/dy 배열- BFS용 방문 표시용 2차원 boolean형 배열- 바이러스 위치 저장용 리스트 virusList- 뽑은 바이러스 M개 저장할 임시 리스트 tmpList  1. 연구소 정보를 저장하면서, 바이러스 위치도 저장한다.2. 조합(DFS)으로 바이러스 위치들 중 M개를 뽑아 뽑은 칸에서 BFS 탐색을 통해 바이러스를 퍼뜨리는 시간을 계산한다. [바이러스 위치들 중 ..

📖 문제 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 풀이 방식 • BFS + 시뮬레이션 1. 배열을 시계 방향으로 90도 회전시킨다. (그림 참고) private static void rotate(int r, int c, int v, int[][] tmp) {// tmp : 회전 후 값 저장용 배열 for(int i = 0 ; i < v; i++) { for(int j = 0 ; j < v ; j++) { tmp[r + i][c + j] = A[r + v - 1 - j][c + i]..