본문 바로가기

전체 글669

백준 24416 알고리즘 수업 - 피보나치 수 1 (JAVA 자바 풀이) 백준 24416 알고리즘 수업 - 피보나치 수 1 (JAVA 자바 풀이) 📌 문제 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자. 피보나치 수 재귀호출 의사 코드는 다음과 같다. ⚔ 입력 첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다. 📣 출력 코드1 코드2 실행 횟수를 한 줄에 출력한다. 💎 문제 분석 재귀 vs 동적 계획법 예제 💡 코드 구현 import java.io.Buffered.. 2022. 12. 8.
백준 9184 신나는 함수 실행 (JAVA 자바 풀이) 백준 9184 신나는 함수 실행 (JAVA 자바 풀이) 📌 문제 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오. ⚔ 입력 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. 📣 출력 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다. 💎 문제 분석 메모이제이션 사용하기 예제 💡 코드 구현 import java.io.BufferedReader; import jav.. 2022. 12. 8.
백준 2580 스도쿠 (JAVA 자바 풀이) 백준 2580 스도쿠 (JAVA 자바 풀이) 📌 문제 게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. ⚔ 입력 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다. 📣 출력 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 💎 문제 분석 틀리기 쉬운 부분은 3가지 조건을 만족하지 못했을 때 (= 이전 값을 잘못 찾아서 더 진행이.. 2022. 12. 7.
백준 2981 검문 (JAVA 자바 풀이) 백준 2981 검문 (JAVA 자바 풀이) 📌 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,.. 2022. 12. 4.
백준 2609 최대공약수와 최소공배수 (JAVA 자바 풀이) 백준 2609 최대공약수와 최소공배수 (JAVA 자바 풀이) 📌 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 📣 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 💎 문제 분석 최대공약수와 최대공배수는 유클리드 호제법을 이용하여 간단히 구할 수 있다. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Strin.. 2022. 12. 4.

티스토리툴바