본문 바로가기

알고리즘39

[C++] 완전 탐색(1) - 부분 집합 구하기 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. 완전 탐색 거의 모든 알고리즘 문제를 해결하는 데 사용할 수 있는 일반적인 방법 완전 탐색은 정답에 대해 충분한 시간이 있다면 좋은 기술이다. 왜냐하면 완전 탐색은 검색을 구현하기 쉽고 항상 올바른 정답을 제공하기 때문이다. 하지만 완전 탐색이 너무 느리다면 그리디 알고리즘, 동적프로그래밍과 같은 다른 기술이 필요하다. 1. 부분 집합 구하기 먼저, n개 원소 집합의 모든 하위 집합을 생성하는 문제를 살펴보자. 예를 들어 {0, 1, 2}의 하위 집합은 "공집합, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}" 이다. 하위 집합을 생성하는 일반적인 방법에.. 2021. 6. 24.
[BOJ/백준] 2231번 - 분해합 단계별로 풀어보기 > 브루트포스 > [1단계] 2231번 문제 링크 : https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 요약 구해야 할 것 : N의 가장 작은 생성자 예시) 256(N;입력) = 245(원하는 정답;출력) + 2 + 4 + 5(각 자리수의 합) 생성자가 여러 개인 경우 가장 작은 것을 출력 입력 복사 예제 입력 1 >> 출력 : 198 216 CODE #include using namespace.. 2021. 6. 23.
[C++] 데이터 구조(3) - Map structures 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. Map structures 맵은 키-값 쌍으로 구성된 배열을 말한다. C++ 표준 라이브러리는 2가지 맵 구현체를 포함한다. map 구조는 밸런스 이진 트리 기반으로, 원소 접근 시간은 O(logn)이다. unorderd_map 구조는 해싱을 사용하며, 원소 접근 시간은 평균 O(1)이다. 1. map 함수 선언 (키 : string, 값 : integers) map m; m["monkety"] = 4; m["banana"] = 3; m["harpsichord"] = 9; cout 2021. 6. 21.
[BOJ/백준] 2798번 - 블랙잭 단계별로 풀어보기 > 브루트포스 > [1단계] 2798번 문제 링크 : https://www.acmicpc.net/problem/2798 문제 요약 1. 3장을 고른다. 2. 3장의 합을 구한다. 3. 주어진 M을 넘지 않는 최대값을 구한다. 입력 복사 예제 입력 1 >> 출력 : 21 5 21 5 6 7 8 9 예제 입력 2 >> 출력 : 497 10 500 93 181 245 214 315 36 185 138 216 295 CODE #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector v; int num[n]; int sum; for(int i = 0; i > n.. 2021. 6. 21.
[C++] 데이터 구조(2) - Set structures 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. Set 구조 set은 삽입하는 특정 순서에 따라 고유한 원소를 저장하는 데이터 구조이다. ▶ "중복이 없다" set의 기본 작업은 원소 삽입, 검색, 제거이다. C++ 표준 라이브러리는 2가지 set 구현을 포함한다. set 구조는 밸런스 이진 트리 기반으로, 이는 O(logn) 연산 시간을 가진다. unordered_set 구조는 해싱을 사용하며, 이는 평균 O(1) 연산 시간을 가진다. 1. set 함수 선언 set s; 2. insert함수 : set으로 원소 삽입 set s; s.insert(3); s.insert(2); s.insert(5); 3. count함수 : set 내부.. 2021. 6. 19.
728x90
반응형

티스토리툴바