cpp
-
자료구조: Array Table 구현하기 (feat. c++)알고리즘/자료구조 2021. 5. 31. 20:07
Characteristic: - Table class is an array Table class Operations: - insert - lookup - deleteKey #include #include using namespace std; const int MAX_TABLE = 100; template class Table { public: Table(); bool lookup(tableKeyType lookupKey, tableElementType& data); void insert(tableKeyType insertKey, tableElementType insertData); void deleteKey(tableKeyType deleteKey); private: struct item { tableK..
-
알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)알고리즘 2020. 11. 9. 23:46
부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다. 합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다. 전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는 조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 예를 들어보자 n = 3, W =6 w1 = 2, w2 = 4, w3 = 5 이라 할때 각 노드들의..
-
알고리즘: 슈트라센(Strassen) 행렬 곱셈 알고리즘 (feat.c++ ,pseudocode)알고리즘 2020. 9. 27. 15:33
이번 포스팅은 일반적인 정방행렬의 곱셈을 알아보고 더 빠른 슈트라센(Strassen) 행렬곱셈에 대해서 알아본다. void matrixMulti(const int a[][N], const int b[][N], int c[][N]) { for (int i = 0; i < N;i++) for (int j = 0; j < N; j++) { c[i][j] = 0; for (int k = 0; k < N; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } } 일반적인 행렬곱셈은 우리가 아는 행렬곱셈 그대로 코딩하면 위와 같은 3중 for문으로 구성된다. 1. 시간복잡도 분석 입력 크기 행과 열의 수가 n이라고 할 때 1) 곱셈의 관점 2) 덧셈의..