potato's devlog

문제링크 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 내가 푼 코드 var n = Int(readLine()!)! var tp: [[Int]] = [] var dp = Array(repeating: 0, count: 100) for i in 0..

문제 링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA 규칙을 찾다가 2차원배열로 풀어야한다는 생각을 미처 하지 못해서 인터넷을 참고했다. dp 도 다양한 유형을 풀며 어떤 상황일 경우 어떻게 접근해야하는지 감을 익혀야하는 것 같다. 규칙찾기가 힘들었다. 이런 문제가 나오면 2차원으로 풀자. k개를 더해서 n을 만드는 경우의 수를 배열로 넣으면 된다. 2차원 배열일 경우 표를 그리면서 규칙을 찾아나서면 된다. 생각보다 간단한 규칙이 있다. dp는 무조건 규칙부터! 규칙을 설명해보겠다. 우선 위에서 적은것 처럼 k개의 수를 더해서 n을 만들자! 라는 맥락..

문제링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 풀이 IDEA 우선 dp 문제를 만나면, 규칙을 파악하기 쉽게 모든 경우의 수를 수기로 써본다. 이렇게 작성해보았다. 문제의 규칙이 보일듯, 보이지 않았다. dp 배열에 1일때 항의 수 1, 2일때 항의 수 2, 3일때 항의 수 3, 4일때 항의 수 1.. 이렇게 넣으려고 하는 건 알겠다. 근데 이제 어떻게 점화식을 만들어야할까? 우선 나는 아..

문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 idea 앞에서 풀던 dp 문제와 다를 것 없는 문제! 앞에서부터 더해주고 max값으로 바꿔주면 돼. 왜냐면!! 어차피 가장 큰 값을 찾는거라 계쏙 max 값으로 업데이트 되기 때문이다. 소스코드 let n = Int(String(readLine()!))! let arr = readLine()!.split(separator: " ").map{Int(String($0))!} var dp ..

최장 증가 부분 수열 (LIS,Longest Increasing Subsequence) 이란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열"이라고 한다. - 나무위키 🌳 ▷ 예시를 들어보자. [ 3, 5, 7, 9, 2, 1, 4, 8] 다음과 같은 수열이 있다고 하자. 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있다. 몇 개의 수를 제거해서 오름차순으로 이루어진 수열을 최장 증가 부분 수열이라고 하였는데, 즉, '공차'가 존재하지 않아도 부분수열이라고 본다는 것이다. (규칙적이지 않고 오름차순이면 된다는 뜻) 따라서 위 수열에서 도출될 수 있는 부분수..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 내가 푼 풀이 bottom up 방식으로 문제 풀이 dp 배열의 인덱스가 숫자를 뜻하고, value가 그 인덱스까지 도달할때 최소 경우의 수이다. 즉, dp 배열에는 그 숫자까지 도달할때의 경우의 수를 메모이제이션 해두는 것이다. 1번규칙 (3으로 나누어 떨어진다) dp[n] = d[n/3] +1 바로 직전 (3의배수니까 n/3) 경우의 수 에서 1을 더해주는 것 2번규칙 (2로 나누어 떨어진다) dp[n] = dp[n/2] +1 3번규칙 (1을 뺀다) dp[n] = dp[n-1]+1 1을 빼는 건,..

Dynamic Programming (동적 계획법) 동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. - Wikipedia ▷ 코딩테스트에서의 DP 코딩테스트의 단골 문제로 출제되고 있기에 필수적으로 알아야하는 개념 중 하나이다. 간혹 제약사항에 주어지는 숫자의 범위가 크고, 경우의 수가 엄청 많은 문제들이 대부분 DP(동적계획법) 을 활용하여 풀어야 하는 문제이다. Dynamic Programming (동적 계획법) 방법 모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는..