본문 바로가기

Algorithm

 (130)
<map> STL 정리 C++에는 여러 종류의 맵이 있으며, 그 중 map(#include)과 unordered_map(#include )이 주로 쓰인다. map과 unordered_map은 사용방법이 완벽히 동일하다. 하지만 map은 균형트리인 red black tree로 구현되어 있고, unordered_map은 해시 테이블로 구현되어 있다. 데이터가 작다면 unorderd_map이, 크다면 map이 유리하다. unordered_map m; //key가 string이고, value가 int인 unordered_map 선언 map["hi"]=5; // 새로 insert, 기존값 있으면 덮어쓴다. map["hi"]++; //기존값 있으면 1증가, 없으면 새로운 value는 1로 한다. ex) for (string name : ..
<string> STL 정리 - vector와 매우 유사하다. - C언어의 char*, char[] 문자열과 달리, 문자열끝에 '\0' 없다. - +로 string끼리 합칠 수 있다. - string의 원소 하나하나는 char이다. str[i] : str의 i번째 원소를 참조 str.push_back(x) : str의 끝에 x를 추가 str.insert(p,x) : str의 p번째 위치에 x를 삽입 str.pop_back() : 마지막 원소를 삭제//반환값 없다!! str.erase(p) : str의 p(주소)위치 원소를 삭제 str.erase(b,e) : str의 [b,e)구간 원소를 삭제 str.front() : 문자열의 첫번째 원소 반환 str.back() : 문자열의 마지막 원소 반환 str.begin() : 문자열의 첫번째..
<vector> STL 정리 - 상단에 #include 로 헤더를 추가해서 사용한다. vector v : 빈 컨테이너인 v 생성 vector v(n) : 0으로 초기화된 n개의 원소를 갖는 v생성 vector v(n,x) : x로 초기화된 n개의 원소를 갖는 v생성 vector v(6, vector(5, 0)) : 6행 5열, 모든 원소 0인 v생성 v[i] : v의 i번째 원소를 참조 v.push_back(x) : v의 끝에 x를 추가 v.insert(p,x) : v의 p번째 위치에 x를 삽입 v.pop_back() : 마지막 원소를 삭제//반환값 없다!! v.erase(p) : v의 p(주소)위치 원소를 삭제 v.erase(b,e) : v의 [b,e)구간 원소를 삭제 v.front() : 벡터의 첫번째 원소 반환 v.back()..
[C++] 백준 1373번 : 2진수 8진수 (B2) #문제 www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net #풀이 & 학습한 내용 먼저 2진수인 수의 총 길이가 3의배수가 되지 않을때, 총 길이가 3의 배수가 되도록 앞에 0을 추가해준다. 그리고 3개씩 잘라서 2진수의 값을 10진수로 변환하여 순서대로 출력하면, 8진수로 변환된 결과가 나온다. 이때, char로 표현된 0~9를 int로 다루고 싶으면 '0'을 빼주면 된다는 점을 기억하자. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #include #include using namespace std; in..
[C++] 백준 17087번 : 숨바꼭질 6 (S1) #문제 www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net #풀이 & 학습한 내용 동생들의 각각의 위치에서 수빈이의 위치를 뺀 값들의 최대공약수(GCD)를 구하는 문제이다. 유클리드 호제법을 이용해 GCD를 구하고, GCD(a,b,c)=GCD(GCD(a,b),c)임을 통해 순차적으로 계산한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..
[C++] 백준 9613번 : GCD 합 (S3) #문제 www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 b인 경우로 인자를 전달해줘야 한다고 생각했는데 상관없었다. 만약 a> T; while (T--) { ans = 0; cin >> N; for (int i = 1; i > arr[i]; } for (int i = 1; i
[C++] 백준 2004번 : 조합 0의 개수 (S2) #문제 www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/119에서는 2의 개수보다 5의 개수가 항상 적어서 5의 개수만 세어줬지만, 조합의 경우에는 2의 개수가 5의 개수보다 많을 수 있으므로 모두 세어주고 둘 중 최솟값을 답으로 출력해야 한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using name..
[C++] 백준 1676번 : 팩토리얼 0의 개수 (S3) #문제 www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net #풀이 & 학습한 내용 뒤에 0이 붙는 건 2와 5의 곱에 의해 나타난다. 그리고 2의 개수보다 5의 개수가 항상 적기 때문에 5의 개수만 세어주면 된다. 이때 처음에 간과한 것이 5로 나누어 떨어질 때 답에 1을 증가시켜준 것이다. 만약 25일 경우에는 5가 2개 들어있으므로 답에 2를 더해줘야 한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include using namespace std; int main(..

티스토리툴바