코딩테스트48 [백준 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. [백준 1003]피보나치 함수 - 자바 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 풀이 피보나치 수열을 재귀를 사용하여 풀때, 0과 1의 호출 횟수를 구하는 문제입니다. 피보나치의 재귀 동작 순서가 쓰여져있어서, 처음엔 피보나치 수열을 재귀적으로 풀어서 정답을 구하려다보니 시간 초과가 발생해서 DP를 사용하여 풀게 되었습니다. 우선, 피보나치의 0과 1의 호출 횟수는 아래와 같은 규칙을 가집니다. n memo[i][0] 0 호출 횟수 memo[i][1] 1 호출 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 memo[i][j] = memo[i-1][j] +.. 2020. 4. 1. 이전 1 ··· 4 5 6 7 8 다음
