어제의 나보다 성장한 오늘의 나

※ 문제의 S를 N으로 두고 풀었기 때문에 헷갈리지 않게 조심해주세요. 풀이 : 단순한 그리디 문제이다. 가장 많은 숫자를 더해서 N을 완성 시켜야 하므로, 작은 수부터 차례로 1,2,3,4,.....,k 까지 쭈욱 더한다. 1~k까지 더한 값을 N에서 뺐을 때 0보다 크고 N보다 같거나 작은 수가 나온다면 정답은 k이다. 예를 들어보자. 100 = (1+2+.....+13) + 9 . 9는 1~N 사이 값이므로 정답은 13이다. 좀 더 자세히 설명 해보자면 9는 이미 1~13 안에 들어있기 때문에 이렇게 바꿔줘야 한다. 100 = (1+2+.....12) + (13+9) = (1+2+.....12) + 22 따라서 갯수(k)는 13이다. Coding #include using namespace std;..

STL container 중 하나인 트리 중 Complete Binary Tree (완전 이진 트리)를 구현해보았다. 그리고 응용 함수들을 만들어 보았다. 구현 Struct struct TreeNode{ int key; // node 속 data 저장 TreeNode* left; TreeNode* right; TreeNode(int k, TreeNode* l , TreeNode* r){ key = k; left = l; right = r; } TreeNode(int k) : key(k), left(nullptr), right(nullptr){} ~TreeNode(){} }; using tree = TreeNode*; 기본 함수들 empty : 비어있다면 true 반환 , 아니면 false 반환. bool..

간단한 Greedy 문제이다. 정렬 후, for 반복으로 arr[i] * (arr_size()-i) 를 다 더해주면 답이 나온다. #include #include #include using namespace std; int main(int args ,char** argv){ int N; cin >> N; vector pi; int temp; for(int i = 0 ; i > temp; pi.push_back(temp); } sort(pi.begin() , pi.end()); int pi_size = pi.size(); int answer = 0 ; for(int i = 0 ; i < N ; ++i){ answer += pi[i] * (pi_size-i); } cout

◎ key , value 가 pair 형태로 연결되어 있는 자료 구조. ◎ 이진 탐색 트리의 일종이다. (레드 블랙 트리) ◎ 값을 찾을 때 시간 복잡도가 O(logN)으로 빠른 편이다. ◎ 삽입 / 삭제 할 때 시간 복잡도는 O(logN)으로 오래 걸린다. ◎ key 값을 기준으로 자동 정렬 되어 있다. ◎ key값이 중복 불가능 하다. 즉 , key 값이 유일하다. ◎ 메모리가 자동으로 동적 할당 된다. STL 사용법 헤더 파일 #include 선언 map m; key , value 순으로 선언. map m; // 내림차순 key 기준으로 기본 오름차순 이지만 greater를 사용하면 내림차순으로 바뀐다. 값 삽입 4가지 방법. m.insert( {0,"zero"} ); m.insert(make_pa..

풀이 : ① 입력 된 문장을 +,- 와 숫자로 나눈다. ( substr 사용) ② 조건에 맞게 계산을 한다. 가장 작은 값이 결과로 나오도록 해야 하므로 - 가 나오기 전까지는 모든 숫자를 더 해주고, -가 한 번이라도 나오면 그 이후로는 모두 빼주면 된다. Coding #include #include #include using namespace std; int main(int args ,char** argv){ string str; cin >> str; vector ops; // str에 들어있는 + , - 순서대로 저장. vector nums; // str에 들어있는 숫자들 순서대로 저장. int first_index = 0; int last_index = 0; // 입력된 문장을 + , - 와 숫자..

에서 제공하는 Find 함수가 있고, 에서 제공하는 Find 함수가 있는데 두 가지를 모두 정리해보았다. ① 의 find 함수 헤더파일 #include 사용법 s.find( 찾을 문자열 , 시작 위치 , 찾을 문자열의 길이 ) string s = "Hello My Name is metoday."; int non; non = s.find("h"); //non == npos cout

1) s.substr(시작 위치 , 문자열의 길이) string s = "0123456789"; string subs1 = s.substr(2,5); // subs1 = "23456" string s = "0123456789"; string subs1 = s.substr(5); // subs1 = "56789" string s = "0123456789"; string subs1 = s.substr(); // subs1 = "0123456789" 시작 위치와 문자열의 길이를 입력 받아서 문자열을 자른다. 숫자 하나만 집어넣으면 시작 위치로 인식되어 시작 위치 부터 끝까지로 문자열을 자른다. 아무 것도 넣지 않으면 s 전체가 복사 됨. find 함수와 함께 사용 string s = "0123456789"; ..

알고리즘 도시를 하나 씩 옮겨가면서 첫 번째 도시~ 현재 도시 중 가장 주유 값이 적은 것을 선택한다. 현재도시~다음 도시 까지의 도로의 길이를 구한다. (첫 번째 도시 ~ 현재도시 중 가장 적은 주유값) * (현재도시~다음 도시 까지의 도로의 길이) 를 total에 더한다. 이 과정을 첫 번째 도시 부터 마지막 도시까지 적용하면 쉽게 구할 수 있다. Coding #include #include using namespace std; int main(int args ,char** argv){ int N ; long long int temp; cin >> N; vector street; vector cost_gas; for(int i = 0 ; i > temp; street..