파스칼의 삼각형이란 아래 사진과 같이 이항계수를 삼각형 모양의 기하학적 형태로 배열한 모양을 듯합니다.


a_{n1} = 1
a_{nn} = 1
a_{nk} = a_{{n-1}{k-1}} + a_{{n-1}{k}} (n, k>=0)

구하는 점화식은 위와 같이 나타냅니다. 이런식으로 점화식을 구하여 부분 문제를 풀어가며 전체 문제의 해답을 찾아내는 방식을 dp라고 하죠 ㅎㅎ 

아래는 n을 입력하면 처음부터 n번째 줄 까지의 파스칼의 삼각형을 구하는 예제 소스입니다


/* 파스칼의 삼각형 구하는 예제(dp) */

#include <iostream>

using namespace std;

 

int arr[100][100] = {0, };

 

int main(){

        int n;

        cin >> n;

        for(int i=0; i<n; i++){

               for(int j=0; j<=i; j++){

                       if(i == 0 || j == 0){

                              arr[i][j] = 1;

                       }

                       else{

                              arr[i][j] = arr[i-1][j] + arr[i-1][j-1];

                       }

               }

        }

 

        for(int i=0; i<n; i++){

               for(int j=0; j<=i; j++){

                       cout << arr[i][j] << " ";

               }

               cout << endl;

        }

 

        return 0;

}

신고

Heap(힙) 이라는 자료구조를 이용해 정렬을 하는 알고리즘입니다.

일반적으로 버블정렬, 삽입정렬, 선택정렬은 O(n^2)의 시간복잡도 이지만

힙정렬은 힙의 구조상 시간복잡도가 O(nlogn)으로 상대적으로 효율적인 알고리즘입니다. 


n^2 시간복잡도의 sort 알고리즘에 비해서 좀 구현이 까다로울 수 있지만 그래도 힙의 구조를 이해하면 쉽게 구현하실 수 있을꺼같아요.


아 그리고.... 힙소트는 힙이라는 자료구조를 만들어둔 상태에서 소트를 하는 알고리즘이기 때문에

입력을 받을때부터 Insert함수에서 힙으로 만들어줍니다.

이 밑에 있는 요상한 것이 바로 힙(Heap)이라는 건데요.


구조적으로 바이너리 트리를 만족하고,

현재 노드v의 원소의 value는 노드v의 left, right(즉 자식이겠죠.)의 원소보다 value값이 작은 조건을 만족하는 형태를 가집니다.


그리고 이걸 배열로 구현하게 된다면

현재 자기자신의 노드의 index를 i라 하면, 왼쪽 노드의 인덱스는 index*2, 오른쪽 노드는 index*2+1가 됨을 알수있죠. 밑에 그림에서 보면 last node의 index를 가리켜야 한다고 하는데요. 이 index는 바로 heap의 size와 같다는걸 알 수 있죠. (자세한 Heap Data Structure 설명은 다음에 포스팅 하도록 하겠습니다.)



/*

Heap_Sort

Made by Hahahia

*/

#include <iostream>

using namespace std;

 

int heap[1000000],heapSize; // heap DataStructure, heapsize

 

void Insert(int element) // heap 원소를 삽입하는 함수

{

        heapSize++;

        heap[heapSize] = element;

        int now = heapSize; // heapSize = index

        while(heap[now/2] > element) // 부모의 원소가 자식의 원소보다 경우

        {

               heap[now] = heap[now/2]; // 자리를 바꿔요

               now /= 2;

        }

        heap[now] = element; // 최종적으로 힙에 들어갈 자리를 잡아요.

}

int main()

{

        int n;

        int size;

        int temp;

        int index;

        heapSize = 0;

        cout << "input n : " ;

        cin >> n;

        int element;

        for(int i=1; i<=n; i++)

        {

               cout << "input " << i << " : ";

               cin >> element;

               Insert(element); // 힙정렬의 특징으로 구조를 만들어둬야 합니다.

        }

        cout << "Heap Sort \nresult : ";

        size = n;

        for(int i=1; i<=n-2; i++){

               temp = heap[1];

               heap[1] = heap[size];

               heap[size] = temp; // heap size 감소

               size--;

               index = 1;

               while(1) // heap 으로 재정렬을 합니다.

               {

                       if(size==2)

                       {

                              if(heap[index] <= heap[index+1])

                              {

                                      temp = heap[index];

                                      heap[index] = heap[index+1];

                                      heap[index+1] = temp;

                                      break;

                              }

                       }

                       if(heap[index] >= heap[index*2] && (heap[index*2] <= heap[index*2+1]))

                       {

                              temp = heap[index];

                              heap[index] = heap[index*2];

                              heap[index*2] = temp;

                              index = (index*2);

                       }

                       else if(heap[index] >= heap[index*2 + 1] && (heap[index*2] >= heap[index*2+1]))

                       {

                              temp = heap[index];

                              heap[index] = heap[index*2+1];

                              heap[index*2+1] = temp;

                              index = (index*2 + 1);

                       }

 

                       if(((index*2) >= size) || ((heap[index] <= heap[index*2] && heap[index] <= heap[index*2+1])))

                               break;

               }

        }

        for(int i=n; i>=1; i--){

               cout << heap[i] << " ";

        }

        cout << endl;

        return 0;

}

 

실행결과



신고
  1. - 2013.05.14 16:49 신고

    1. 힙 삽입 시 whlle 조건문에 s > 1 을 넣어주셔야 음수일 때도 작동해요
    2. s == 2 일때는 무조건 break 여야 하는데 if 구문 안에 break를 넣으셨네요

프로그램 명: bsearch
제한시간: 1 초

정렬된 수열을 입력으로 받아 이 수열내에 찾고자 하는 수가 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

입력의 첫 수는 검색 대상이 되는 수의 개수 n ( 1 <= n <= 500,000 ) 이고 , 다음 n 개의 수 와 검색대상 수가 입력으로 주어진다. 주어지는 수열의 수와 검색되상의 수는 정수 범위를 넘지 않고 , 입력되는 첫 수가 첫번째 수이다.

출력

찾으면 몇 번째 있는 수인지를 출력하고 찾고자 하는 데이터가 없으면 "not found" 를 출력한다.

입출력 예

입력

5
2 4 6 8 10
4

출력

2

입력

5
2 4 6 8 10
5

출력

not found
출처 | dovelet

정렬된 데이터라고 가정할 때 logN번으로 가장 효과적으로 특정한 데이터를 찾아내는 알고리즘 기법을 binary search(이진탐색)이라고 합니다. 사실은 이 기법은 업다운게임(?)을 생각해보면 쉽게 이해하실 수 있습니다. 업다운게임도 결국에는 연속된 수들을 기준으로 외치는 숫자보다 크면 업! 작으면 다운!을 외치면서 값을 찾아내기 때문이죠.

소스코드를 보시면 쉽게 이해가능 합니다.




/*

made by hahahia

binary.cpp

*/

 

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

int data[500001];

int main(){   

 

        int n, left, right, center, num;

        cin >> n;

        center = n/2;

        for(int i=0; i<n; i++) // input data

               cin >> data[i];

        cin >> num; // search number

        left = 0;

        right = n-1;

        while(1)

        {

               center = (left + right)/2;

               if(data[center] < num)

                       left = center + 1;

               else if(data[center] > num)

                       right = center - 1;

               else if(data[center] == num)

               {

                       cout << center+1 << endl; // found number. and program exit

                       return 0;

               }

               if(left > right) break;

        }

        cout << "not found" << endl; // not found

        return 0;

}

 

신고

/*

made by hahahia

main.cpp */


#include <iostream>

#include <vector>

#include <cstdlib>

#include <cmath>

#include <iterator>

#include <algorithm>

#include <string>

 

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<str.length()-i-1; j++)

                       e*=2;

               if(str[i] == '1')

                       result += e;

               e=1;

        }

        cout << result << endl;

        return 0;

}






출력 결과


0011

3


1001

9


1100

12

신고
  1. c언어초보 2014.02.07 19:07 신고

    이건 2진수를 10진수로 변환 하는것 같은데요.

프로그램 명: 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 programming이란 일부분의 답을 구해 하나씩 더해가 최종 답을 구하는(?) 그런

프로그래밍 기법이라고 볼 수 있습니다.

소스코드를 보시면 더 이해가 빠르실거에요.



main.cpp

#include <iostream>

#include <vector>

#include <iterator>

#include <algorithm>

#include <string>

#include <cmath>

using namespace std;

int main()

{

   int a[10000], dp[10000]={0};

   int result, i, n;

   for(i=0; ; i++){

           cin >> a[i];

           if(a[i]==0)

                break;

   }

   n = i;

   for( i = 0 ; i < n ; i++)

dp[i] = a[i] > a[i] + dp[i-1] ? a[i] : a[i] + dp[i-1];

   result = dp[0];

   for( i = 1 ; i <n ; i++)

      if ( result < dp[i] ) result = dp[i];

   cout << result << endl;

}

신고

음 보통 알고리즘 문제 풀거나 계산을 많이 하는 과정에서 *2를 하거나 /2를 하는 계산이 꽤나 많이 있는데....(2의 n승 전부)

보통은 a *= 2, 또는 a /= 2 이런식으로 곱하기 나누기를 하지만 사실은 그것보다 더 시간을 빠르게 사용하여 계산을 할 수 있다.

그것이 바로 쉬프트연산!!!!!!!!!


간단하게 숫자 5로 예를 들어보겠습니다. 숫자 5를 2진수로 나타내면(8bit)


 0

0

 0

 0

 1

 0

 1


이런식으로 나타나겠죠??

그럼 이 숫자 5에다가 2를 곱해보겠습니다. 그러면 5 * 2 = 10 이 되겠죠

이 숫자 10을 다시 2진수로 나타내보도록 하겠습니다


 0

 0

 0

 0

 1

 0

 1

 0   


자 여기서 벌써 알아보신분들도 계실텐데...(아닌가 ㅎㅎ) 1이 있는 비트들이 왼쪽으로 한칸씩 이동한 것을 볼 수 있죠 ㅎㅎ


#include <iostream>

using namespace std;

 

int main(){

        int a = 5;

        a = a << 1;

        cout << a << endl;

        return 0;

}


이런식으로 하게 되면 a는 10이 출력될 것입니다.

마찬가지로 5에서 4(2의 2승)을 곱하면 20이 되겠죠.

그렇게되면 쉬프트연산을 하게되면


 0

 0

 0

 1

 0

 1

 0

 0      


자 두칸씩 더 왼쪽으로 간 것을 확인할 수 있나요?ㅎㅎ

a = a << 2; 이런식으로 하면 a가 5였다면 20으로 되겠습니다.

 

그리고 반대로 현재 20인 a에서

a = a >> 2; 쉬프트 연산을 반대로 하게되면 어떻게 될까요



 0

 0

 0

 0

 0

 1

 0

 1    


자 보이시나요?? 다시 오른쪽으로 두칸 이동해서 20/4 = 5 가 되겠죠.


#include <iostream>

using namespace std;

 

int main(){

        int a = 20;

        a = a >> 2;

        cout << a << endl;

        return 0;

}

 

이런식으로 코딩해서 출력해보면 a의 값이 5가 나온다는 것을 알 수 있습니다.

2의 n승(n=1, 2, 3, 4, 5, .....)의 곱셈 나눗셈 연산을 이러한 쉬프트 연산을 이용해서 더 빠르게 계산할 수 있겠습니다.ㅎㅎ

신고


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 <iostream>

using namespace std;

void swap(int *, int *);

int main()

{

    int n, min;

        int arr[100];

        cin >> n;

        for(int i=0; i<n; i++)

               cin >> arr[i];

    for(int i=0;i<n-1;i++){                                                       

        min=i;       // 최소값의 인덱스 설정                

        for(int j=min+1;j<n;j++){       

            if(arr[min] > arr[j]) // 현재 최소값이 j번째 원소보다 경우        

                min=j;            // 현재 최소값의 인덱스 변경

        }                                     

        if(min != i)                    

            swap(&arr[i],&arr[min]);     // swap 함수 호출(call by reference)    

    }                                   

        for(int i=0; i<n; i++)

               cout << arr[i] << "\t";

        cout << endl;

    return 0;                                      

}

void swap(int *a, int *b)

{

        int temp;

        temp = *a;

        *a = *b;

        *b = temp;

}

 

신고
  1. 헐.. 2012.04.23 00:00 신고

    과제하려고 쑤시다가 민화형 블로그에 오네
    설마 했는데 진짜 민화형꺼네..
    충격

분할정복 접근법을 이용한 merge sort

분할 : 정렬할 n개의 원소의 수열을 n/2개씩 두 개의 부분 수열로 분할한다.
정복 : 병합 정렬을 이용해서 재귀적으로 그 두 부분 수열을 정렬한다.
결합 : 정렬된 두 개의 부분 수열을 병합해 하나의 정렬된 수열을 만든다.

-> 여기서 정렬할 수열의 크기가 1이 되면 다 정렬된것이므로 더이상 재귀적 호출은
일어나지 않게됩니다.

병합을 위한 과정으로는 Merge(A,p,q,r)이 필요한데 여기서
A = 배열, p,q,r은 index입니다(p <= q < r) 
Merge는 두 부분 배열 A[p...q]와 A[q+1...r]이 정렬되어 있다고 가정하고
이들을 병합해서 하나의 정렬된 배열을 만들면서 원래의 부분 배열인
A[p...r]을 대체합니다.

/* merge.cpp */

 

#include <stdio.h>

#define LEN 9

 

void merge_sort(int num[], int start, int end);

void merge(int num[], int start, int median, int end);

int main()

{

        int i;

        int arr[LEN] = {10, 67, 63, 17, 23, 78, 12, 73, 86};

        merge_sort(arr, 0, LEN-1);

        for(i=0; i<LEN; i++)

        {

               printf("%d\t", arr[i]);

        }

}

void merge_sort(int num[], int start, int end) // arr 덩어리의 배열로 나눈다

{

        int median = (start + end) / 2; // 중간값 설정

        if(start < end)

        {

               merge_sort(num, start, median); // 각각의 덩어리로 재귀함수()

               merge_sort(num, median+1, end); // 각각의 덩어리로 재귀함수()

               merge(num, start, median, end); // 각각의 덩어리를 뭉치면서 정렬

        }

}

void merge(int num[], int start, int median, int end)

{

        int i, j , k, m, n;

        int temparr[LEN]; // 임시 배열

        i = start;

        j = median+1;

        k = start;

        while(i<=median && j<=end)

        {

               temparr[k++] = (num[i] > num[j]) ? num[j++] : num[i++];

          // 작은 숫자를 찾아 임시 배열에 넣고 어느쪽 덩어리던 index 끝에 닿으면  빠져나가도록한다      

 }

// 아직 배열에 속하지 못한 부분들을 넣기위한 작업

        m = (i>median) ? j : i; // // 아직 원소가 남아있는 덩어리가 어디인지 파악

        n = (i>median) ? end : median; // for문의 index 정하는 작업

        for(; m<=n; m++) // m,n으로 배열에 속하지 못한 원소를 채워넣는다

               temparr[k++] = num[m];

 

        for(m=start; m<=end; m++)

               num[m] = temparr[m]; // 임시 배열에서 원래 배열로 데이터 넣기

}


신고

삽입정렬
- 사람들이 카드놀이를 할 때 손에 쥔 카드를 정렬하는 방식을 생각해보면 되겠습니다.  일단 왼손에 아무것도 쥐지 않고, 카드는 탁자위에 있다고 해봅시다. 탁자에 카드를 한장씩 가져와 왼손의 적절한 위치에 넣습니다. 카드를 삽입할 적절한 위치를 찾기 위해 왼손의 카드들을 찾아보겠죠. 참고로 왼손의 카드들은 다 정렬된 상태가 되겠습니다. 밑의 그림을 확인해보세요...


각각 a,b,c의 첫번째 테이블에서 각각 가리키는 화살표를 기준으로 위의 값들은 왼손에 있는카드(정렬된 상태)라고 보면 되겠고, 화살표 밑의 값들을 오른손에서 왼손의 적절한 위치에 삽입할 카드라고 보면 되겠네요. 

/* insertion.cpp */

#include <iostream>

using namespace std;

int main()

{

        const int arraySize = 10;

        int data[arraySize];

        int insert;

        for(int i=0;i<10; i++)

               cin >> data[i];

        for(int next=1; next < arraySize; next++)

        {

               insert = data[next];

               int moveItem = next;

               while((moveItem > 0) && (data[moveItem - 1] > insert))

               {

                       data[moveItem] = data[moveItem - 1];

                       moveItem--;

               } 

               data[moveItem] = insert;

        }

        for(int i=0;i<10;i++)

        cout << data[i] << " " ;

} // insertion sort

신고

#include <stdio.h>

int u_gcd(int, int);
int u_lcm(int, int, int);
int main()
{
 int a, b, gcd, lcm;
 printf("두 수를 입력하세요 : ");
 scanf("%d %d", &a, &b);
 gcd = u_gcd(a, b);
 printf("두 수의 최대공약수는 %d입니다.\n", gcd);
 lcm = u_lcm(a, b, gcd);
 printf("두 수의 최소공배수는 %d입니다.\n", lcm);
 return 0;
}
int u_gcd(int x, int y)
{
 if(x==y)
 {
  return x;
 }
 else if(x > y)
 {
  return u_gcd(x-y, y);
 }
 else
 {
  return u_gcd(x, y-x);
 }
}
int u_lcm(int x, int y, int Gcd)
{
 return x * y/ Gcd;
}

신고

+ Recent posts