Preparing Coding Test114 [Java/프로그래머스/DFS] 타겟 넘버 문제 programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 코드 class Solution { static int answer; public void dfs(int index, int result, int[] numbers, int target){ if(index == numbers.length){ if(result==target) answer++; return; }else{.. 2020. 10. 19. [Java/프로그래머스/힙(Heap)] 더 맵게 문제 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 코드 모든 원소가 K보다 커야 한다고 해서 for문으로 검사를 했었는데, 생각해보니 우선순위 큐라서 제일 앞의 원소만 K보다 큰지 확인해주면 됐었다. import java.util.PriorityQueue; class Solution { public int solution(int[] scoville, int K) { //int answer = 0; Pri.. 2020. 10. 16. [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 7 8 ··· 13 다음