알고리즘56 [백준 11047] 동전 0 - 자바 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 1. 풀이 아주 쉬운 그리디 문제입니다. 문제에 오름차순으로 입력이 들어온다고 했으므로, 큰 돈부터 차례대로 나누어 가면서 나누어지면 더하고, 나머지 값들을 대상으로 계속해서 나누어가면 됩니다. 2. 코드 import java.util.*; public class Main { public static void main(String[].. 2020. 4. 3. [백준 11399] ATM - 자바 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 1. 풀이 제일 기본적인 그리디 알고리즘 문제 중 하나입니다. 그리디 알고리즘이란 매 순간마다 최적의 선택을 하여 정해진 목표까지 계산해 나가는 것을 의미합니다. DP랑 비슷해보이지만, DP는 모든 경우를 저장하여 계산하는 것이고, 그리디는 순간순간 최적의 경우만 저장하여 최적의 수로만 진행하는 것을 의미합니다. 이 문제의 경우 줄에 선 사람들의 순서대로 인출하는데 걸리는 시간을 최소화 하는 것이 목표이다. 그러므로 걸리는 시.. 2020. 4. 3. [백준 12865] 평범한 배낭 - 자바 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 1. 풀이 DP관련 알고리즘 수업때 항상 나오는 문제인걸로 알고 있습니다. knapsack 알고리즘이라고도 하죠. 처음엔 완전탐색(브루트-포스)로 해볼려고 했으나, O(2^n)의 시간복잡도를 가지므로 포기했습니다. 그리디 알고리즘도 가격이나, 무게중 하나를 탐욕적으로 계산을해도 최.. 2020. 4. 2. [백준 9251] LCS - 자바 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 우선 LCS에 대해서 이해를 해야 한다고 생각합니다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 즉, bcba는 abcbdab와 bdcaba의 LCS입니다. 이 문제를 처음 접했을때, 여러가지 생각을 해봤지만, .. 2020. 4. 2. [백준 1149]RGB거리 - 자바 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 문제의 조건을 보면 i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다고 나와있습니다. 전형적인 DP문제이며, RGB 3가지 색으로 구별하였으므로 3가지 방향으로 나누어 접근하도록 합니다. 즉, 3가지 방향으로 접근하여 N번째 까지의 드는 비용들을 전부 메모이제이션하고, 마지막에 N번째의 최소 값을 구하면 됩니다. R G B 1번 집 .. 2020. 4. 2. [백준 11726] 2xn 타일링 - 자바 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 풀이 처음에 문제만 보고는 당황하게 됩니다.. 하지만 직접 1부터 세보면서 규칙을 보면 피보나치 수열이 되는 것을 볼 수 있습니다. 1 : 1 2 : 2 3 : 3 4 : 5 5 : 8 6 : 13 7 : 21 8 : 34 9 : 55 ... 주의할 점은 입력값이 1일때도 1을 출력해서, memo의 크기를 입력값+1을 하게되면, 1을 입력했을때 문제가 됩니다. 그러므로, 애초에 memo의 배열 크기를 입력값의 제.. 2020. 4. 1. 이전 1 ··· 5 6 7 8 9 10 다음
