IT_공부하자

[JAVA] 백준 1068 트리_트리

문제 : https://www.acmicpc.net/problem/1068 접근 :    - 입력 받은 수를 배열에 넣는다.   - 지워야할 수를 저장한 후, 입력 받은 배열로 그래프를 만든다.  - 만약 배열의 인덱스나 배열의 값이 지워야할 수 이라면 그래프로 만들지 않고 다음 수로 넘어간다.  - root 와 지워야할 수가 같다면 0을 출력, 다르면 root 부터 리프노드의 수를 DFS 로 계산한다.  - 탐색이 끝나면 리프노드 수를 출력한다.  코드 구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.H..

[JAVA] 백준 11725 트리의 부모 찾기_트리

문제 : https://www.acmicpc.net/problem/11725  접근 :    - 입력되는 정보로 그래프를 작성   - 루트가 1 이므로 DFS를 통하여 1부터 인접한 노드의 부모 노드를 현재 수로 등록한다.   - 만약 인접 노드가 자신의 부모 노드일 경우 DFS를 실행하지 않는다.   - 부모 노드를 모두 등록하면 2부터 자신의 부모 노드를 출력한다.    코드 구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { private static ArrayList[] adj; pri..

[JAVA] 프로그래머스 단속카메라_최소힙

문제 :https://school.programmers.co.kr/learn/courses/30/lessons/42884  접근 :   - 끝을 기준으로 최소힙에 넣는다.  - 한개 씩 차례대로 빼면서 다음의 시작 지점이 이전의 끝지점보다 큰 경우 끝지점을 갱신하고 정답에 1을 추가한다.  - 끝까지 진행 후 결과값을 출력한다.    코드 구현 :   import java.util.Collections;import java.util.PriorityQueue;class Solution { private static class Car implements Comparable{ int route_in; int route_out; public Car(int route_i..

[JAVA] 백준 2688 줄어들지 않아_DP

문제 :https://www.acmicpc.net/problem/2688  접근 :   - n = 1,  dp[1] = 10, before = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}  - n = 2, dp[2] = 10 - 0 + 10 - 1 + 9 - 1 + · · · + 2 - 1 , before = {0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}  - n = 3, dp[3] = 55 - 0 + 55 - 10 + 45 - 9 + · · · + 2 - 1, before = {0, 55, 45,  36, 28, 21, 15, 10, 6, 3, 1} 즉 dp[n] = dp[n-1] - before[0] + (dp[n-1] - before[0]) - before[1] + ..

백준 9465 스티커_DP

문제 : https://www.acmicpc.net/problem/9465  접근 :   - 위쪽을 뜯는 경우와 아래쪽을 뜯는 경우를 나눠서 생각한다.  - 가로의 위치가 0 과 1 인 경우에는 나올 수 있는 최대값을 dp에 저장한다.  - 가로의 위치가 2 이상인 경우에는 위쪽과 아래쪽을 나눠서 현재 위치까지 도달했을 때, 가능한 최대값을 dp에 저장한다.  - 가로로 진행할 때, 항상 위쪽과 아래쪽을 나누어 더 큰 값으로 ans 값을 갱신한다.  - n-1 까지 진행한 후, ans 값을 출력한다.       코드구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public clas..

문제 :https://www.acmicpc.net/problem/1520  접근 1:   - BFS 로 결과 지점까지 도달하면 결과값 + 1  - Queue 가 빌 때까지 실행 후 출력  - 메모리 초과로 불가  접근 2:  - DP 와 DFS 를 이용하여 정답을 카운트  - 정답 지점까지 도달한 후, 시작 지점으로 돌아오면서 count 를 증가  - 시작 지점에 도달하면 count를 정답으로 출력  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static int[][] map; private static int[]..

문제:https://www.acmicpc.net/problem/2193  접근 :   - 1자리 수의 경우 = 1  - 2자리 수의 경우 = 10  - 3자리 수의 경우 = 100, 101  - 4자리 수의 경우 = 1000, 1010, 1001  - 5자리 수의 경우 = 10000, 10100, 10010, 10001, 10101  - n자리 수의 경우 = n-1 자리 수의 경우 + 0, n-2 자리수의 경우 + 01    -> DP[n] = DP[n-1] + DP[n-2]  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public ..

문제 : https://www.acmicpc.net/problem/2156  접근 :   - 마지막 포도주를 마시는 경우와 마시지 않는 경우를 나눈다.  - 만약 마지막 포도주를 마시지 않는 경우, 1) 이전까지(n-1)의 최대값이 정답이다.  - 마지막 포도주를 마시는 경우, 2) 3번째 전(n-3) 최대값에 전 포도주 잔(n-1)과 이번 포도주 잔(n)을 마실 수 있다.  - 또한, 3) 2번째 전(n-2) 최대값에 이번 포도주 잔(n)을 마실 수 있다.  - 1) 2) 3) 3가지 경우 중 최대값을 정답으로 출력한다.    코드 구현 :import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;pu..

문제:https://www.acmicpc.net/problem/2011  접근 :   - 0 으로 시작하는 숫자가 들어오면 복호화가 불가능 하므로 0을 출력한다.  - 길이가 2이상인 경우에는 복호화 한 수가 26 이하이면 2, 6 개별 수 및 26 합친 수의 경우 모두를 고려한다.  - 첫 번째 글자부터 끝까지 확인하면서 정답을 구한다.  코드 구현 : import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br ..

문제:https://www.acmicpc.net/problem/11052  접근 :   - 카드를 최댓값으로 N개 구매하기 위해서는 1 부터 N까지 구매 최대값을 알고 있어야한다.  - 카드 1개를 살때 최대값 (dp[1])은, card[1]이 최대값이다.  - 카드 2개를 살때 최대값 (dp[2])은 , card[1]을 2번 구매하는 값과 card[2] 중 더 큰 값이다.  - dp[3] 은, dp[1] + dp[2] 과 card[3] 중 더 큰 값이다.  - dp[4] = dp[1] + dp[3] , dp[2] + dp[2], num[4] 중 가장 큰 값이다.  - dp[5] = max { (dp[1] + dp[4]), (dp[2] + dp[3]), (card[5]) }   - dp[n] = max{..