본문 바로가기

분류 전체보기134

[DP] 계단 오르기 개구리가 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 점프하는 게임을 하려고 한다. 개구리는 한 계단을 점프해서 오를 수도 있고, 두 계단을 점프해서 오를 수도 있다. 각 계단에는 일정한 점수가 부여되어 있으므로, 개구리가 계단을 밟으면 그 계단의 점수를 획득한다. 예를 들어, 아래 그램에서 개구리가, 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 개구리가 획득하는 점수는 10 + 20 + 25 + 20 = 75점이 된다. N개의 계단에 부여된 점수가 주어질 때, 개구리가 획득할 수 있는 최대 점수를 출력하시오. Input 첫째 줄에 계단의 개수 N이 주어진다. 둘째 줄에 N개의 계단의 점수가 차례대로 주어진다. 6 10 20 15 25 10 20 6 10 -20 -1.. 2022. 12. 14.
[DP] 이항 계수의 합 음이 아닌 정수 N이 주어졌을 때, 거듭제곱식 (1 + x)^N 를 전개했을 때의 각 항의 계수를 모두 더한 값을 출력하시오. 예를 들어, N=0인 경우에는 전개식 1 의 계수의 합은 1이다. N=1인 경우에는 전개식 1 + x 의 계수의 합은 1 + 1 = 2이다. N=2인 경우에는 전개식 1 + 2x + x^2 의 계수의 합은 1 + 2 + 1 = 4이다. N은 0보다 크거나 같고, 500,000보다 작거나 같은 정수이다. Hint: 이 문제는 해답 코드내에서 파스칼의 삼각형을 직접 생성하면 풀기 어렵지만, 먼저 규칙을 도출해서 간단한 해답 코드로 풀면 아주 쉬운 문제이다. Input 첫째 줄에 음이 아닌 정수 N이 주어진다. 0 2022. 12. 14.
[DP] 세보나치 수열 DP: dynamic programming 미리 준비한 테이블을 통해 가장 작은 부분 문제를 먼저 풀고, 이미 해결한 부분 문제를 통해 상위 부분 문제를 풀어나가는 방식 세보나치 수열이란? F(1) = 1, F(2) = 2, F(3) = 3 F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3 세보나치 수열은 다음과 같이 재귀적으로 정의한 수열이다. F(1) = 1, F(2) = 2, F(3) = 3 F(n) = F(n-1) + F(n-2) + F(n-3), if n > 3 양의 정수 n이 주어졌을 때, n번째 세보나치 수열 F(n)을 출력하시오. Input 첫째 줄에 양의 정수 n이 주어진다. 1 2022. 12. 14.
[Hash Table] 에너그램 정렬 애너그램? 두 문자가 있을때, 두 문자의 알파벳 순서를 무시하고 둘 다 동일하면 애너그램이다 예) eat, ate N개의 단어가 주어졌을 때, 애너그램을 알파벳 순으로 다음과 같이 정렬하시오. 1. 서로 애너그램인 단어들은 하나의 그룹으로 묶어 한 줄에 오름차순으로 정렬하여 출력한다. 2. 애너그램 그룹의 가장 첫 번째 단어의 오름차순으로 각 그룹을 출력한다. 예를 들어, N=6개의 단어 eat, tea, tan, ate, nat, bat 가 입력으로 주어지면, 다음과 같이 세 개의 애너그램 그룹으로 나누어 한 줄에 하나의 그룹을 출력한다. ate eat tea bat nat tan 위에서 각 애너그램 그룹의 첫 단어인 ate, bat, nat가 오름차순으로 그룹의 출력 순서를 결정한다. 또한, 각 그룹.. 2022. 12. 13.

티스토리툴바