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 위 조건을 추가해 점화식을 적용하면 다음..

최대 합이 되는 경로 검색 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 2차원 배열로 구성을 했다변 더 좋았겠지만, 2차원 배열을 굳이 사용하지 않더라도 수식만으로 2차원 배열을 사용하는 것처럼 구성이 가능하다는 것을 보이기 위해 1차원 배열을 사용해봤다. #include using namespace std; int main() { int n; cin >> n; int* arr = new int[n * n]; cin >> arr[0]; for (int i = 1; i > arr[i * n]; arr[i * n] += arr[(i - 1) * ..

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) ..

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