Archive 101 Archive 101

#include #include #include #include #include using namespace std; int min_value; int min_index; int solution(vector d, int budget) { int answer = 0; int cur_value = 0; while (d.size()>0) // is_reamin test : { min_value = *min_element(d.begin(), d.end()); min_index = min_element(d.begin(), d.end())-d.begin(); if (cur_value + min_value > budget) { break; } else { cur_value += min_value; answer++; ..

백트래킹 알고리즘 : 재귀 + State Space Tree Back tracking algorithms : Possible solution 을 찾기 위해 반복하는 Brute force 알고리즘 space tree 는 현재 모든 상태를 기록하는 것. n - queen 문제 (BOJ 9663) 예로 들면 Queen의 위치 state를 기록한 것. 이 때 2차원 배열 Q[i,j] = true(1) , false(0) 으로 기록할 이유는 없음. 2차원 map 에서 어떤 object의 유무에 대한 정보기록은 Q[i]= j 로 1차원 배열로 기록할 수 있음. 1) 해당 Space tree에 (k- th 상태에 대한 기록을 하고) 2) function(k+1) 로 Recursion funciton 호출 ( base..

Deque 란 ? : Double Ended Queue는 일반적으로 한쪽에서 Insert 되면 반대쪽에서 Deletion 되는 Queue 구조와는 달리 Deque 구조는 양쪽에서 삽입 / 삭제가 가능하다. 양쪽 끝의 삽입 / 삭제는 time complexity 로 O(1) 시간에 수행 가능하다.

Single Linked list 를 값을 담는 data와 다음 Node를 가르키는 pointer 변수인 next를 가지는 Class를 Node로 생각하자. class Node { public : int data; Node* next; }; Linked list에 head ,second , third라는 Node를 가지고 순회하는 예제. int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; head = new Node(); second = new Node(); third = new Node(); (*head).data = 1; (*head).next = second; head->data = 1; head->next = secon..

일반적으로 dot operator의 경우 , Class ,Struct의 member를 참조하기 위해서 많이 사용하고 익숙하다. Arrow operator에 대해 알아보자. class foo { public : int member_a = 5; int member_b = 3; void method() { cout

C / C++ 에서 Pointer 변수의 크기에 대해 알아보자. #include int main() { std::cout

int main() { int name; name = 5; double name_example; // Error 발생 name_example = 3.0; } 우선 변수와 같은 name 이라는 것은 namespace 내에서 오직 하나만 있어야 한다. 즉 코드 내에서 변수 a라는 게 존재하면, a가 또 존재할 수가 없는 유일한 entity라는 것이다. 다른 namespace에서는 동일한 이름을 가질 수 있다. 변수이름이 global 한 scope에서 제한된다면, 변수 이름이 서로 충돌날 것이다. #include int main(void) { std::cout

해당 문제에서 고민했던 부분 : 문자 숫자 Case 변환 어떻게 하지? * a-z 가 ascii code 숫자가 연속적이므로, 배열을 저런식으로 구성하면 index에 효과적으로 접근할 수 있음. #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); string c; cin >> c; int freq[26] = { 0 }; // 26: 알파벳 개수 char s; // 해당 배열 문제 : O(N) 복잡도 for (char i = 0; i < c.length(); i++) { s = c[i]; // ascii code 의 값이 a-z까지 연속적인 것을 이용하여 // ascii code : a = 97 // asci..