여름 언덕에서 배운 것

최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘으로, '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 다익스트라 최단 경로 알고리즘 (알고리즘 대회를 준바한다면 다익스트라 최단 경로 알고리즘은 자다가도 일어나서 바로 코드를 작성할 수 있을 정도로 코드에 숙달되야함) 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 "가장 비용이 적은 노드"를 선택해서 임의의 과정을 반복하는 그리디 알고리즘이기도 함 [1] 출발 노드를 설정한다. [2] 최단 거리 테이블을 초기화한다. [3] 방문하지 않은 노드 중에..

동적 계획법(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를 출력한다. 구분은 공백으로 한다. 📝 문제 해결 이진 탐색..