본문 바로가기

Coding Test/백준 알고리즘 풀이45

[백준] 11722번 가장 긴 감소하는 부분 수열 (자바) : DP [실버 2] ✔️ 문제 설명 (펼치기)더보기문제수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다. 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 예제 입력 1 복사610 30 10 20 20 10예제 출력 1 복사3입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있.. 2024. 8. 28.
[백준] 2748 피보나치 수2 (자바) : DP [브론즈2] ✔️ 문제 설명 (펼치기)더보기문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 10예제 출력 1 55  ✔️ 문제 풀이이 문제의 경우 이전에 풀었던 .. 2024. 8. 27.
[백준] 11726 2xn 타일링 (자바) : DP [실버 3] 이번 포스팅에서는 DP 알고리즘 백준 11726 2xn 타일링 문제를 풀어보도록 하겠습니다. 상세한 설명 포함 !! ✔️ 문제 설명 (펼치기)더보기 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. ✔️ 문제 풀이[의식의 흐름] 1. 처음에는 n이라는 숫자를 1의 배수의 합과 2의 배수의 합으로 나타내야 한다고 생각했다. 2. a+2b = n 이라는 방정식을 세웠다 .3. for 문을 활용해서 a와 b를 어떻게든 구할 수 있겠다. 4. n이 5일 때 2x1 타일이 1개이고 1x2 타일이 2개 일 때, 각 타일을 어디다가 배치할지에 대한 고민이 생긴다. 위의 그림처럼 타일을 배치하는거에 따.. 2024. 8. 26.
[백준] 2579 계단 오르기(자바) : DP [실버3] ✔️ 문제 설명더보기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번째 .. 2024. 8. 26.
[백준] 9095 1,2,3 더하기 (자바) : DP ✔️ 문제 설명더보기문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.예제 입력 1 복사34710예제 출력 1 복사744274 ✔️ 문제 풀이우선 혼자의 생각으로 이 문제를 풀지 못 했다... ㅎㅎ 블로그를 여러개 찾아보던 중 가장 쉬운 설명으로 이.. 2024. 8. 24.
[백준] 1463 1로 만들기 (자바) : DP ✔️ 문제 설명더보기문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.예제 입력 1 2예제 출력 1 1예제 입력 2 10예제 출력 2 3힌트10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다. ✔️ 문제 풀이  [알고리즘 정리] DP(Dynamic Programming) : 동적 계획법✔️ DP(Dynamic Progra.. 2024. 8. 24.

티스토리툴바