hahahia

파스칼의 삼각형이란 아래 사진과 같이 이항계수를 삼각형 모양의 기하학적 형태로 배열한 모양을 듯합니다. ()구하는 점화식은 위와 같이 나타냅니다. 이런식으로 점화식을 구하여 부분 문제를 풀어가며 전체 문제의 해답을 찾아내는 방식을 dp라고 하죠 ㅎㅎ 아래는 n을 입력하면 처음부터 n번째 줄 까지의 파스칼의 삼각형을 구하는 예제 소스입니다 /* 파스칼의 삼각형 구하는 예제(dp) */#include using namespace std; int arr[100][100] = {0, }; int main(){ int n; cin >> n; for(int i=0; i

Heap(힙) 이라는 자료구조를 이용해 정렬을 하는 알고리즘입니다.일반적으로 버블정렬, 삽입정렬, 선택정렬은 O(n^2)의 시간복잡도 이지만힙정렬은 힙의 구조상 시간복잡도가 O(nlogn)으로 상대적으로 효율적인 알고리즘입니다. n^2 시간복잡도의 sort 알고리즘에 비해서 좀 구현이 까다로울 수 있지만 그래도 힙의 구조를 이해하면 쉽게 구현하실 수 있을꺼같아요. 아 그리고.... 힙소트는 힙이라는 자료구조를 만들어둔 상태에서 소트를 하는 알고리즘이기 때문에입력을 받을때부터 Insert함수에서 힙으로 만들어줍니다.이 밑에 있는 요상한 것이 바로 힙(Heap)이라는 건데요. 구조적으로 바이너리 트리를 만족하고,현재 노드v의 원소의 value는 노드v의 left, right(즉 자식이겠죠.)의 원소보다 va..

프로그램 명: bsearch제한시간: 1 초정렬된 수열을 입력으로 받아 이 수열내에 찾고자 하는 수가 있는지 없는지를 구하는 프로그램을 작성하시오.입력입력의 첫 수는 검색 대상이 되는 수의 개수 n ( 1 n; center = n/2; for(int i=0; i> data[i]; cin >> num; // search number left = 0; right = n-1; while(1) { center = (left + right)/2; if(data[center] num) right = center - 1; else if(data[center] == num) { cout

/*made by hahahiamain.cpp */ #include #include #include #include #include #include #include using namespace std; int main(){ int result = 0; string str; cin >> str; int e=1; for(int i=str.length()-1; i>=0; i--) { for(int j=0; j

프로그램 명: minterval제한시간: 1 초서로 다른 정수의 값이 일렬로 주어졌을 때, 가장 큰 합을 가지는 부분 구간을 구하시오. 여기서 부분구간이란 연속된 구간을 의미한다.예를 들어, 다음과 같은 값이 주어지면,-2 9 2 -6 7 -7 5최대 구간은 [9 2 -6 7]이며, 합은 12 이다.입력입력의 끝은 0 으로 인식한다.수의 개수는 2,000 개를 넘지 않는다.출력최대 구간의 합을 출력한다.입출력 예입력 -2 9 2 -6 7 -7 5 0 출력 12출처 | dovelet 대표적인 dynamic programming이라고 볼 수 있겠습니다.. 이걸 모든 경우로 구하려고하면 엄청나게 시간소모가 될 꺼 같지만적당한 점화식을 구해서 구해보면 적은 시간에 답을 뽑아낼 수 있겠죠......dynamic ..

음 보통 알고리즘 문제 풀거나 계산을 많이 하는 과정에서 *2를 하거나 /2를 하는 계산이 꽤나 많이 있는데....(2의 n승 전부)보통은 a *= 2, 또는 a /= 2 이런식으로 곱하기 나누기를 하지만 사실은 그것보다 더 시간을 빠르게 사용하여 계산을 할 수 있다.그것이 바로 쉬프트연산!!!!!!!!! 간단하게 숫자 5로 예를 들어보겠습니다. 숫자 5를 2진수로 나타내면(8bit) 0 0 0 0 0 1 0 1 이런식으로 나타나겠죠??그럼 이 숫자 5에다가 2를 곱해보겠습니다. 그러면 5 * 2 = 10 이 되겠죠이 숫자 10을 다시 2진수로 나타내보도록 하겠습니다 0 0 0 0 1 0 1 0 자 여기서 벌써 알아보신분들도 계실텐데...(아닌가 ㅎㅎ) 1이 있는 비트들이 왼쪽으로 한칸씩 이동한 것을 볼..

Selection Sort(선택 정렬)- n개의 원소들 중에서 첫 번째 값을 키로 하여 남은 데이터 중에서 최소 값을 선택하여 비교한 후, 선택한 값이 키 값보다 작으면 서로 교환, 그렇지 않으면 다음 값을 키로 하여 n-1만큼 반복 수행하는 정렬이다. ex) n=5, 8 3 4 9 7초기 : 8 3 4 9 7 1단계 : (3)(8 4 9 7) 2단계 : (3 4)(8 9 7) 3단계 : (3 4 7)(9 8) 4단계 : (3 4 7 8 9) /* selection.cpp */ #include using namespace std; void swap(int *, int *); int main() { int n, min; int arr[100]; cin >> n; for(int i=0; i> arr[i]; ..

분할정복 접근법을 이용한 merge sort 분할 : 정렬할 n개의 원소의 수열을 n/2개씩 두 개의 부분 수열로 분할한다. 정복 : 병합 정렬을 이용해서 재귀적으로 그 두 부분 수열을 정렬한다. 결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다. -> 여기서 정렬할 수열의 크기가 1이 되면 다 정렬된것이므로 더이상 재귀적 호출은 일어나지 않게됩니다. 병합을 위한 과정으로는 Merge(A,p,q,r)이 필요한데 여기서 A = 배열, p,q,r은 index입니다(p