반응형 분류 전체보기99 1158 요세푸스 문제 / #include<list> / List 사용하기 1. 리스트의 경우 Random Access 가 불가능하다. 따라서 iterator를 활용하여 출력을 해줘야 한다. - 근데 iterator의 경우 it+3과 같은 접근이 불가능하기 때문에 it++; 과 같은 형태로 이용해주어야 한다. - 맨 앞과 뒤는 출력이 가능한데 이는 list.front(), list.end() 와 같은 형식으로 접근이 가능하다. 2. 리스트의 경우 erase를 하고 나면 그 후에 사용이 불가능하다. 따라서 it = erase(it); 형태로 바꿔주어야한다. 3. 리스트의 삽입은 list.insert(it,x) 꼴이며 list.push_back(x), list.push_front(x) 와 같은 형태로 사용이 가능하다. - 삭제도 마찬가지 pop_front() , pop_back().. 2022. 1. 27. 10816 백준 숫자카드2 문제는 다음과 같이 10개의 수가 주어지고 8개 수 중 몇개가 들어있는지 나열하는 것이다. 나는 counting sort를 이용해서 풀었는데 시간이 오래 걸려서 다른 방법을 찾아보았다. 중복되는 수 때문에 이진 탐색을 이용할 수 없다 생각하여 counting sort를 활용하였는데 lower_bound, upper_bound를 이용해서 쉽게 해결할 수 있더라.. 소스 코드를 직접 구현하면 이런 느낌이다. 이 것을 내장함수로 표현하면 다음과 같다. 훨씬 더 소스코드가 간결해졌지만 실행 시간은 counting sort와 비슷한 결과를 가져다 주었다. 메모리 차이는 많이 나더라.. 2022. 1. 27. Count sort -> Input이 매우 많을 때 (1000만) 2022. 1. 23. 유클리드 호제법 (최대공약수&최소공배수 구하기) 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수(GCD)는 b와 r의 최대공약수(GCD)와 같다. 이 성질을 이용하여 다시 b를 r로 나눈 r' 를 구하고, 다시 r을 r'로 나누는 과정을 반복한다. 이 과정을 통해 r'가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. 기존 이중 반복문을 통한 최대공약수 찾기는 O(min(a,b)) -> O(n) 의 시간복잡도를 가지고 있다. 하지만 유클리드 호제법을 이용하게 되면 나눗셈의 횟수가 log n 이므로 시간 복잡도는 O(log n)이다. 재귀를 통한 유클리드 호제법 사용시 공간복잡도가 나눗셈 횟수인 O(log N) 만큼 더 증가한다. Why? 호출 스택에서 나눗셈 횟수인 O(log N)만큼 공간을 잡아먹.. 2022. 1. 23. #include<algorithm>_ reverse / #include<cstdlib> itoa / #include<string> to_string 문자열 뒤집기 #include 의 reverse() 사용법은 벡터와 비슷하다. reverse(str1.begin(), str1.end()); 정수 -> 문자 형변환 #include 의 itoa() 정수를 문자 char * 형으로 변환하는 경우에는 itoa() 사용. itoa(int, char*, 10진수/2진수); 정수 -> 문자열 형변환 #include 의 to_string() 놀랍게도 C++ 에서는 itos가 아닌 to_string을 쓴다. 흠.. itos도 하나 만들어주지.. to_string(int); 문자 -> 정수 #include 의 atoi() atoi의 매개변수로는 char * 형을 받아야 한다. string 을 넣으려면 atoi(string.c_str()); 사용 문자열 -> 정수 #i.. 2022. 1. 23. #include <vector> / #include <cctype>_to(upper/lower), is(upper/lower) 오늘은 C++ 소스코드를 보면 자주 쓰이는 벡터에 대해서 간단히 정리해 보았다. #include vector v; v.push_back(__) //입력할 때 v.inesrt(v.begin(), value) // 처음 0번째 index에 값 삽입 v.inesrt(v.begin()+n, value) // n번째 index에 삽입 v.erase(v.begin()); v.erase(v.begin()+n); // n 번째 index제거. v.pop_back() // 가장 마지막 값 삭제 v.back() // 가장 마지막 값 불러오기 v.front() // 가장 처음 값 [0] 인덱스 값 불러오기 sort(v.begin(), v.end(), greater()); #include toupper, tolower -> .. 2022. 1. 22. 백준 1427 소트인사이드 / <cstdlib>_atoi()_문자형변환 이번 문제도 실버5로 매우 낮다. 따라서 이번에도 문제풀이 위주가 아닌 #include 의 atoi() 함수에 대해 알아보려고 한다. 크게 보자면 C++에서 문자형을 숫자형으로 바꾸기 위해서 어떻게 해야하는지 다시 적으려고 한다. 백준 소스코드는 맨 밑에 있다. 급하면 맨 밑으로 #문자열을 정수로 형변환 분명 티스토리에서 마크다운 모드가 아닌 기본모드에서 작성하는데 까먹고 #을 붙이게 된다. 아무튼 제목이다. 그렇다고 한다. #include 혹은 헤더파일에 atoi()함수가 존재한다. atoi() 함수의 매개변수는 atoi(const char *)이다. 따라서 문자 하나를 정수형으로 바꾸면 오류가 난다. (char -> int) stoi() 함수의 매개변수는 stoi(const string &__str).. 2022. 1. 21. 백준 2822 점수계산 (실버 5) / <algorithm>_sort() 티스토리 너무 어렵다... 백준보다 어려운거같다.. 어쨌든 내가 오늘 리뷰할 문제는 2822번이다. 난이도도 실버 5로 별로 어렵지도 않고 시간 제약도 없다. 편안하게 풀면 되는데 sort() 에 대해 궁금한게 생겨서 이거 저거 찾아보고 느낀점과 코드 리뷰도 같이 하면 좋을 것 같아서 적어봤다. 우선 sort() 함수는 #include 헤더의 내장함수이다. sort 뜻 그대로 정렬 해준다는 뜻 이며 오름차순이 Default이다. 사용법은 sort(array, array+10) 하면 a배열에 대해 오름차순 정렬을 해준다. 정말 간단하다. 내림차순은 sort(array, array, greater()) 과 같은 형식이다. greater() 뒤의 괄호()는 필수이다!!. 또한 greater() 부분에 사용자 .. 2022. 1. 20. 이진 탐색(정렬) & #include <cmath>_pow() 이진 탐색 소스코드. 이진 탐색을 하기 위해서는 정렬 필요 why 오름차순 배열에서 반 잘라서 같으면 탐색 성공 크면 다시 오른쪽의 반만 아니면 반대로 진행 시간 복잡도 : O(logN) -> 빠름. -> sort(arr1, arr1+n); 나는 동적할당을 자주 사용하니까 다음과 같은 형식으로 처음과 끝을 지정해주었다. 백준 1009번 문제를 푸는데 시간제한이 떠서 개념만 복습하고 직접 구현해봤다. 알고리즘 수업을 들은게 벌써 2년전이니까.. 가물가물했어도 성공했다. 탐색, 연산, 정렬을 재귀로 수행하게 되면 공간복잡도가 시간복잡도인 O(log N)을 더 차지하게 된다. 재귀로 수행할 경우 스택에 시간복잡도 만큼 호출을 하게 되어 공간을 더 차지하게 된다고 한다. -나무위키 참조 (유클리드 호제법)- i.. 2022. 1. 12. 이전 1 ··· 7 8 9 10 다음 반응형
