본문 바로가기

dp60

백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.
백준 14002 자바 - 가장 긴 증가하는 부분 수열 4 (BOJ 14002 JAVA) 문제 : boj14002 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘에 대한 설명은 생략하고, 가능한 수열을 찾는 방법에 대해 설명한다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제 정답은 '10 20 30'이므로 LIS 알고리즘 자체만 사용해서는 원하는 실제 수열을 출력할 수 없다. 2. 추가로 배열을 더 사용해서 .. 2021. 12. 21.
백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA) 문제 : boj2806 1. 문자를 하나씩 보면서 전부 A, 혹은 B로 변경해 나간다고 생각해보자. 그렇다면 8가지 경우가 나온다. case1. 현재 문자는 A, 이전까지 전부 A 였음, 전부 A로 유지할 것임 -> 이전 상태에 그냥 A를 붙이면 된다. (돌연변이 +0) case2. 현재 문자는 A, 이전까지 전부 A 였음, 전부 B로 유지할 것임 -> 이전 상태에 그냥 A를 붙인 후, 전체를 B로 변경한다. (돌연변이 +1) case3. 현재 문자는 A, 이전까지 전부 B 였음, 전부 A로 유지할 것임 -> 이전 상태 전체를 A로 변경하고 A를 붙인다. (돌연변이 +1) case4. 현재 문자는 A, 이전까지 전부 B 였음, 전부 B로 유지할 것임 -> 현재 문자를 B로 변경해서 붙인다. (돌연변이 +.. 2021. 12. 19.
백준 4781 자바 - 사탕 가게 (BOJ 4781 JAVA) 문제 : https://www.acmicpc.net/problem/4781 유명한 DP 활용 문제 유형인 냅색(knapsack) 문제이다. '각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.'라는 부분 때문에 냅색에서 난이도가 좀 낮춰지지만, 가격이 실수라서 난이도가 다시 높아진다 ㅋㅋㅋ 결국 실수만 잘 처리할 수 있으면 DP를 사용해 풀 수 있다. 그래도 양심이 있는지 소수점 두번째 자리까지만 주어지고, 최대 100.00 이라서 그냥 100을 곱해서 처리하면 된다. 소수점을 처리할 방법들중 몇가지는 다음과 같다. 1. 주어진 실수에 100을 곱한다. -> 주의점은 입력받은 실수에 100을 곱한 후 +0.1 정도를 해줘서 소수점 오차를 없앤 후 int형으로 형변환 해야한다. 안전.. 2021. 11. 23.
백준 1003 자바, 파이썬, C# - 피보나치 함수 (BOJ 1003 JAVA, Python, C#) 문제 : https://www.acmicpc.net/problem/1003 코드(자바) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.java 코드(파이썬) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.py 코드 (C#) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.cs Memoization 개념에 대해 익힐 수 있는 아주 좋은 문제이다. 피보나치의 경우 문제에 제시된 기본적인 방식으로 짜게 되면 재귀적으로 호출되는 함수.. 2021. 10. 29.
백준 23046 자바 - 큰 수 뒤집기 (BOJ 23046 JAVA) 문제 : https://www.acmicpc.net/problem/23046 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23000/BOJ_23046.java ... 8시간 걸렸다. 주말 다 날라갔다. 처음엔 reverse에 대해 boolean으로만 처리하고 deque에 앞뒤로 boolean값에 따라 앞이나 뒤에 넣으면서 풀라는 쉬운 문제인줄 알았다. 그리고 '-' 나오기 전까지는 사실 실제로 s를 x에 더하지 않아도 되니깐, '-' 나오면 boolean값 반전시키면서 deque에 넣고, 그동안 쌓인거 저장하는 식으로 구성했다. 거기서도 시간 줄이고 충분히 가능할꺼라 생각했다. 그런데 계속 시간초과가 나길래, 거기에 deque도 .. 2021. 10. 24.
백준 23256 자바 - 성인 게임 (BOJ 23256 JAVA) 문제 : https://www.acmicpc.net/problem/23256 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23200/BOJ_23256.java 규칙성을 찾기가 난해했다. 일단 결과부터 말하자면 이 문제는 점화식 2개를 만들어 풀어야 한다. 전체 경우의 수를 따로 세고, 전체의 경우 중 맨 우측이 1칸짜리 블록인 경우를 따로 세야 한다. 예를들어 N=1인 경우 전체 경우의 수는 7이고, 맨 우측이 1칸짜리 블록인 경우 3가지로 다음과 같다. 그럼 왜 그렇게 해야하는지 풀이를 써보겠다. 1. N=2 이상일 경우 이전 경우에서 우측에 3개가 추가된다. 이 때 그 3개는 다음의 3가지 경우가 있다. 따라서 일단 f(n)이.. 2021. 10. 21.
[자바] 프로그래머스 - 3 x n 타일링 [코딩테스트 연습 Lv4] - 문제 출처 : 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges - 지형이동 문제 : https://programmers.co.kr/learn/courses/30/lessons/12902 - 코드 : 깃헙 일반적으로 DP 기본 문제로 풀어봤을 2 x n 타일링과 크게 다르지 않다. 2 x n 타일링에서 규칙성이 좀 더 찾기 어려워졌을 뿐 마찬가지로 꼼꼼하게 규칙성만 잘 찾으면 된다. 1. 우선, 2칸짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. (코드 10line) 2. 가장 기본적인 .. 2021. 10. 21.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA) https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀.. 2021. 10. 7.
백준 15989 자바 - 1, 2, 3 더하기 4 (BOJ 15989 JAVA) https://www.acmicpc.net/problem/15989 처음엔 무지성 DP 돌리면 될줄 알았는데, 수의 순서가 다른 것은 하나로 처리해야 한다. 무작정 dp 진행하며 모든 쌍을 확인하고, 그 중 겹치는 것을 확인하기엔 메모리가 부족해보인다. 풀이1. 2차원 DP https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15900/BOJ_15989_2D-DP.java 우선 서로 겹치는 쌍이 생기지 않도록 하려면 어떻게 해야할까? 각 n에서 더해지는 숫자에 제한을 두면 된다. 예를 들어 서로 겹쳐도 된다고 생각하고 n = 1~4 일 때 1,2,3의 덧셈으로 표현 가능한 경우를 보자. 1 : 1 2 : 2, 1+1 3 : 3, 1+1+1, 1+.. 2021. 10. 4.

티스토리툴바