Jaegu's Algorithm Blog

1번째 행부터 시작해서 column을 순차적으로 돌면서 dp값을 갱신한다.

채점한 학생의 점수가 모두 같다는 말에는, 책상이 연속적으로 위치해있어야한다는 조건이 숨어있다.

#include <cstdio> #include <iostream> #include <vector> using namespace std; int main(void) {     int N,K;     int result[10001] ={0,};     scanf("%d %d",&N,&K);     vector<int> vec;     for (int i=0; i<N; i++){         int input;         scanf("%d",&input);         vec.push_back(input);     }          //중복을 제외하는 법은 아래와 같이 한번만 계산해야될 부분을 바깥 loop에 감싼다.     for (int i=0;i<vec.size();i++)     {         for (int j=1;j<=K;j++){             if ((j-vec[i]) < 0)                 continue;             if ((j-vec[i]) == 0)                 result[j]+=1;             else                 result[j]+=result[j-vec[i]];         }     }     printf("%d",result[K]); }

http://bowbowbow.tistory.com/26

출처 : https://o-tantk.github.io/posts/finding-median/ (감사합니다!) 중앙값 찾기 중앙값은 정렬된 배열에서 찾아야 한다. 가장 먼저 정렬을 수행해야 한다.정렬 후엔, 단순히 배열 크기의 절반에 해당하는 인덱스에 접근해 반환하면 된다. 실시간으로 중앙값(Running Median) 찾기 수행 속도가 훨씬 빠른, 추가/삭제가 정렬과 함께 이루어지는 자료 구조를 이용, Heap 알고리즘 Max heap은 최대값에 바로 접근할 수 있다. Min heap은 최소값에 바로 접근할 수 있다. Heap의 두 성질 이용해, 중앙값보다 작은 값들은 Max heap에, 중앙값보다 큰 값들은 Min heap에 저장하는 방식으로 중앙값을 찾는 알고리즘을 구현할 수 있다. 아래의 상황을 보자. 먼저, 작은 값과 큰 값을 나눌 기준이 필요하다. 중앙값이 아니라 굳이 기준이라 표현한 이유는, 개수가 짝수일 때를 고려해서이다. 기준은 어차피 가운데에 있으니, 변수를 따로 만들 필요 없이 Max heap 또는 Min heap에 포함시키면 된다. 여기선 Max heap을 이용했다. 첫 번째 입력은 별 수 없이 기준이 된다. 홀수개이므로 중앙값은  3 이다. 나머지는 기준보다 작다면 Max heap에, 크다면 Min heap에 넣는다. 그리고, Max heap과 Min heap의 크기가 균형되도록 조절한다. 다만, 기준을 고려해 기준을 가진쪽이 하나는 더 클 수 있도록 허용한다. 2 는 기준보다 작으니 Max heap에 넣지만 균형을 맞추기 위해 Max heap의 최대값을 이동시킨다. 짝수개이므로 중앙값은  2 와  3 의 평균이다. 4 는 기준보다 크니 Min heap에 넣지만 균형을 맞추기 위해 Min heap의 최소값을 이동시킨다. 홀수개이므로 중앙값은  3 이다. 1 은 기준보다 작으니 Max heap에 넣지만 균형을 맞추기 위해 Max heap의 최대값을 이동시킨다. 짝수개이므로 중앙값은  2 와  3 의 평균이다. 입력이 들어올 때마다 한 번의

정의 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리 된다.  제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. running time 플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 O(V^3) 의 시간 복잡도를 갖는다.  경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 O(V) 의 시간 복잡도를 갖는다.  종종 데이크스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다. 소스코드 : https://github.com/JaeguKim/Algorithm/tree/master/Floyd 추가 참고 : http://hsp1116.tistory.com/45

선형 검색(Linear Search) 다른이름으로 순차 검색(Sequential Search) 이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다. 선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘 이분  탐색(Binary Search) 선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘 이지만 이진검색은 중간값부터 탐색 선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다. 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점  데이터의 집합이 반드시 정렬(Sort)되어야 한다는 단점이 있습니다. 출처: http://andrew0409.tistory.com/143 [C 읽어주는 오빠] 출처: http://andrew0409.tistory.com/143

정의 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘 알고리즈 개요 데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다. 데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다. 경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 실행시간 개의 변과  {\displaystyle n} 개의  꼭짓점 을 가진  그래프 에 대해  대문자 O 표기법 으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다. 가장 간단한 구현으로,  Q 의 집합을  연결 리스트 나  배열  구조로 구현하고 Extract-Min(Q) 함수를 단순한  선형 탐색 으로 구현했을 때 실행 시간은  {\displaystyle O(n^{2})}  시간이 된다. 만약 희소 그래프(sparse graph), 즉  {\displaystyle n^{2}} 보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는,  인접 리스트 와 바이너리  힙  또는  피보나치 힙 으로 구현한  우선순위 큐 를 이용해 데이크스트라 알

■ 방법1 : 비재귀로 구현 quick_sort()함수로 20,000개 정도의 정수를 정렬하다보면 갑자기 이상한 문자가 나오면서 실행이 중지되는 현상이 생길 수 있다. 이는 내부 스택의 오버플로로 프로그램이 강제로 중지되기 때문이다. 한 번의 재귀 호출로 복귀 주소 2바이트, n 2바이트, a 2바이트해서 모두 6바이트의 스택이 사용된다. 20,000개 정도의 정수를 퀵 정렬하기 위해서는 정확히 분할이 이등분된다면 재귀의 깊이가 15(log220000)이면 되므로 15*6=90바이트 밖에 스택이 쓰지 않는다. 하지만 최악의 경우(역순 배열이나 정렬된 배열의 경우)N만큼 재귀가 깊어지므로 20000*6=120000바이트 약 120KB 가량이 소모되어 스택은 넘치게 된다. 이런 문제를 해결할 수 있는 방안은 재귀 호출을 없애고 직접 스택을 만들어 쓰는 것이다. 이렇게 직접 스택을 만들어쓰게되면 함수 호출에 의한 오버헤드 현상으로 속도가 시원 스럽게 오르지 않는다. 정렬된 배열과 역순 배열의 경우 그렇지 않은 경우에 비해 무려 40배 가량이나 느리다. ■ 방법2 : 난수 분할 정렬된 배열과 역순 배열일 때 퀵 정렬의 속도가 현저히 느려지는 것은 축값으로서 가장 오른쪽의 값을 택하기 때문에 결과적으로 가장 큰 값이나 가장 작은 값이 축값이 되기때문이다. 이 문제의 해결 방법은 축값을 잘 선택하는 것이다. 하지만 입력되는 자료가 임의적인 것이므로 일관적인 방법으로 축값을 잘 선택하는 방법은 없다 한 가지 대안으로 제시되는 것은 축값을 난수(random)으로 선택하는 것이다. ■ 방법3 : 삽입정렬 큇 정렬이 더 이상 빨라질수 있는가? 퀵정렬은 구간을 쪼개면서 정렬을 해 나간다. 큰 구간을 쪼개나가는 것은 퀵 정렬로 하고 작은 구간에 대해서는 더 성능좋은 알고리즘을 사용하면 된다. 삽입 정렬은 구현이 간단하면서도 작은 크기의 배열에서는 매우 효율이 좋다. 또한 삽입 정렬은 추가적인 메모리를 필요치 않는다. 작은 구간에 대한 삽입 정렬을 사용 하는 것은 퀵 정렬의 재귀의

위 그림  출처 :http://findfun.tistory.com/385 정의 최소비용 신장트리란 spanning tree의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 '최소 비용 신장 트리'라고 한다. 최소비용 신장트리에는 사이클이 생겨서는 안된다.(트리의 기본조건) 구현 알고리즘 1) 크루스칼  가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식 시간복잡도 크러스컬 알고리즘은 O(Elog V) 시간 안에 동작한다고 증명 2)프림 하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식 시간복잡도 참고: https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그림출처 : http://dev-ahn.tistory.com/39 삽입정렬의 경우, 정렬대상이 완전히 정렬된 상태라면 안쪽 for문에서 걸리지기 때문에 시간복잡도는 O(n)이 된다. 병렬정렬의 경우, 임시메모리가 필요하다는 단점이 있다. 하지만 연결리스트를 정렬할 때는이런한 단점을 극복할 수 있다. 힙정렬의 경우도 힙저장공간이 필요하다는 단점이 있다. 퀵소트의 경우, 최악의 경우는 이미 데이터들이 정렬된 상태이고 pivot이 가장 작은 값으로 결정되는 경우이다. 이 경우 데이터가 둘로 나뉘는 횟수 k = n이고 되고 결과적으로 O(n^2)이 된다. 참고로, pivot값을 가운데에 두면 성능이 개선된다. Radix(기수)정렬의 경우, 성능은 가장좋지만 적용할 수 있는 범위가 제한적이다.

Priority Queue : 우선순위가 높은 데이터부터 나오는 queue Heap이란 : 위키백과에 따르면 '특별한 트리를 기본으로 하는 자료구조이다.'라고 설명되어 있습니다. 여기서 특별한 트리란 우리가 전에 배운 완전 이진 트리를 말하며, 힙 자료구조는 최대 힙(Max Heep) 과 최소 힙(Min Heep) 으로 나뉘며 이러한 힙은 최대값 또는 최소값을 짧은 시간내에 찾기 위해서 만들어진 자료구조입니다. 최대 힙이란 부모 노드의 값이 항상 자식 노드의 값보다 크다는 것이며, 최소 힙은 부모 노드의 값이 항상 자식 노드의 값보다 작다는 것입니다.  출처: http://blog.eairship.kr/249 [누구나가 다 이해할 수 있는 프로그래밍 첫걸음] 소스코드: https://github.com/JaeguKim/Algorithm/tree/master/Heap

Dynamic Programming 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)으로 나누어 푼 다음,  그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. Greedy Algorithm과의 비교 동적 계획법은 주먹구구식이라는 단점이있다. 이러한 단점을 극복하기 위하여 그리디 알고리즘이 등장했다. 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 MST(최소 비용 나무 문제)등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 입증되었다. 그리디 알고리즘과 동적 계획법을 비교하자. 우리가 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다. 반면 그리디 알고리즘은 전체적인 상황을 고려하지 않고, 순간순간 교차로가 보일 때마다 가장 빠른 경로를 검색하여 찾아줄 것이다. 물론 동적 계획법으로 경로를 검색하는 동안 우리가 운전을 잠깐 쉬어야 하듯이, 우리는 동적 계획법을 사용하면 약간의 시간이 걸린다는 단점이 있다. 그러나 이렇게 얻어낸 경로는 (교통 환경이 변하지 않았다는 가정 하에) 우리가 갈 수 있는 가장 빠른 길이 된다고 장담할 수 있다. 반면 그리디 알고리즘은 즉효성이 있는 대신, 항상 최적의 경로를 찾아주지는 않는다. 각 구간마다 최적의 경로를 찾는다고 해도 그것이 전체적으로 최적의 경로가 되지는 않기 때문이다. 즉, 동적 계획법은 그리디 알고리즘에 비해 시간적으로는 효율적이지 못할 수는 있어도, 그 결과에 대해서는 효율적인 값을 구할 수가 있다.

P의 정의 P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. NP의 정의 NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자 NP Complete의 정의는? NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다.  NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다.  반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. NP Hard의 정의 NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에 속한다. 즉, NP-완전은 NP와 NP-난해의 교집합이다.

위상 정렬(topological sorting) 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 이 점에서 비순환 유향 그래프(directed acyclic graph) 이다. 소스코드 : https://github.com/JaeguKim/Algorithm

그래프(영어: graph) 일련의 꼭짓점(V)들과 그 사이를 잇는 변(E)들로 구성된 구조 트리의 구조 : cycle이 없는 graph 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고 , 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다 이진 트리의 종류 정이진 트리(Full Binary Tree) 전체 노드의 수가 2^(k-1)개의 노드이고, 레벨 i마다 2^(i-1)개의 노드들로 꽉 찬 트리를 말한다. 전이진 트리(Complete Binary Tree) 전이진 트리는 노드의 수가 n개일 때, 정이진 트리의 각 노드에 붙인 1~n의 일련변호와 1:1로 대응되는 트리, 중간에 빈 부분이 있으면 전이진 트리가 될 수 없다.

함수 맨 윗줄에  #define _CRT_SECURE_NO_WARNINGS 를 추가시킴

cin 대신에 scanf를 cout 대신에 printf를 사용하자!

 *QuickSort 버전* #include <iostream> #include <string> using namespace std ; void swap( int arr[], int a, int b) {     int temp = arr[a];     arr[a] = arr[b];     arr[b] = temp; } int partition( int arr[], int left, int right) {     int pivot = arr[left];     int low = left + 1 ;     int high = right;          while (low <= high)     {         while (low <= right && pivot >= arr[low])             low++;                  while (high >= left+ 1 && pivot <= arr[high])             high--;                  if (low <= high)         {             swap (arr, low, high);         }     }          swap (arr, left, high);          return high; } void quickSort( int arr[], int left, int right) {     if (left <= right)     {         int pivot = partition (arr, left, right);         quickSort (arr, left, pivot- 1 );         quickSort (arr, pivot+ 1 , right);     } } int main( int argc,

#include <iostream> #include <string> using namespace std ; int main( int argc, const char * argv[]) {     string str;     getline ( cin ,str);          int cnt = 0 ;          for ( int i = 0 ; i < str. length (); i++){         if (str. at (i) == ' ' )             cnt++;     }          if (str. at ( 0 ) == ' ' )         cnt--;     if (str. at (str. length () - 1 ) == ' ' )         cnt--;          cout << cnt+ 1 ; }

탐욕 알고리즘 은 최적해를 구하는 데에 사용되는 근사적인 방법으로,  여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.  순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.  탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다. 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은  근사 알고리즘 으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다. 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를  매트로이드 라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다. (예시) <다익스트라 알고리즘> 음의 가중치가 없는  그래프 에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는  알고리즘 이다.  방향그래프,무방향 그래프 모두 상관없다. *Minimum Spanning Tree (최소 신장 트리) <크루스칼 알고리즘> Kruskal Algorithm과 Prim Algorithm은 Greedy Algorithm를 적용 하는 알고리즘 중의 하나이다.  최소신장트리를 구성할 때, 최적의 해를 구하려면

#include <iostream> #include <string> #include <ctype.h> using namespace std; int main(int argc, char * argv[]) { //input이 없을때 에러발생 if (argc < 2) { cout << "에러입니다. 숫자를 입력하세요." << endl; return 0; } int len = strlen(argv[1]); //숫자이외의 input이 들어왔을때 에러발생 for (int i = 0 ; i<len; i++) { if (isdigit(argv[1][i]) == 0) { cout << "알파벳이 입력으로 들어왔습니다." << endl; return 0; } } int input = stoi(argv[1]); //여기서부터 소수 판별하는 부분     for (int i = 2; i < input; i++){         if (input % i == 0) { cout << "합성수 입니다." << endl; return 0; }            }      cout << "소수입니다." << endl; return 0; }