여름 언덕에서 배운 것

동적 계획법(DP, Dynamic Programming)이란? 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 💡 퀵 정렬 (분할 정복)과 차이는? 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있음 즉, 한 번 해결했던 문제를 다시금 해결한다는 점이 특징임 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 프로그래밍에서 수학적 점화식을 표현하려면 재귀 함수를 사용하면 된다. f(n) = f(n-1) + f(n-2) 하지만 n이 커지면 수행 시간이 기하급수적으로 늘어날 수 있다 public class Main { public static int fibo(int x) { if (x == 1 || x == 2) { ret..

📚 문제 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 📝 문제 해설 : 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것 전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다. 이 높이 괜찮아..? 를 확인한 뒤에 조건의 만족 여부에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 범위를 좁힐 때는 이진 탐색의 원리를 이용한다! 💡 파라메트릭 서치 최적화 문제를 결정 문제('예' 혹은 '아니오'로 답하는 문제) 로 바꾸어 해결하는 기법 -원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용 - 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 ..

📚 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 📝 문제 해결 이진 탐색..

📚 문제 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. - 시간 복잡도 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나 O(N)을 보장하는 계수 정렬을 이용하면 된다. import java.util.*; class Student implements Comparable{ private String name; private int score; public Student(String name, int score) { this.name = name; this.score = score; } publi..