본문 바로가기

전체 글

B_10816 Sol.1, unordered_map #include #include using namespace std; int main(void) { int N, M, card; unordered_map m; ios::sync_with_stdio(false); cin.tie(0); cin >> N; for (int i = 0; i > card; m[card]++; } cin >> M; for (int i = 0; i > card; cout N; for (int i = 0; i > card; arr[i] = card; } sort(arr, arr + N); cin >> M; for (int i = 0; i < M; i++) { .. 더보기
B_1934 #include using namespace std; int gcd(int a, int b) { int r = a % b; if (r == 0) return b; return gcd(b, r); } int main(void) { int T, A, B, temp, answer; cin >> T; for (int i = 0; i > A >> B; if (A >= B) temp = gcd(A, B); else temp = gcd(B, A); answer = A * B / temp; cout 더보기
B_11478 #include #include using namespace std; int main(void) { string S; set answer; cin >> S; for (int i = 0; i < S.length(); ++i) { string temp = ""; for (int j = i; j < S.length(); ++j) { temp += S[j]; answer.insert(temp); } } cout 더보기
B_1620 #include #include #include #include #include using namespace std; map dictionary; static bool comp(pair &a, pair &b) { return a.second second; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; for (int i = 1; i > temp; dictionary.insert({temp, i}); } vector dicVec(dictionary.begi.. 더보기
B_7785 set/hash/map set은 연관 컨테이너로, key-value의 구조를 가지는 자료구조이다. 연관 컨테이너는 주로, - 특정 키가 연관 컨테이너에 존재하는지 유무를 알려주는 기능 - 만일 존재한다면, 이에 대응되는 값을 알려주는 기능 이 대표적인데, C++의 경우 위 두 가지 작업을 모두 처리할 수 있는 '연관 컨테이너'를 제공한다. 전자인 존재유무는 Set/Multiset이 이를 담당하며, 후자인 대응 값 탐색은 Map/Multimap이 담당한다. set의 특징은 원소의 추가-삭제 작업의 시간 복잡도가 O(logN)으로 굉장히 빠르다는 점이다. 또한, set은 중복된 원소를 허용하지 않으며, 정렬된 상태를 유지한다는 점이 장점이다. 이러한 특성과 더불어, 자체적으로 'find' 메소드를 제공, 컨.. 더보기
Backtracking 백트래킹 어떠한 문제가 모든 가능성을 조사하지 않고는 해를 구할 수 없는 경우, 모든 가능성을 조직적이고 효율적으로 조사하는 방법 '조사하지 않아도 되는 부분은 조사 대상에서 제외, 해를 빨리 찾는다.' 이러한 백트래킹의 해는 어떠한 제한조건을 만족하는 n개의 원소로 구성된 벡터인 (x1, x2, x3, ..., xn)의 형태로 나타낼 수 있다. 이러한 이유는, 해의 표현을 어떻게 정하느냐 하는 것은 알고리즘의 설계 방향 및 시간복잡도를 결정하기 때문에 위와 같이 단순한 형태로 나타낸다. 따라서, 해를 결정하는 과정에서 아니다 싶은 것은 사전에 제거하는데, 이때 DFS의 변형을 통해 가지치기하여 결정한다. 분기한정 백트래킹과 유사하나, 해를 찾기 위해 백트래킹과 같이 어느 특정한 운행 방법뿐만 아니라 깊.. 더보기
P/NP & Approximation Algorithm 1. 해결 가능한 문제/해결 불가능한 문제 P-완비 문제들은 현실적인 시간내에 풀 수 없는 문제들 (지수시간)이다. 다항식 시간, 현실적인 시간 -> 입력의 크기 n의 다항식으로 표시되는 시간 비다항식 시간, 비현실적인 시간 -> 지수시간, 계승시간 등 2. 결정적 문제 / 최적화 문제 결정적 문제: Yes/No 문제, 존재의 여부 파악 최적화 문제: 문제의 최적값을 찾는 문제 3. NP 완전문제 결정적 문제에만 국한되는 문제이지만, 최적화 문제와 밀접환 관계를 가진다. 결정문제가 풀린다면 최적화 문제도 풀리고 결정문제가 안풀린다면 최적화 문제도 안풀린다. 4. P/NP P: 다항식 시간 내에 결정 문제 해결 가능 NP: P를 포함, 아직 P라고 해결되지 않은 문제, 해를 제공, 해당 해가 Yes임을 다.. 더보기
Computer Animation (Basic) 더보기

티스토리툴바