Algorithm
-
[다이나믹 프로그래밍] 문제 이름 : 1로 만들기Algorithm/유형별 문제 풀기 2021. 11. 24. 12:06
문제 설명 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. 1. X가 5로 나누어떨어지면, 5로 나눔 2. X가 2로 나누어떨어지면, 2로 나눔 3. X가 3으로 나누어떨어지면, 3으로 나눔 4. X에서 1을 뺌 정수 X가 주어졌을 때, 위의 연산 4개를 적절히 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 구하시오. 사용 개념 다이나믹 프로그래밍, 보텀업 방식 문제 해결 아이디어 모든 연산 가능 경우에 대해 생각해봐야 할 것 같은데 너무 많은 것 아니야..? → 맞아! 경우의 수로 모든 경우에 대해 봐야되는거 맞는데 다이나믹 프로그래밍을 사용해서 빠르게 구하는거지! 어차피 최소 연산 횟수 구하는 것이니까! 1. 함수 호출 과정 도식화하기 → 모든 경우의 ..
-
[다이나믹 프로그래밍] 개념 정리Algorithm/개념정리 2021. 11. 23. 21:11
다이나믹 프로그래밍(동적 계획법)?! 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법임 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 구현은 일반적으로 2가지 방식(탑다운 & 보텀업)으로 구성됨 '동적 계획법' 이라고도 부르는데, 흔히 프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중에' 라는 의미임 예를 들어, 자료구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법임 하지만 다이나믹 프로그래밍에서의 '다이나믹'은 동적 할당(Dynamic Allocation)에서의 다이나믹과는 다른 의미임 다이나믹 프로그래밍의 기본적인 아이디어 1줄 요약 : 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면..
-
[이진 탐색] 문제 이름 : 부품 찾기 - 배열 Sort, Binary SearchAlgorithm/유형별 문제 풀기 2021. 11. 18. 11:33
문제 설명 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 가게 안에 손님이 원하는 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 사용 개념 탐색 문제 해결 아이디어 비교 대상이 되는 값들을(가게의 부품 번호) 배열에 저장하므로, java.util.Arrays 에서 제공하는 sort()로 정렬하고, binarySearch() 사용하여 탐색함 코드 import java.util.Arrays; import java.util.Scanner; public class Q1 { public static void main(String[] args) {..