potato's devlog

문제 링크 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 부터 쭉 경우의 수를 살펴보면,..

문제 링크 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 내가 푼 풀이 우선 이전 2xn타일링 문제에서는 규칙을 발견하고 그냥 피보나치 방식으로 풀었다. 이 문제는 그 문제의 연장선이기는 하지만, 피보나치 수열 규칙으로는 풀 수가 없었다. 정확하게 왜 그런 방식으로 문제를 풀었는지 이해하는 것이 중요했다.. 우선 풀이에 앞서 경우의 수를 구하는 방식과 원리에 대해서 이해해보자. [1, 2, 3, 4] 의 배열이 있을 때 , 이 숫자들로 만들 수 있는 순열을 작성해보면 다음..

문제 링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 내가 푼 풀이 처음에도 이게 왜 동적계획법인지 몰랐다. 인터넷을 대충 참고해보니, 타일링 갯수가 늘어나는 규칙이 피보나치와 닮아있다는 사실을 발견하면 쉽게 풀릴 수 있다고 했다. 정말, 그림을 그리며 풀이과정을 생각해보니 일정한 규칙대로, 피보나치 수열의 형태로 숫자가 증가함을 알 수 있었다. 그래서 bottom up 방식으로 for 문을 이용하여 풀었다. dp 문제에서 기억할 것은, dp 배열은 항상, 경..

문제 링크 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을 빼는 건,..

문제 링크 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 해결 아이디어 함수 isPrimeNumber 현재 입력받은 수까지 무슨 소수가 존재하는지 배열로 정리 예를들어 9가 입력되면, [2, 3, 5, 7] 이 반환된다. main 입력받은 num 까지 무슨 소수가 존재하는지 isPrimeNums 배열 생성 2부터 num/2 까지 반복 왜 num/2 냐? 10을 예로 들면, (3, 7), (5, 5) (7, 3) 이렇게 골드바흐 파티션이 3..