dp19 [백준 11055] 알고리즘 47일차 : 가장 큰 증가 부분 수열 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 동적계획법 C++ 이번엔 가장 큰 증가하는 부분 수열의 합 구하기 접근 방법 지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다. 차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우 길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로 비교할 때 이 부분을 주의해야 했다. 소스.. 2020. 8. 20. [백준 10844] 알고리즘 46일차 : 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적계획법 C++ 쉬운계단수 구하기 접근방법 1~8까지는 괜찮은데 0,9가 문제였다. 그래서 0,9 경우를 따로 계산하고 우선 기본적인 접근은 n번째 자리에 오는 0부터9까지의 숫자의 갯수를 저장하는 배열을 사용한다. 0의 개수는 이전 자리의 1의 개수 1~8(i)의 개수는 이전 자리의 i-1의 개수 + i+1의 개수 9의 개수는 이전 자리의 8의 개수 그리고 마지막에 n번째 자리에 오는 0~9의 개수를 모두 더한 값을 출력한다. 처음엔 마지막에 값을 더할때 나머지 계산을 안하고, 1~8의 경우를 저장할 때 i.. 2020. 8. 18. [백준 11053] 알고리즘 45일차 : 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 동적계획법 C++ 가장 긴 증가하는 부분 수열을 구하는 문제 접근 방법 DP라서 뭔가 2중 for문은 안될 것 같다고 생각하다가 최대 N이 1000이고 제한시간이 1초면 2중 for문도 되겠다 싶어서 그렇게 구현했다. 이번에도 각 인덱스 까지의 최대길이를 갖고 있는 배열을 사용했다. 다만 2중 for문을 사용해야 했던 .. 2020. 8. 17. [백준 2156] 알고리즘 44일차 : 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 동적계획법 C++ 계단 오르기 문제와 로직이 동일해보여서 풀기 시작했는데 닮은듯 달랐다. 계단오르기와 차이점은 우선 두칸이상 건너뛸 수 있다. (근데 사실상 세칸이상 건너뛰는 경우는 없다. 가운데 하나를 먹어야 이득이니까) 그리고 꼭 마지막 주스를 먹어야할 필요가 없다. (최종 값을 출력할때 n-1칸과 n-2칸의 값을 비교해서 출력해야함) 차이점은 두갠데 그래서 많은 것이 추가됐다.. 접근방법은 계.. 2020. 8. 14. [백준 1463] 알고리즘 43일차 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법 C++ 문제는 위에 사진 참고 (설명 매우 귀찮다 딱히 요약할 것도 없응께) N의 범위는 1부터 10^6 까지 접근방법 n개의 정수 배열을 사용한다. 배열에는 해당 수가 1이 되는데에 필요한 연산의 최소 횟수가 저장된다. 1: 0회, 2: 1회, 3: 1회까지 미리 저장해두고 4부터는 [ 1을 뺀 수의 연산 최소횟수 + 1 , 3으로 나눈 값의 연산 최소횟수 + 1 (3으로 나누어질때만), 2로 나눈 값의 연산 최소횟수 + 1 (2로 나누어질때만) ] 이 중 가장 작은 값을 해당 인덱스의 배열에 저장.. 2020. 8. 13. [백준 1932] 알고리즘 41일차 : 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 동적계획법 C++ 숫자 트리에서 숫자들의 합이 최대가 되는 경로 구하기(최댓값 출력) 접근방법 전형적인 DP 상향식 풀이로 풀었다. 가장 밑 행부터 모든 숫자에 대해 해당 자리까지의 최댓값을 저장해가면서 값을 갱신한다. 예를들어 위의 사진에서 4번째 행 첫번째 자리 2에서 최댓값을 가지려면 4,5중 5를 선택해야하니까 원래 2가 있던 자리에 2+5 = 7을 저장한.. 2020. 8. 11. [백준 11051] 알고리즘 35일차 : 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 수학3, 동적계획법 C++ 이항계수를 동적계획법으로 푸는 문제 (간략) 작년 알고리즘 수업에서 배우고 또 비슷한 손코딩 문제가 시험에도 나왔었던 문제 이항계수였는지는 기억안남 DP에서 피보나치와 함께 배운 기억이 난다. 두 문제 모두 재귀를 배울때 나오는 개념들이지만 사실 시간복잡도면에서 보면 배열을 사용해서 반복문을 쓰는게 훨씬 효율적이다. (이걸 동적계획법 부분에서 배움 매번 이런식이지 비효율적인거 실컷 가르쳐놓고 효율적인 방법 나중에 알려주기 교수님 : 하지만 .. 2020. 7. 31. [백준 9461] 알고리즘 26일차 : 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 다이나믹 프로그래밍 C++ 접근방법 문제에 떡하니 피보나치 같은 규칙을 찾아서 풀으라고 써있어서 그렇게 풀었다. 사실 그림만 보면 p[i] = p[i-1] + p[i-5] 가 맞지만 p[i-2] + p[i-3] 으로 제출해도 맞다. 처음엔 불필요한 계산을 최대한 안하려고 (동적계획법이니까) 변수도 더 쓰고 처리도 더 했었는데 그런거 다 안해도 통과되길래 그냥 다 지우고 최대한 간결하게 제출했다. 소.. 2020. 7. 20. [백준 1904] 알고리즘 25일차 : 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 다이나믹 프로그래밍 C++ 접근방법 이것도 그냥 피보나치다. 근데 입력이 1,000,000까지고 출력은 모든 이진수 개수%15746이다. 그래서 그냥 피보나치 처럼 풀어서 나눈 나머지를 출력하면 절대 값이 안나온다. 다행히 나머지를 구하는 것이라는 거 나머지를 구해야 하는거면 굳이 결과 값을 다 더하면서 갈 필요가 없다. 결과 값에서 15746로 나누어 떨어지는 만큼은 필요 없기 때문에 1부터 N까.. 2020. 7. 18. 이전 1 2 3 다음 728x90
