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

brute force vs. KMP 알고리즘의 속도를 비교해봤다.제한 조건은 다음과 같다.https://en.wikipedia.org/wiki/algorithm 문서 100개 분량(복사 붙여넣기 X100)검색 문자열 "algorithm" 위 제한 조건으로 C#에서 탐색한 결과 대략적으로 아래의 결과를 보였다.bruteforce - 100msKMP algorithm - 50ms 1회 실행의 실행시간 비가 bruteforce:KMP algorithm = 2:1이 나온다// bruteforceList list = new List();string str = richTextBox1.Text;string pattern = textBox1.Text;for(int i = 0; i // KMP algorithmpriva..

제한시간 내 순열 만들기 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드 순열 자체를 구하는 속도는 빠르지만, 이를 하나씩 출력하는 과정에서 속도를 잡아먹는 것이 많기 때문에 stringstream에 출력할 문자열을 저장한 뒤, 최종에 한번 출력하도록 하여 속도 향상을 꾀함 #include #include #include using namespace std; int visited[9]; int permutationList[9]; stringstream ss; void bt(int maxValue, int..

주어진 배열에서 연속하는 각 요소의 합이 최대인 값 구하기. 코드 #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) ..