rainyCode rainyCode

백준 1932번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 이 문제는 규칙이 눈에 보여서 어떻게 코드로 잘 정리하냐가 관건인 문제 같다. 문제 링크 알고리즘 최댓값의 경로를 파악해야 하는데 dfs 같이 모든 경로를 탐색해 버리면 n이 최대 500개라 해보진 않았지만 분명 시간 초과가 날 것 같아, 위에서 부터 한번에 돌면서 최댓값을 찾는 dp를 이용해야된 다. dp 이중배열을 선언해 dp[i][j]라 하면, 위에서 부터 i번째 층에 왼쪽부터 j번째 값의 최댓값을 저장한다고 하자. 지금부터 dp배열의 값들을 구해볼 것이다. 우선 삼..

백준 11053번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 이 문제는 특히 실버2의 난이도를 갖고 있는 만큼 생각을 많이 해야지만 규칙을 파악할 수 있다. 문제 링크 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 알고리즘 규칙을 파악하기 까다로운 문제이다. 먼저, 가장 긴 증가하는 수열이 되기 위해서는 처음부터 각 원소의 최대 증가길이를 생각해볼 필요가 있다. 예를 들어, 위의 예시에 주어진대로 10 20 10 30 20 50 수열에서는, 10 20 의 각각의 수열의 길이는 1,2 가 된다. 하지만 3번째 ..

백준 1149번 RGB거리 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 cnt [1001][3]라는 이중 배열을 선언해 cnt [n][o]은 n 번째 집을 빨간색으로 칠할 때 최솟값, cnt [n][1]은 n 번째 집을 초록색으로..

백준 2193번 이친수 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 알고리즘 // 1 // 10 // 100 101 // 1000 1010 1001 // 10000 10100 10010 10001 10101 이친수는 0으로 시작하지 않고 1이 두 번 이..

백준 11726번 2xn 타일링 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 문제 링크 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 알고리즘 실버 3 문제인데 생각보다 안 떠올라서 어렵게 느껴졌다. 결국 노가다하다가 규칙은 찾아내었는데 마지막에 값이 너무 커지는 걸 생각을 못해, 마지막 출력에만 10007로 나누어주었다가 틀렸다...