C++ Google style guide Coding Rule * header orderdir2/foo2.h.C system files.C++ system files.Other libraries' .h files.Your project's .h files.* inline function 권장 : but 10 줄 이내만! * namespace : 가능하면 namespace 사용 * 소스 내부에만 사용하는 변수 : class 에 선언하지 말고 가능하면 소스내에 unnamed namespace나 static 변수로 선언 * 로컬변수는 사용하는 곳 바로 위에 선언해라. 그래야 읽기 쉬움. * 루프의 변수는 루프내에 선언하고, object일 경우는 밖에 할 것. obj의 경우 loop를 나올 때마다 constructor/destructor가 계속 불림 .. 더보기 Tree, Hash, Linked list 1234567891011121314151617181920212223242526272829303132struct LIST{ //struct HASH{ int in, int out, HASH *prev; }h[max_hash]; int v; int ans; LIST *prev; LIST(){}; LIST(int _v, LIST* prev):v(_v), prev(_prev), ans(-1){};}a[1000]; //부모 노드LIST* branch[30]; // LIST* last[max]; //struct NODES{ int parent; .. LIST* last}nodes[max_node]; //HASH* hash_table[hash_size]; int heap_idx; // int hash_idx = 0;.. 더보기 간단한 String Hash 구현 다른 곳에 있는 코드를 가져옴~!hashtable에 값을 넣을 때, hash value가 충돌난 경우, 현재 hash값에 있는 구조체를 node의 다음으로 연결한 후,hashtable에 node 넣는 것을 잊지 말자. // 현재 hash값에 있는 구조체는 다음(뒤)으로 연결!!! node->next = hashtable[hashval]; // hashtable에 값 입력 hashtable[hashval] = node; 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858.. 더보기 모스 부호 사전 문제링크: 모스 부호 사전 동적계획법 문제를 풀 때 유형이 있다.K번째 답을 찾는 것이라면, 1. 완전정복으로 푼다.2. skip할 수 있는 지 줄여본다. (이항계수 등으로)3. 문제 자체를 한번에 풀 수 없는 지 생각해본다. 위와 같은 순서로 해본다. K번째 답을 구할 때에는 N개에서 M개를 뽑는 가짓수를 이용해서 할 수 있는지 생각한다.nCm = n-1Cm + n-1Cm-1 임을 이용한다!!! n: 1, m:0으로 생각. 123456789101112131415161718#include #include using namespace std;int N = 2, M = 3;void solve(int n, int m, string s) { if (n == 0 && m == 0) { cout 더보기 여행 짐 싸기 문제링크: 여행 짐 싸기 유명한 문제인데 풀 때마다 새롭다. 이런 류의 문제들은 패턴이 있으니 기억하자. 배낭에 넣었을 때와 안넣을때의 값 중에 max를 취한다. 일단 최대 절박도를 구하는 함수를 구하고, 그 함수를 이용하여 선택한 item들을 재구성한다. - recursive무게가 capacity만큼 남았을 때, 해당 item부터 마지막 item들까지 넣었을 때 얻을 수 있는 최대절박도를 구하는 함수를 만든다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include #define.. 더보기 LIS 문제링크: Longest Increasing Sequence 증가하는 부분 수열의 갯수를 구하는 문제이다. 동적계획법으로 풀 수 있으며, 아래보다 더 최적화된 O(NlogN) 방법이 가능하지만, 그 방법은 해당 수열을 저장하지 않는 방법이므로 일단 동적계획법을 이용해서 구현해 보았다. 현재 숫자보다 큰 숫자를 만나면 1을 더해주고, 해당숫자를 재귀적으로 호출해서 해결한다. 12345678910111213141516171819202122232425262728293031323334353637#include using namespace std;#define max(a,b) ((a)>(b) ? (a):(b))int C, N;const int MAXNUM=100001;const int MAXN = 501;int .. 더보기 Gallery: 감시 카메라 설치 문제링크: 감시 카메라 설치 갤러리에 갔다 돌아오려면 다시 지나가야 하므로, 싸이클이 없는 그래프가 된다. 처음에는 제일 많은 자식노드를 가진 노드에 카메라를 설치하도록 생각해서 구현했는데그렇게 되면 최적화가 안되는 경우가 있었다. =ㅁ=;;역시.. 손으로 검증을 다 해보고 구현해야.. 리프노드가 있는 경우 그 부모에 무조건 카메라를 설치한 후, 나머지 노드에 설치하면 된다.리프노드 전 노드에 카메라를 설치하지 않으면 리프노드에 어차피 카메라를 설치해야 하기 때문에리프노드의 부모노드는 무조건 설치해야 한다. dfs로 트리를 방문하면서 1. 자식들 중에 커버되지 않는 자식을 가지고 있으면, 현재 방에 카메라를 설치한다. 2. 자식들 중에 카메라가 설치되어 있는 방이 있으면, 현재 방에는 카메라를 설치할 필.. 더보기 트리 순회 순서 변경 문제링크: 트리 순회 순서 변경 PreOrder, InOrder Tree 정보로 Post Tree를 출력하는 문제이다. 간단한 예제를 통해 손으로 풀어본 뒤 짜면 간단하다. 키는 P(부모)는 언제나 1개라는 점을 이용하면 된다. Pre: PLRIn: LPRPost: LRP Pre: 27 16 9 12 54 36 72 -> 맨 앞에 노드가 부모노드. In: 9 12 16 27 36 54 72 -> InOrder에서 부모노드를 찾으면, 왼쪽은 left subtree (0~P-1), 오른쪽은 right subtree(P+1~N-1).Inorder tree에서 부모노드 위치가 결국 왼쪽 tree의 크기이다. (LSIZE = P) 따라서 Pre: 27 16 9 12 54 36 72 하당 크기를 이용하여Preord.. 더보기 조세푸스 문제 문제링크: 조세푸스 문제 원형으로 원소를 삭제하는 문제이다. 벡터나 c++라이브러리에서 지원하는 벡터나 리스트를 이용하면 간단히 되지만 다른 라이브러리를 사용하지 않으려고 링크드리스트를 만들어 사용해 보았다. - 원형 리스트를 이용한 구현123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include using namespace std;int C, N, K; typedef struct list { int elem; list *prev; list *next;} List; List *list; L.. 더보기 링크드 리스트 - 구조체1234struct ListNode { int element; ListNode *prev, *next;};cs - 삭제1234void deleteNode(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev;}Colored by Color Scriptercs - 자기 자신을 다시 리스트에 삽입1234void recoverNode(ListNode* node) { node->prev->next = node; node->next->prev = node;}Colored by Color Scriptercs 더보기 이전 1 2 다음