Preparing Coding Test/Baekjoon49 [Java/백준/우선순위 큐] 11279번: 최대 힙, 1927번: 최소 힙 자바의 우선순위큐 라이브러리에 원소를 담고 다시 빼면, 우선순위는 오름차순으로 정렬되어 나온다. 따라서 최대 힙을 구현하려면 우선순위 큐를 선언할 때, 매개변수로 Collections.reverseOrder()를 넣어주면 된다. www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net import java.util.*; import java.io.*; class Main{ public static void main(String[] args) thro.. 2020. 11. 25. [Java/백준/BFS] 1389번: 케빈 베이컨의 6단계 법칙 문제 www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 코드 BFS로 풀었다. import java.util.*; import java.io.*; class Main{ static ArrayList[] adjacent; static int users; public static int addCnt(int[] visited) { int sum = 0; for(int e : visited) { //System.out... 2020. 11. 23. [Java/백준/DP] 1010번: 다리 놓기 문제 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 코드 1(DP를 사용하지 않는 방법) 조합 공식을 그대로 사용했다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; class Main{ public static void .. 2020. 10. 16. [Java/백준/DP] 1463번: 1로 만들기 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 매번 새 유형 나오면 모르쇠,,,,, 슬프다. 우선 초기값, Working-backward는 dp[0]과 dp[1]은 연산을 하지 않아도 되므로 0이다. N==2 : N/2를 하거나 N-1를 하면 바로 1이 된다. → 연산 결과 1번 N==3 : N/3을 하면 바로 1이다 → 연산 결과 1번 N==4 : 3가지 경우의 수를 고려한다. ① N-1 N-1을 하면 N=3 → N/3=1 (연산 결과 2번) ② N/2 N/2를 하면 N=2 → N/2=1 (연산 결과 2번) ③ N/3 N%3!=0 이므로 연산 불가능 ①, ②.. 2020. 10. 5. [Java/백준/DP] 2579번: 계단 오르기 문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 참고 www.youtube.com/watch?v=EKHFu9vB-Oc 문제에 대한 풀이는 아니지만 계단오르기 문제 유형에 대한 감을 잡기에 좋았다. 코드 한칸 또는 두칸을 이동하는 것, 최댓값을 구하는 것은 어렵지 않았지만 연속된 세 개의 계단을 밟으면 안된다는 조건이 까다롭다ㅠ 가장 마지막 계단 N번째 계단으로 생각해본다. 그 전의 N-1번째 계단을 밟고 올라왔는지, N-2번째 계단을 밟고 올라왔는지로 나눠 계산할 .. 2020. 10. 5. [Java/백준/DP] 1932번: 정수 삼각형 문제 www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 한 줄과 그 위의 줄만을 생각한 점화식을 세웠다. 0 0 0 0 0 0 ← i=0 0 7 0 0 0 0 ← i=1 0 3 8 0 0 0 ← i=2 0 8 1 0 0 0 ← i=3 0 2 7 4 4 0 ← i=4 0 4 5 2 6 5 ← i=5 == N ↑ ↑ j=0 j=5 입력값을 받는 배열이 triangle, 최대값이 들어가는 배열이 max_triangle이라 할 때, max_triangle[i][j] 에 들어가는 배열을 생각하면 1) 윗 줄의 양 대각선 위치의 max_.. 2020. 10. 4. [Java/백준/DP] 1149번: RGB거리 문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 코드 나한테 미지의 세계인 문제였다.... DP는 문제 맞닥뜨릴 때마다 이게 뭔데 하게 됨 ㅠ 코드는 아래 링크를 참고했다. m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료) 문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문.. 2020. 10. 2. [Java/백준/DP] 9461번: 파도반 수열 문제 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 � www.acmicpc.net 코드 n==1일 때 부터 5까지는 예외이다. → 따로 Basic case인 걸로 했다. 그 이후 점화식은 D(n) = D(n-1) + D(n-5) 이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Outp.. 2020. 10. 1. [Java/백준/DP] 1904번: 01타일 문제 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 코드 IDE에서는 StackOverflowError가 나오지만 백준에서는 정답 뜨는 마성의 코드... DP에 대해 감을 잘 못 잡아서 동빈나 유튜브로 미리 공부하고 시작했다. 내가 생각한 풀이 방법은 Basic case에 대해서 생각한다. (이 코드에선 n이 1, 2일 때) : 재귀함수를 끝내는 역할 값들을 중간 중간 저장해주는 역할의 배열 (dp_arr) : 구한 값을 배열에 저장해주었을 때, 그 값을 다.. 2020. 10. 1. 이전 1 2 3 4 5 6 다음