BOJ
백준 11053: 가장 긴 증가하는 부분 수열 해설- python
✏️ 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✏️ 풀이 LIS(Longest Increasing Subsequence)라는 유명한 DP문제이다.만약 A={6, 2, 5, 1, 7, 4, 8, 3} 가 있을때 LIS는 {2, 5, 7, 8}이 된다. 증가하는 수열은 {2, 5}, {2, 7} 등 많지만 그 중 가장 긴 것이 LIS가 된다. - dp[i]를 전부 1로 초기화했다. LIS의 길이는 기본적으로 1은 될 것이기 ..
백준 9095: 1, 2, 3 더하기 해설- python
✏️ 문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 풀이 늘 그렇듯 규칙을 찾아보자. n=1 일 때, 1n=2 일 때, 1+1, 2n=3 일 때, 1+1+1, 1+2, 2+1, 3n=4 일 때, 1+1+1+1, 1+3, 3+1, 4....어? 이거다. 1+3은 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3). 아까 n=3일 때 해결한 문제를 내포하고 있다.즉 n이 3보다 커지면 그 문제들은 n=1,2,3일 때의 문제를 포함하고 있다.즉 작은 문제(n=1,2,3)를 이용해 큰 문제를 해결하는 동적계획법(Dynamic Programming)을 이용하면 적합하겠다. [Python & A..
백준 11727: 2xn 타일링(2) 해설- python
✏️ 문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ✏️ 풀이 2xn 타일링 문제에서 2x2타일이 추가된 형태의 문제로 점화식만 살짝 수정해주면 된다. 2xn 타일링 문제는 아래에서 다시 풀어보자 백준 11726: 2xn 타일링 해설- python ✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acm duckracoon.tistory.com 이전의 문제에서는 점화식이 c..
백준 11726: 2xn 타일링 해설- python
✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✏️ 풀이 뭘 어쩔지 모를땐 늘 그렇듯 규칙을 찾아보자. 모든 경우의 수를 한번 생각해보았다. n=1 > size 1 : 1개 n=2 > size 1: 2개 || size 2: 1개 n=3 > size 1: 3개 || size 1: 1개 + size 2: 2개 || size 1: 2개 + size 2: 1개 n=4 > size 1: 4개 || size 1: 2개 + size 2: 2개(L) || size 1: 2개 + size 2: 2개(R) || size 1: 1개 + s..
백준 1463: 1로 만들기 해설- python
✏️ 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 풀이 해당 풀이는 주로 동적계획법 (Dynamic Programming) 을 이용하는 것 같다. 동적계획법에 대한 설명은 아래글을 참고하자. [Python & Algorithm] Dynamic Programming(동적프로그래밍) ✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나 duckracoon.tistory.com 어떻게 시작해야할지 잘 모르겠으니 나는 임의의 X를 가지고 수가 어떻게 변하는지를..