본문 바로가기

알고리즘/백준118

백준 1912 연속 합 (JAVA 자바 풀이) 백준 1912 연속 합 (JAVA 자바 풀이) 📌 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. ⚔ 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 📣 출력 첫째 줄에 답을 출력한다. 💎 문제 분석 sum 배열로 dp[]를 이용하는 것이 핵심이다. 💡 코드 구현 im.. 2022. 12. 9.
백준 9461 파도반 수열 (JAVA 자바 풀이) 백준 9461 파도반 수열 (JAVA 자바 풀이) 📌 문제 N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 📣 출력 각 테스트 케이스마다 P(N)을 출력한다. 💎 문제 분석 int로 선언시 틀리는 점에 주의하자. 💡 코드 구현 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { private static long[] dp; public static void main(String[] args) throws.. 2022. 12. 9.
백준 1904 01타일 (JAVA 자바 풀이) 백준 1904 01타일 (JAVA 자바 풀이) 📌 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000.. 2022. 12. 9.
백준 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.

티스토리툴바