potato's devlog

문제 링크 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 ..

문제 링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 IDEA 우선 해당 문제는 LIS를 구현한 이후에, LIS 부분 수열을 출력하는 문제이기 떄문에 아래 두 개의 포스팅을 모두 이해해야 해당 문제를 수월하게 풀 수 있다. ▷ LIS 란? https://didu-story.tistory.com/236 [알고리즘] (Swift) 최강 증가 부분 수열..

문제 링크 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 문제 풀이 IDEA 초반에 도대체 이게 무슨 소리야, 그냥 오름차순이면 수열이 되는거임? 라고 생각하며 의아했지만, 바로 그게 잘 이해한 거였다. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequences) 라는 개념인데, 주어진 배열에서 오름차순으로 이루어진 수열 중, 가장 긴..

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

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 IDEA N=2 부터 규칙을 찾아보니까, 이전에 풀었던 동적계획법 문제와 비슷하게 끝자리에 따라서 경우가 나뉘었다. 아래와 같이 점화식을 도출할 수 있다. 이를 코드로 구현하면 아래와 같다. let n = Int(readLine()!)! var dp = [[Int]](repeating: Array(repeating: 0, count: 2), count: n+1) if n..

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA dp를 꾸준히 풀다보니, 어떤게 2차원으로 풀어야할지, 어떤게 일반 dp 1차원 배열로 풀어야할지 감이 잡혔다. 올레! 해당 문제는 N=1 부터 경우의수를 하나씩 따져가며 그림을 그려보니, 규칙이 눈에 보였다. 찾은 규칙은 아래와 같다. 위 그림을 보면, 맨 뒷자리수가 0과 9인 경우에는 한가지씩 늘어날 수 있고, 1~8 이라면 두가지의 경우로 늘어날 수 있다는 규칙을 찾아낼 수있다. 이를 dp 경우의수에 맞게 도식화 하면 아래와 같다. 현재 N에서, 0을 맨 뒷자리로 가지려면, N-1..

문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA (DP 어렵다 .. 나중에 코딩테스트 문제를 연습할때 dp 부분을 집중적으로 공략할 것이다 ㅠㅠ ) 먼저 풀었던 "백준 9095번 1,2,3 더하기" 와는 다르게, 더해지는 숫자의 "순서!!"를 생각해야한다는 점이 어려웠다. 9095번 4를 만들기 위한 경우의 수 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 같은 수 중복 가능 15990번 (지금 문제) 4를 만들기 위한 경우의 수 1+2+1 1+3 ..

문제 링크 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 IDEA 이전 문제 "카드 구매하기"를 먼저 풀어보면 바로 알 수 있는 문제이다. (복습한다는 생각으로 다시 풀이 아이디어를 적어보자) 구매를 원하는 카드의 수를 n , 카드 팩 각각의 가격을 배열 p 에 입력을 받을 것이다. dp 배열을 생성하여 조건 범위 밖의 수인 99999 를 n+1 크기만큼 넣어준다. 가장 큰 수 999999를 넣는 이유는, 우리는 min 값을 구할 것이다. ..

문제 링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 내가 푼 풀이 - 맞았습니다! 예제 1번을 활용하여 생각해보자. 카드 개수 n, 입력되는 각 카드팩의 가격을 배열 p , 카드 n 개를 구매할 때의 최대 금액을 배열 dp에 넣을 것 카드 4개, 가격 p = [1, 5, 6, 7] 일때 dp = [0, 0, 0, 0, 0] → 인덱스 값을 맞추기 위해서 n+1 개 만큼 dp를 0배열로 정의 이렇게 정의한 뒤, dp 배열에 어떻게 max 값을 넣..

문제 링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 내가 푼 풀이 - 맞았습니다! dp 문제를 세 번째 푸는 것이지만, 감을 아직 잡지 못했따. (바본가) 그래서 풀이를 찾아보던 중, dp 문제는 규칙을 찾아내는 거싱 핵심 포인트가 된다는 점을 알게 되었다. dp 문제 특성상, 경우의 수를 찾는 문제가 많고, memoization 해놓은 바로 직전의 수열에 더해서 값을 찾아내는 문제가 많기 때문이다. 내가 해당 문제를 풀이한 방법은 다음과 같다. *(필기에 오류가 있어서 수정했슴다 허허) 이렇게 일단 1 부터 쭉 경우의 수를 살펴보면,..