• 동적 계획법
    - Top-down
    1. 문제를 작은 문제로 나눈다.
    2. 작은 문제를 푼다.
    3. 작은 문제를 풀고, 문제를 푼다.(큰 문제를 풀어 간다.)

    * CODE - 피보나치
     : 트리로 생각하자

    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     : memorization을 이용하면 반복을 줄일 수 있다! 


    int memo[100];
    int fibonacci(int n) {
    	if (n <= 1) {
    		return n;
    	}
    	else {
    		if (memo[n]) {
    			return memo[n];
    		}
    		memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    		return memo[n];
    	}
    }
    

     
    - Bottom-up
    1. 문제를 크기가 작은 문제부터 차례대로 푼다.
    2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
    3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    4. 반복하면 언젠간 풀어야 하는 문제를 풀 수 있다.

    * CODE - 피보나치

    int dp[100];
    int fibonacci(int n) {
    	dp[0] = 1;
    	dp[1] = 1;
    	for (int i = 2; i <= n; i++) {
    		dp[i] = dp[i - 1] + dp[i - 2];
    	}
    	return dp[n];
    }


'Algorithm' 카테고리의 다른 글

에라토스테네스의체  (0) 2016.03.22
알고리즘 - 보간 탐색  (0) 2015.11.14
알고리즘 - 이진 탐색  (0) 2015.11.14
알고리즘 - 순차 탐색  (1) 2015.11.14
알고리즘 - 위상 정렬  (0) 2015.11.14

출처:  http://ohyecloudy.com/pnotes/archives/294/


컨테이너 정렬이 필요할 때, sort를 사용하고 순서가 유지돼야 하면 stable_sort를 사용했다. partial_sort와 nth_element는 한 번도 사용해본 적이 없는데, 일부분만 정렬이 필요하거나 몇 번째 원소를 뽑을 때 유용하게 사용할 수 있을 것 같다. 예를 들면 최고 작은 수 10개만 차례대로 혹은 차례 상관없이 뽑는다던지, 9번째로 작은 수만 뽑는다던지 할 때에 사용하면 좋을 거 같다. 구현하는데 시간을 추가로 쓰는 것도 아니고 이미 구현되어 있는데, 딱 필요한 만큼만 정렬해서 시간을 절약할 수 있다. 아무리 작은 시간이라 하더라도 그냥 낭비하는 건 죄를 짓는 거.

nth_element는 정렬 기준에 따라 몇 번째 원소만 정확히 뽑아준다. 원소를 기준으로 정렬 기준에 맞게 좌우를 나눠주기는 하는데, 그 원소들 사이에 정렬은 되어 있지 않은 상태이다. 

partial_sort는 시작점부터 지정한 위치까지만 정렬해준다. 나머지는 정렬되지 않은 상태로 놔둔다. sort와 stable_sort는 시작점에서 끝점까지 정렬하는데, 정렬되고 난 뒤 stable을 보장 여부가 다르다. 동일한 정렬 기준을 가진 녀석들의 순서가 정렬 후에도 바뀌지 않으면 stable하다고 하는데, 뒤에 소스 코드 예를 보면 단박에 이해된다. 참고로 merge sortinsertion sort가 대표적인 stable sort 알고리즘이고 unstable sort의 대표적인 알고리즘은 quicksort다.

수행 시간은 nth_element < partial_sort < sort < stable_sort 이다.

sort, stable_sort, partial_sort 테스트 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

////////////////////////////////////////////////////////////////////////////////
// Item
////////////////////////////////////////////////////////////////////////////////
struct Item
{
    int     num;
    char    tag;

    explicit Item(int n, char t = ' ') : num(n), tag(t) {}
};

inline bool operator< (const Item& lhs, const Item& rhs)
{
    return lhs.num < rhs.num;    // 숫자만 비교한다.
}

inline std::ostream& operator<< (std::ostream& ost, const Item& item)
{
    ost << item.num << item.tag;
    return ost;
}

정렬 알고리즘에서 호출해주는 operator < 는 숫자만 비교한다. tag는 stable하게 정렬되는지 확인하는 용도로 사용한다.

////////////////////////////////////////////////////////////////////////////////
// main
////////////////////////////////////////////////////////////////////////////////
int main()
{
    const Item itemArray[40] =
    {
        Item (-4, ' '), Item (16, ' '),
        Item (17, ' '), Item (-3, 's'),
        Item (14, ' '), Item (-6, ' '),
        Item (-1, ' '), Item (-3, 't'),
        Item (23, ' '), Item (-3, 'a'),
        Item (-2, ' '), Item (-7, ' '),
        Item (-3, 'b'), Item (-8, ' '),
        Item (11, ' '), Item (-3, 'l'),
        Item (15, ' '), Item (-5, ' '),
        Item (-3, 'e'), Item (15, ' '),
        Item (-4, ' '), Item (16, ' '),
        Item (17, ' '), Item (-3, 's'),
        Item (14, ' '), Item (-6, ' '),
        Item (-1, ' '), Item (-3, 't'),
        Item (23, ' '), Item (-3, 'a'),
        Item (-2, ' '), Item (-7, ' '),
        Item (-3, 'b'), Item (-8, ' '),
        Item (11, ' '), Item (-3, 'l'),
        Item (15, ' '), Item (-5, ' '),
        Item (-3, 'e'), Item (15, ' ')
    };

    typedef std::vector<Item> ItemVector;

    ItemVector v0(
        itemArray, itemArray + sizeof(itemArray) / sizeof(itemArray[0]));
    ItemVector v1(v0.begin(), v0.end());
    ItemVector v2(v0.begin(), v0.end());

    std::sort (v0.begin(), v0.end());
    std::stable_sort (v1.begin(), v1.end());
    std::partial_sort (v2.begin(), v2.begin() + 10, v2.end());

    std::cout << "### sort(begin, end)\n";
    std::copy (v0.begin(), v0.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### stable_sort(begin, end)\n";
    std::copy (v1.begin(), v1.end(), std::ostream_iterator<Item>(std::cout, " "));
    std::cout << "\n\n### partial_sort(begin, begin+10, end)\n";
    std::copy (v2.begin(), v2.end(), std::ostream_iterator<Item>(std::cout, " "));

    return 0;
}

20개 정도로 하니깐 sort로 정렬해도 결과가 stable해서 40개로 늘렸다. VS2005의 딩컴웨어 STL에서는 원소 개수가 32개 보다 작으면 insertion sort를 하기 때문에 20개로 sort를 호출하면 stable한 결과가 나온다. 정렬 알고리즘은 원소를 변경하기 때문에 복사해서 똑같은 원소를 가진 벡터를 3개 만들고 각각을 정렬한 다음 출력했다.

sort는 stablestable의 순서가 엉켜있고 stable_sort는 제대로 출력하고 있다.partial_sort는 [begin, begin+10) 까지만 정렬을 한다.

nth_element 테스트 소스 코드

nth_element 같은 경우는 위와 같은 예제로 하면 확인이 어려워 따로 테스트 코드를 만들었다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

int main()
{
    // VS 2005에서 원소 개수가 32개 이하면 Insertion sort를 한다.
    static const int INSERTION_SORT_THRESHOLD = 33;
    std::vector<int> v;
    v.reserve(INSERTION_SORT_THRESHOLD);

    for (int i = 0; i < INSERTION_SORT_THRESHOLD; ++i)    v.push_back(i);
    std::random_shuffle(v.begin(), v.end());

    std::cout << "### before\n";
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    std::cout << "### nth_element(begin, begin+12, end)\n";
    std::nth_element(v.begin(), v.begin()+12, v.end());
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

VS 2005의 딩컴웨어 STL 구현을 보면 분할 정복 알고리즘(Divide and conquer algorithm)을 사용해서 구현했는데, 여기서도 sort와 같이 분할한 구역 원소 개수가 32개 이하이면 insertion sort을 한다. 그래서 출력해보면 12 앞에 숫자들이 정렬된 상태로 보인다. 처음에 원소를 10개로 잡아 놓고 테스트를 했는데, 전체가 정렬돼서 무척 의아했다. 궁금해서 소스코드를 보니 원소 개수가 32개 이하이면 insertion sort로 정렬하더라.

STLport 5.1.3 으로 돌려본 결과. insertion sort를 하는 threshold가 3이다.


'Programing > C++' 카테고리의 다른 글

inline 함수  (0) 2016.04.12
  • HTTPS(Hypertext Transfer Protocol over Secure Socket Layer)는 월드 와이드 웹 통신 프로토콜인 HTTP의 보안이 강화된 버전이다. HTTPS는 통신의 인증과 암호화를 위해 넷스케이프 커뮤니케이션즈 코퍼레이션이 개발했으며, 전자 상거래에서 널리 쓰인다.
    HTTPS는 소켓 통신에서 일반 텍스트를 이용하는 대신에, SSL이나 TLS 프로토콜을 통해 세션 데이터를 암호화한다. 따라서 데이터의 적절한 보호를 보장한다. HTTPS의 기본 TCP/IP 포트는 443이다.
    보호의 수준은 웹 브라우저에서의 구현 정확도와 서버 소프트웨어, 지원하는 암호화 알고리즘에 달려있다.
    HTTPS를 사용하는 웹페이지의 URL은 'http://'대신 'https://'로 시작한다.

5. HTTPS

SSL은 전자상거래에서의 데이터 보안을 위해서 개발한 통신 레이어다. SSL은 표현계층의 프로토콜로 응용 계층 아래에 있기 때문에, 어떤 응용 계층의 데이터라도 암호화해서 보낼 수 있다.

HTTP는 기본적으로 평문 데이터 전송을 원칙으로 하기 때문에 개인의 프라이버시가 오가는 서비스들(전자상거래, 전자메일, 사내문서)에 사용하기 힘들다. HTTPS는 SSL 레이어위에 HTTP를 통과 시키는 방식이다. 즉 평문의 HTTP 문서는 SSL 레이어를 통과하면서 암호화 돼서 목적지에 도착하고, 목적지에서는 SSL 레이어를 통과하면서 복호화 돼서 웹 브라우저에 전달된다.

간혹 HTTPS를 하나의 프로토콜로 인식하기도 하는데, HTTP와 SSL은 전혀 다른 계층의 프로토콜콜의 조합이다. HTTPS over SSL로 보는게 좀더 정확한 시각이다. 거의 모든 웹 서버와 웹 브라우저와 HTTP 기반의 툴들 - wget, curlab 기타등등 - 이 SSL을 지원한다.

5.1.1. HTTP와 다른 점

  • HTTPS URL은 "https://"로 시작한다. 기본 포트번호는 443이다. HTTP URL은 "http://"로 시작한다. 기본 포트번호는 80이다.
  • HTTP는 평문 데이터를 기반으로 하기 때문에, 유저정보와 같은 민감한 정보가 인터넷 상에 그대로 노출된다. 이 정보는 수집되거나 변조될 수 있다. HTTPS는 이러한 공격을 견딜 수 있도록 설계돼 있다.
  • HTTPS는 인증서를 이용해서, 접속 사이트를 신뢰할 수 있는지 평가할 수 있다.
  • 일반적으로 HTTPS는 HTTP에 비해서 (매우 많이)느리다. 많은 양의 데이터를 처리할 경우 성능의 차이를 체감할 수 있다. 많은 웹 사이트들이 민감한 정보를 다루는 페이지(로그인 혹은 유저정보) 페이지를 HTTPS로 전송하고, 기타 페이지는 HTTP로 전송하는 방법을 사용한다. 하드웨어 SSL 가속기를 이용해서 암/복호화 성능을 높이는 방법을 사용하기도 한다.

출처: http://www.joinc.co.kr/w/Site/Network_Programing/AdvancedComm/HTTP

'Major > Network' 카테고리의 다른 글

HTTP1.0 ~ HTTP2.0  (0) 2016.04.12
네트워크 - 총 정리  (0) 2015.12.18
네트워크 - Link Layer  (0) 2015.12.17
네트워크 - Network Layer  (0) 2015.12.10
네트워크 - Transport Layer  (0) 2015.12.09

+ Recent posts