[알고리즘] 동적계획법

Posted by 백창
2015.10.22 14:47 자료구조&알고리즘/개념

# 동적계획법


 동적계획법은 분할정복법과는 정반대의 방식을 이용하여 문제를 해결한다. 동적계획법은 문제를 더 작은 문제로 분할한다는 점에서는 분할정복법과 비슷하지만 여기서는 작은 문제를 먼저 해결하고 저장하고 다른 계산에 그 저장된 결과를 이용한다.


 동적계획법은 상향식 접근 방법(bottom-up)이다. 계획이란 해답을 구축하는데 배열을 사용함을 의미한다.



# 예시


 파스칼의 삼각형이 비슷한 예시가 되겠다.


 원하는 결과를 얻기까지 결과값들을 배열에 저장하여 그 값을 다음 계산에 이용한다.


int bin(int n, int k){

index i, j;

int B[0..n][0,,k];


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

for( j = 0 ; j <= min( i , k ) ; j++ ){

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

B[i][j] = 1;

else

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

}

}


return B[n][k];

}


'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[알고리즘] 분할정복법  (0) 2015.10.12
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04
이 댓글을 비밀 댓글로

[알고리즘] 분할정복법

Posted by 백창
2015.10.12 20:08 자료구조&알고리즘/개념

# 분할정복법


 분할정복법은 문제를 2개 이상의 더 작은 문제들로 나누어 해결한다. 작은 문제가 여전히 크다면 더 작은 문제들로 계속해서 나눈다. 작은 문제에 대한 해답을 바로 얻을 수 있다면 원래 문제의 해답은 이 해답들을 통합하여 구할 수 있다.

 

  분할정복법은 하향식 접근 방법(top-down)이다. 즉, 문제의 맨 상위 사례의 해답은 아래로 내려가서 작은 사례에 대한 해답을 구함으로써 구한다.


  재귀 함수가 이에 해당한다.


# 예시


  실례로는 binary search가 있다.


  값을 찾기 위해 계속해서 반절로 문제를 쪼개어 해답을 찾는다.


index location(index low, index high) {

index mid;


if(low > high)

return 0;

else {

mid = (low+high)/2;

if( x == S[mid] )

return mid;

else if( x < S[mid )

return location(low, mid - 1);

else

return location(mid + 1, high);

}

}


'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[알고리즘] 분할정복법  (0) 2015.10.12
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04
이 댓글을 비밀 댓글로

[정렬 알고리즘] 시간복잡도

Posted by 백창
2015.10.12 19:19 자료구조&알고리즘/개념

# 정렬 알고리즘 시간 복잡도


 

 최적

 평균

 최악

 퀵소트

 

 

 

 삽입정렬

  

 

 

 선택정렬

 

 

 

 버블정렬

 

 

 

 이진트리 정렬

 

 

 

 합병정렬

 

 

 


'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[알고리즘] 분할정복법  (0) 2015.10.12
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04
이 댓글을 비밀 댓글로

Map 과 HashMap 차이

Posted by 백창
2014.12.26 10:43 자료구조&알고리즘/개념

STL 컨테이너 중 map은 말씀하신 대로 바이너리 서치 트리를 이용합니다.
(일반 binary tree가 아니라, binary search tree 입니다) 구현된 STL제품은 대부분 red-black트리를 이용하고 있습니다.

BST는 평균 탐색 시간이 O(log n)이 되는데, 이는 대부분의 경우 납득할 만한 성능을 보여주지만, 평균 탐색시간을 O(1), 즉 상수시간 안에 탐색을 해내고 싶을 때는 해쉬 테이블을 사용하게 되죠.

해쉬 테이블은 어떤 데이터를 사용하여 해슁 키를 생성합니다. 이를테면 "123456"이라는 문자열의 해슁 키로 123456이라는 정수를 생성하는 식이죠. 해슁 키 생성에는 여러가지 방법을 고려할 수 있습니다. 이를테면, 데이터를 구성하는 모든 자료를 각각의 바이트 별로 더하는 방법도 고려할 수 있고, 자릿수에 가중치를 두어서 더하는 방법도 있을 수 있습니다. 이로서 "근사적으로" 키와 자료 사이에 1:1 대응이 이루어지도록 해슁 키를 생성하고, 이 해슁 키를 배열의 인덱스로 사용하여 자료에 접근합니다. 단, 잘 만들어진 해슁 키는 랜덤 분포가 되므로, 해슁키를 배열의 사이즈로 (대개는 예상되는 자료 양의 2배에 가까운 소수) 나눈 나머지를 배열의 인덱스로 사용합니다.
배열의 접근은 당연히 상수 시간이 걸리므로, 해쉬 테이블 접근은 O(1)의 시간 복잡도가 나타나게 됩니다.

단, 이때 키를 배열의 사이즈로 나눈 나머지가 겹치는 경우가 발생 할 수 있는데, (배열의 사이즈로 소수를 사용하는 이유는 이러한 경우를 최소화하기 위해서입니다) 이런 경우에는 빈 영역을 찾아서 자료를 저장해야 합니다. 이를 해결하는 방법에는 선형 탐색, 2차 탐색 등이 있을 수 있습니다. 선형 탐색의 경우는 blob이 생성되는 문제가 있고, (즉, 한번 충돌이 일어난 영역 근방에서는 계속 충돌이 일어나게 되어 그 근처에 자료가 몰리게 되는 현상), 2차 탐색에서는 그런 문제가 다소 줄어들게 됩니다.

따라서 해쉬테이블의 성능을 좌우하는 것은 해슁 키를 어떻게 적절하게 생성하느냐 하는 것입니다. 해슁 키의 분포 상태가 랜덤에 가까울 수록 성능이 좋아지는 것이죠. 해쉬 테이블이 아직 STL에 포함되지 않은 것은, STL은 그 규정에서 수행 성능을 보장하도록 되어 있습니다. 이를테면, map, set 등의 컨테이너는 삽입, 삭제, 탐색이 모두 O(log n)을 보장하도록 규정되어 있으며, list등의 컨테이너는 지정된 위치의 삽입과 삭제는 모두 O(1)을 보장하고, 탐색, 임의원소 접근은 O(n)을 보장하도록 되어 있죠. vector 컨테이너는 삽인과 삭제, 탐색 모두 O(n)을 보장하되, 임의원소에의 접근은 O(1)을 보장합니다.
그러나, 해쉬 테이블은 사용자 데이터 타입에 대해서는 이러한 성능 보장을 할 수 없기 때문에, 아직 표준에 편입되지는 못하고 있습니다. 물론, 시판되는 STL제품군 중에는 hash_set과 hash_map, hash_list 등의 컨테이너가 포함되어 있는 제품도 있긴 하지만, 정식 표준 컨테이너는 아닙니다.


ref : http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=65660603&qb=aGFzaCBtYXAg7JuQ66as&enc=utf8&section=kin&rank=1&search_sort=0&spq=0&pid=gGP/Ac5Y7u8sssmJZshssc--324518&sid=T4e-XaOYh08AACD-yto

'자료구조&알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] 동적계획법  (0) 2015.10.22
[알고리즘] 분할정복법  (0) 2015.10.12
[정렬 알고리즘] 시간복잡도  (0) 2015.10.12
Map 과 HashMap 차이  (0) 2014.12.26
[개념] 리스트  (0) 2014.11.04
이 댓글을 비밀 댓글로

[알고리즘] N-여왕말 문제(몬테칼로 추정치 - 되추적)

Posted by 백창
2014.08.26 19:45 개발/C언어

 개요


 몬테칼로 추정치는 해답을 모두 찾기 위해서 검사하리라 생각되는 마디의 총 개수를 추정한 것이다. N-여왕말 문제를 백트래킹 기법으로 풀어 몬테칼로 추정값을 구해보도록하자.


 소스





 결과



  1. 창연아 잘썻어 ~~
이 댓글을 비밀 댓글로

[알고리즘] hamiltonian (되추적)

Posted by 백창
2014.08.26 19:41 개발/C언어

 해밀튼의 회로 문제




 소스






 정답


 위 문제에 정답은 없다. 가 정답 

이 댓글을 비밀 댓글로