[BEAKJOON] 백준 11053번 : 가장 긴 증가하는 부분 수열 - 파이썬
문제 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 문제 설명 STEP 1 ] 변수 선언 DP 테이블을 사용해서, 모두 1로 초기화해준다. STEP 2 ] 주어진 숫자의 배열에서 인덱스를 하나씩 늘려서 LIS(Longest Increasing Subsequence) 를 찾는다. 인덱스는 1부터 N까지 진행한다. ( 0번째 인덱스의 값은 길이가 무조건 1이다.) ST..
[BEAKJOON] 백준 2193번 : 이친수 - 파이썬
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 설명 쉽게 발견할 수 있는 특정한 패턴이 있는데, 뒤의 자리가 1일 때에는 0만 올수 있고, 뒤의 자리가 0일 때에는 1, 0 둘다 올 수 있다. 그러면 처음에 [0, 0]의 리스트로 num의 개수만큼 초기화를 하고, 진행해준다. # n = 1 : 1, 1 # n = 2 : 1, 10 # n = 3 : 2, 100, 101 # n = 4 : 3, 1000, 1010, 1001..
[BEAKJOON] 백준 10844번 : 쉬운 계단 수 - 파이썬
문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해설 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 먼저 값이 1일때를 보자 # 1 -> 9: 1, 2, 3, 4, 5, 6, 7, 8, 9 n의 값이 2일때는 # 2 -> 17: 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 n의 값이 3일때는 # 3 -> : 123..
[BEAKJOON] 백준 15990번 : 1, 2, 3 더하기 5
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다. 1+2+1 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 아래와 같이 몇개일지 확인을 해주었다. # 1 - 1 # 2 - 2 : 2 # 3 - 3 : 1+2, 2+1, 3 # 4 - 3 : 1+3..
[BEAKJOON] 백준 11726번 : 2xn 타일링
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하라는 문제이다. 문제 해결 패턴을 먼저 찾아보자. # 1 - 1 -> | # 2 - 2 -> =, || # 3 - 3 -> |=, =|, ||| # 4 - 5 -> ||=, |=|, ||||, ==, ||= # 5 - 8 => |||||, |||=, =|||, |=||, ||=|, |==, ==|, =|=, 마치 피보나치 ..
