본문 바로가기

Coding Test75

[백준] 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.
[알고리즘 정리] DP(Dynamic Programming) : 동적 계획법 ✔️ DP(Dynamic Programming) 정의DP(Dynamic Programming) 이란?다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나눈 다음, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다.  ✔️ DP를 쓰는 이유DP는 일반적인 재귀(Recursion) 방식과 매우 유사하다.큰 차이점은 일반적인 재귀의 경우 큰 문제를 작은 하위 문제로 나누어 해결하는 방법으로, 작은 문제들이 여러번 반복(중복 계산)되어 비효율적인 계산이 될 수 있다.반면에, DP는 작은 하위 문제들로부터 시작하여 그 결과를 저장하고 이를 이용하여 큰 문제를 해결한다.즉, DP는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킨다. ✔️ DP 기법을 적용시킬 수 있는 조건1. 중복되는.. 2024. 8. 24.
[백준] 1080 행렬 (자바) : 그리디 알고리즘 ✔️문제 설명 ( 펼치기 ) 더보기문제0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0) 입력첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 예제 입력 1 3 4000000100000100110111001예제 출력 1 2예제 입력 2 3 3111111111000000000예제.. 2024. 8. 22.
[백준] 11399 ATM(자바) : 그리디 알고리즘 [하] ✔️ 문제 설명 더보기 문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = .. 2024. 8. 22.

티스토리툴바