알고리즘 이론32 [C++/STL] stack을 vector로 변환하기 STL에서 stack은 컨테이너에 대한 접근을 제어하는 목적으로 사용된다. 따라서 iterator를 제공해주지 않기 때문에 iterator을 사용해서 vector를 만들어낼 수 없다. 요소를 제거하면서 vector 생성 stack st; st.push(1); st.push(2); st.push(3); vector arr(st.size()); int index = arr.size() - 1; // copy st to arr while(!st.empty()){ arr[index--] = st.top(); st.pop(); } stack에서는 top을 통해서만 요소를 가져올 수 있기 때문에 top을 이용해서 vector의 뒤에서부터 값을 채워준다. 단, 이 방법을 쓰면 기존 stack에는 요소가 더 이상 남아.. 2021. 1. 21. [DP] 배낭 문제(Knapsack Problem) 다이나믹 프로그래밍 DP의 대표 문제 중 하나인 물건을 넣느냐 빼느냐를 선택하는 0/1 배낭문제. 물건의 개수가 N이고 배낭에 담을 수 있는 최대 무게가 W이다. 물건은 종류별로 1개씩 있다. d[i][j] = 물건을 i번째 까지 배낭에 넣는다고 가정했을 때, 무게 j를 초과하지 않으면서 배낭에 넣을 수 있는 물건들의 가격의 총합의 최대값 d[i][j] = d[i - 1][j] (j = w[i]인 경우, i번째 물건을 넣을 수 있는 경우) d[i - 1][j - w[i]] : i-1번째 물건을 이용, j - w[.. 2020. 11. 28. 이진검색트리 (BST: Binary Search Tree) 이진 검색 트리(Binary Search Tree, BST)는 탐색을 효율적으로 할 수 있는 자료구조 중 하나입니다. 이진 검색 트리의 성질은 다음과 같습니다. - 각 노드에 고유의 값이 있다. - 노드의 왼쪽 서브트리는 노드 값 보다 작은 값들이다. - 노드의 오른쪽 서브트리는 노드 값 보다 큰 값들이다. - 서브트리 또한 이진 검색 트리이다. 생성 노드를 생성하는 방법을 알아보겠습니다. 방법은 우선 첫 번째로 입력받은 수는 루트 노드로 만듭니다. 그 뒤에 입력받는 수는 루트로부터 노드의 수와 비교하여 작으면 왼쪽, 크면 오른쪽 자식 노드로 내려갑니다. 그리고 노드가 없을 때는 해당 위치에 입력받은 값으로 노드를 생성합니다. 예를 들어서 알아봅시다. 자료 : 15 3 8 10 26 38 36 7 9 2.. 2020. 10. 6. brian kernighan's algorithm 2진법 수에서 1의 수(cnt) 를 세는 알고리즘. N = 11010(2) 에서 1의 수를 세보자. 일단 N - 1을 구한다. N - 1 = 11001(2) N, (N - 1)을 AND 연산한다. N & (N - 1) = 11000(2) 연산 결과는 N에서 뒤에서부터 가장 처음나오는 1 비트를 삭제한 결과와 같다. 1비트가 하나 있어서 삭제되었으므로 cnt + 1을 해준다. 이를 N이 0보다 큰경우 반복한다. (N이 0보다 큰 경우 1이 반드시 한 개 있다는 의미이므로) #include using namespace std; int main() { int N; cin >> N; int cnt = 0; while (N > 0) { N &= (N - 1); cnt++; } cout 2020. 7. 24. 문자열 해싱(String Hashing) 해싱 알고리즘은 다양한 문제들을 해결하는데 도움을 준다. 문자열을 효과적으로 비교해야 하는 문제들이 있다. 각 문자들을 비교해서 브루트 포스(brute force) 방법으로 문자열(s1, s2)을 비교하는 경우 시간복잡도는 O(min(|s1|, |s2|))가 된다. 더 효과적으로 비교하는 방법의 아이디어는 문자열을 정수형으로 바꾸는 것부터 시작한다. 문자열 대신 숫자를 비교하게 된다면 시간복잡도는 O(1)이 된다. 문자열의 해시(hash)라 불리는 정수를 얻기 위해 해시 함수(hash function)를 사용한다. 만약 두 문자열 "ss"와 "tt"가 같다면 그들의 해시 값도 같아야 한다. hash(문자열)을 문자열의 해시값이라고 한다면 hash("ss")와 hash("tt")가 같아야 한다. hash(.. 2020. 6. 20. 동전 교환(CC: Coin Change) 동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다. 예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으로 10원을 만드는 경우의 수를 구해보겠습니다. 동전의 가치는 cost 배열에 넣었다고 생각하겠습니다. 즉, cost[] = {0, 1, 2, 5, 10} 입니다. 모든 경우의 수를 구하기 위해서는 2차원 배열이 필요합니다. d[i][j] = i가지 종류의 동전을 사용해서 j금액을 만드는 모든 경우의 수 입니다. 따라서 우리가 구하고자 하는 경우의 수는 d[4][10]이 됩니다. 이제 배열을 채워봅시다. 0행은 0원으로 j금액을 만드는 경우의 수라고 생각하변 됩니다. 0금액을 만드는 방법은 .. 2020. 2. 23. 이전 1 2 3 4 5 6 다음
