몽상실현개발주의

[BOJ] 11722 / 가장 긴 감소하는 부분 수열 / Python www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 [BOJ] 11053 / 가장 긴 증가하는 부분 수열 문제의 연관 문제이다. 조건만 반대로 작성해 주면 된다. N = int(input()) nums = list(map(int, input().split())) dp = [1] * N for i in range(N..

[BOJ] 11055 / 가장 큰 증가 부분 수열 / Python https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 [BOJ] 11053 / 가장 긴 증가하는 부분 수열 의 연관 문제이다. 수열의 길이가 아닌 LIS 부분 수열의 원소 합을 구해야 한다. N = int(input()) nums = list(map(int, input().split())) dp = [1] * N for ..

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python 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 풀이 긴 증가하는 부분 수열을 구하는 문제로 LIS 문제라고도 한다. 이중 for 문을 이용하여 현재 index 이전 까지의 수 중에서 현재 수보다 작은 숫자들을 찾고, 작은 수들의 부분 문제 결과 를 이용하여 현재 index 의 문제를 해결 할 수 ..

[BOJ] 2156 / 포도주 시식 / Python www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 주어진 조건에 대한 규칙을 배열을 이용하여 찾을 수 있는 문제이다. i 번째 포도주 선택에 대한 경우의 수는 다음과 같다. ~ i-3 i-2 i-1 i ~ O O X ~ O X O ~ X O O 위의 세 경우 중 가장 양이 커질 경우를 선택하면 된다. A = dp[i-1] B = wine[i] + dp[i-2p] C = wine[i] + wine[i-2] ..

[BOJ] 9465 / 스티커 / Python https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 주어진 데이터와 조건을 분석하여, 규칙을 찾으면 쉽게 풀리는 문제였다. 하지만 익숙한대로 손이 간다고, DFS 를 이용한 완전 탐색으로 구현해 보았다. import copy T = int(sys.stdin.readline()) def deleteStiker(i, j, stickers): stickers[i][j] = 0 if i: st..

[BOJ] 2193 / 이친수 / Python https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 경우의 수를 구하여 나열해 보았다. N = 1 -> 1 N = 2 -> 10 N = 3 -> 100 101 N = 4 -> 1000 1001 1010 N = 5 -> 10000 10001 10010 10100 10101 N = 6 -> 100000 100001 100010 100101 100100 101000 101001 101010 ..

[BOJ] 11058 / 오르막 수 / Python https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 BOJ / 10844 / 쉬운 계단 수 와 유사한 문제이다. 쉬운 계단 수 문제와 마찬가지로, 경우의 수를 이차원 배열로 정리하여 결과에 대한 연관성을 구하였다. 0 1 2 3 4 5 6 7 8 9 N = 1 ->1 1 1 1 1 1 1 1 1 1 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ N = 2 ->1 → 2 ..

[BOJ] 10844 / 쉬운 단계 수 / Python www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 처음 시도는 경우의 수가 정해져 있다고 생각하여, N 으로 구하는 점화식을 세우려고 하였다. 하지만 매우 복잡한 점화식이 세워졌고, 그 답은 보기 좋게 오답이 나왔다. 문제를 풀기 위한 생각의 방향은, 숫자의 자리수가 늘어날때 조건이 있고, 그 조건으로 인해 경우가 좁혀져 패턴이 발생한다는 것이다. N = 1 -> 1 2 3 4 5 6 7 8 9 N = 2 -> 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 N = 3 -..