F.R.I.D.A.Y.

주어진 배열에서 연속하는 각 요소의 합이 최대인 값 구하기. 코드 #include using namespace std; #define max(x,y) ((x) > (y) ? (x) : (y)) int main() { int n; int* arr; cin >> n; arr = new int[n]; for (int i = 0; i > arr[i]; int result = arr[0]; { for (int i = 1; i 0 && arr[i - 1] + arr[i] > 0) { arr[i] += arr[i - 1]; } result = max(arr[i], result); } } cout 0 위 조건을 추가해 점화식을 적용하면 다음..

LIS를 해결하는 시간 복잡도 O(nLogn)의 알고리즘 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include using namespace std; int main() { int n; cin >> n; int* input, * dp; input = new int[n]; dp = new int[n + 1]{}; for (int i = 0; i > input[i]; int maxLength = 1..

가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include int main(void){ int size, max = 1; int data[1000], dp[1000]; scanf("%d", &size); for(int i = 0; i d..

계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 설명 DP 공부를 하면서 느낀건데, 규칙성이 있다면 점화식을 구하는게 급선무?라 생각한다. 일단, 문제에서 규칙을 정해주었기 때문에 규칙을 보면 다음과 같다. 여기에서 중요한 것이 (3)인데, 마지막에 대한 설명이 존재하기 때문이다. 따라서 마지막 규칙을 기반으로 하면 다음과 같다. dp[i] = dp[i - 3] + data[i - 1] + data[i]; dp[i] = dp[i - 2] + data[i]; 배열 dp는 여태 계산상에서 가장 높은 수를 찾은 데..

주가 스팬 계산하기 길벗에서 출판한 책 에서 처음으로 나오는 알고리즘은 스택을 이용한 주가 스팬 계산입니다. 마침 스택에 대한 포스트도 연이어 작성 중인 와중에 이 책을 읽고 있어 잘됐다 싶어 포스트 주제.. pang2h.tistory.com 위 포스트에서 주가 스팬(Stock span)이란 알고리즘을 소개한 지 세 달 정도 흘렀네요. 이 알고리즘을 여기서 쓰게 되리라고는 생각해보지 않았는데 어떻게 사용하게 되네요. # tmlTitle.js 코드 분석을 함께 진행합니다. JavaScript를 모른다면 이해가 어려울 수 있습니다. # tmlTitle.js의 v20.02.13. Release Code를 사용합니다. 문제 선택 tmlTitle.js에서의 문제 제가 만든 스크립트 tmlTitle.js는 티스토리..

문제를 해결하는 데 있어서는 많은 방법이 있습니다. 프로그래밍이란 결국 문제를 해결하는 과정을 순차적으로 나열한 것이라고 봐도 무방하겠지요. 오늘 포스트에서는 동적 계획법, 다르게 말하면 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 알아봅니다. Q. 피보나치 수 구하기 갑자기 웬 피보나치 수를 구하느냐구요? 동적 계획법을 설명하는 가장 간단하면서도 이 기술을 처음 접하는 사람들이 이해하기 쉬운 문제이기 때문입니다. 위 문제를 구하라고 한다면 대체적으로 아래와 같은 두 가지 방법 중 한 가지를 이용할 겁니다. // # F[1] = F[2] = 1; int fibonacci1(int n){ // 재귀 함수를 이용한 방법 if(n > 2){ return fibonacci1(n-1) ..

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 입력받은 동전들의 가치로 입력받은 금액을 만드는 동전 개수에서 가장 개수가 적은 값을 출력하는 문제입니다. 문제의 알고리즘 분류를 보면 과 이 들어가 있습니다. 문제 해결에 앞서 그리디 알고리즘에 대해 알아봅니다. 그리디 알고리즘 그리디 알고리즘을 간단히 설명하면 현재 상황에서 가장 최선의 값을 선택하는 알고리즘으로 아래와 같은 상황에서 A 루트를 선택하는 경우입니다. 전체를 보았을 때 B 루트가 최..

길벗에서 출판한 책 에서 처음으로 나오는 알고리즘은 스택을 이용한 주가 스팬 계산입니다. 마침 스택에 대한 포스트도 연이어 작성 중인 와중에 이 책을 읽고 있어 잘됐다 싶어 포스트 주제로 선정하게 되었습니다. 주가 스팬을 구하는 기본적인 알고리즘 구조는 책에서 보실 수 있습니다. 저는 이 책에서 선보이는 의사 코드(pseudo code)를 C언어로 재구성하고자 합니다. 주가 스팬? 먼저 문제를 풀어보기 전에 주가 스팬이 무엇인지 알아봅니다. 주가 스팬은 다음과 같습니다. 왼쪽과 같은 주식 그래프가 존재한다고 생각해봅시다. 이때 1번 그래프는 앞에 주가 스팬을 판단할 값이 존재하지 않으므로 1번의 그래프 주가 스팬은 1입니다. 2번 그래프는 1번 그래프보다 값이 크므로 주가 스팬은 2입니다. 이는 5번 그..

문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라. 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a..

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 2839번: 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N..