Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ##### 문제 ##### # 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. # 그리고 나서 세준이는 괄호를 모두 지웠다. # 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. # 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 식이 주어진다. # 식은 ‘0’~‘9’, ..

▶ 문제 : 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 ##### 문제 ##### # 준규가 가지고 있는 동전은 총 N종류이고, # 각각의 동전을 매우 많이 가지고 있다. # 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. # 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 N과 K가 주어진다. (1 ≤ N..

그리디 알고리즘(Greedy Algorithm)이란 문제를 해결하는 과정에서 순간 순간마다 최선이라고 생각하는 것을 선택하여 최종 해답에 도달하는 알고리즘을 의미한다. 계산 과정이 굉장히 빠른 알고리즘이지만, 순간 순간 마다의 최선의 선택이 언제나 전체 결과의 최선의 해결책을 보장하지는 않는다는 단점이 있다. 그리디 알고리즘을 사용하기 위해서는 다음의 두 가지 조건을 만족해야 한다. 1. 최적 부분 구조(Optimal Substructure) : 부분 문제의 최적 결과를 전체에 그대로 적용할 수 있다. 2. 탐욕적 선택 속성(Greedy Choice Property) : 이전의 선택이 이후 선택에 영향을 주지 않는다.

▶ 문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ##### 문제 ##### # 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. # 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 # 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다. #..

▶ 문제 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ##### 문제 ##### # LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제는 # 두 수열이 주어졌을 때, # 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. # 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. ##### 입력 ##### # 첫째 줄과 둘째 줄에 두 문..

▶ 문제 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net ##### 문제 ##### # 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. # 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. # 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. ##### 입력 ##### # 입력의 첫 줄에는 테스트 케이스의 ..

▶ 문제 : 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 ##### 문제 ##### # 이 문제는 아주 평범한 배낭에 관한 문제이다. # 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. # 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, # 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. # 준서가 여행에 필요하다고 생각하는 N개의 물건..

▶ 문제 : https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net ##### 문제 ##### # 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. # 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. # 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 # 0이 쓰인 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. # 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을..

▶ 문제 : https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ##### 문제 ##### # 피보나치 수는 0과 1로 시작한다. # 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. # 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. # 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. # n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. #..

동적 프로그래밍(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 방법을 의미한다. 여러 개의 문제로 나누어 해결한다는 점에서 분할 정복(Divide and Conquer)과 유사해 보이지만, 동적 프로그래밍의 경우, 간단한 문제들이 반복적으로 일어난다는 점에서 차이가 있다. 즉, 동적 프로그래밍은 간단한 문제들을 한 번만 해결하고 그보다 복잡한 문제를 풀어나갈 때 똑같은 간단한 문제가 다시 나타나면 그 결과 값을 이용해해결하는 방법이다. 이때, 간단한 문제의 결과 값을 기억하여 반복 수행을 제거하는 과정을 메모이제이션(Memoization)이라고 한다. 동적 프로그래밍을 사용하려면 아래 두 가지 조건을 만족해야 한다. 1. 부분 문제 반복(Overlapp..