뒤에서부터 채워나가는 DP(다이내믹 프로그래밍) 문제이다. 우선 백준이는 N+1번째 날에는 퇴사를 하기 때문에 ' intex + T(i) ' 값이 N(여기서는 7)을 넘어갈 수 없다. 예를 들어 7일째를 보면 index가 6이고 T(i) 값은 2이므로 6+2의 값이 7을 넘어가게 된다. 마찬 가지로 6일째도 index가 5이고 T(i)값은 4이므로 5+4의 값은 7을 넘어가게 된다. 이럴 경우에는 아까 말했다 싶이 뒤에서부터 채워나가는 DP이므로 i+1번째 있는 DP값을 그대로 내려받는다. 따라서 dp[6]과 dp [5]는 차례로 0이 된다. 이제 5일째 즉 index가 4인 경우의 날을 보면 index가 4이고 T(i) 값은 2이므로 4+2는 7을 넘어가지 않는다. 이때부터는 그 위의 dp값 즉 여기서..

이 문제는 next_permutation 문제이다. next_permutation이란 무엇인가? 현재 순열의 상태에서 크기순으로(사전 순) 다음에 올 수 있는 순열을 생성해주는 역할을 한다. 예를 들어 1, 4, 3, 2라는 수가 있을 때 1 4 3 2 -> 2 4 3 1 -> 2 1 4 3 ~ 식으로 순열을 만들어주는 역할을 수행한다. 1 4 3 2의 경우 뒤에서부터 순열을 비교, 뒷 값이 앞 값보다 큰 경우까지 반복한다. -> 여기서는 (1, 4)가 해당 이때 1의 인덱스를 x라고 하고 4의 인덱스를 y라고 한다. 다시 두 번째 for 문으로부터 탐색하여 인덱스 x값 즉 1 보다 큰 값이 있으면 그 값과 1을 swap 한다. -> 여기서는 1과 2가 swap y에 해당하는 인덱스부터 정렬해준 뒤 이어..

규칙성을 찾아낸 뒤 DP를 이용하여 풀이하는 문제이다. 우선 숫자가 작은 경우 직접 개수를 세 규칙성을 찾는다. 1일 때 -> 1 2일 때 -> 2 3일 때 -> 4 4일 때 -> 7 5일 때 -> 13 이에 따라 점화식은 f(n) = f(n-1) + f(n-2) + f(n-3) (n>3 인 경우) n = int(input()) def sums(n): if n == 1: return(1) elif n == 2: return(2) elif n == 3: return(4) else: return sums(n-1) + sums(n-2) + sums(n-3) #규칙을 찾아내는게 중요! for i in range(n): a = int(input()) print(sums(a))

자료구조(Data Structure)란 '데이터를 표현하고 관리하고 처리하기 위한 구조'이다. 오늘은 그중 기초인 스택과 큐에 대해 알아보자. 스택과 큐는 다음의 두 핵심적인 함수로 구성된다. 삽입(push) : 데이터를 삽입한다. 삭제(pop) : 데이터를 삭제한다. 이 외에도 오버플로(특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생)와 언더플로(특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생)도 고민해봐야 하는 문제이다. 스택 스택은 쉽게 도넛 쌓기에 비유할 수 있다. 도넛을 아래부터 차곡차곡 쌓는다고 하면 그 도넛을 먹을 때는 가장 위에 있는 도넛을 먹을 것이다. 이러한 구조를 선입 후출(First In La..

점화식을 생각해보면 dp[ i ]가 가질 수 있는 경우의 수는 dp [ i-1 ] 에서 추가로 2x1의 타일을 세로로 붙인 경우 dp [ i-2 ] 에서 추가로 2x1의 타일을 가로로 2개 붙인 경우 + 2x2의 타일을 하나 붙인 경우 이렇게 점화식을 구성할 수 있다. (여기서 주의할 점은 dp[ i -2 ]에서 2x1 타일을 세로로 2개 붙인 경우는 1번 경우 안에 포함됨으로 점화식에 포함시키지 않는다.) 따라서 최종 점화식은 dp[i] = dp[i - 1] + 2 * dp[i - 2] (여기서 i = 0일때 즉 타일을 아무것도 놓지 않는 경우도 1로 세준다는 것에 주의하자) 이 문제는 테스트 케이스의 개수가 주어지지 않기 때문에 예외처리를 통해 구현해준다. dp = [0 for i in range(2..