Coding StudyRoom

문제 설명 : 숫자를 담은 벡터를 input 값 으로 받는다. 벡터에서 연속된 숫자 부분은 한번만 저장되도록 바꾼다. ex) [1,1,1,3,3,0,1,1] >> [1,3,0,1] 간단하게 짧은 line으로 푼 풀이가 있어서 작성한다. #include #include #include using namespace std; vector solution(vector arr) { arr.erase(unique(arr.begin(), arr.end()),arr.end()); vector answer = arr; return answer; } C++ vector의 erase 멤버 함수 iterator erase (const_iterator position); iterator erase (const_iterator ..

Stack (스택) : LIFO (Last In First Out) 특징 - 나중에 들어온 값이 먼저 나온다 >> 마지막에 들어온 원소가 제인 먼저 나갈 수 있도록 하는 자료 구조. #include : stack 라이브러리 전처리 필요 stack 변수명 : stack 생성 멤버함수 push(데이터) : 데이터 삽입 (top에 원소 추가) size() : 현재 스택에 저장되어 있는 데이터의 갯수를 반환 top() : 현재 스택 최상위의 데이터를 반환 (데이터를 제거하지는 않는다) pop() : 현재 스택 최상위의 데이터를 제거 (top에 있는 원소를 삭제) >> 반환값 x (void) empty() : 현재 스택이 비었으면 true, 아니면 false 반환 ※ C++ explicit 키워드 : 컴파일러에 ..

시간복잡도 : O(N + M) N : 텍스트 길이 M : 패턴(탐색 문자열)의 길이 KMP 알고리짐에서 prefix(접두사) suffix(접미사)란? : 문자열에서 맨앞과 맨 뒤에어서 같은 문자열이 나오는 경우 ex) ABCAB -> 접두사 : AB, 접미사 : AB 핵심 아이디어 : 문자열이 불일치 할 때 앞서 탐색했던 정보를 이용하여 몇 칸 정도는 건너 뛴 후 탐색하겠다! Simple 비교할 문자열의 인덱스는 계속 증가한다!다만 패턴의 인덱스가 pi 배열의 접두사 접미사가 일치하는 정보를 기반으로 비교하는 패턴의 인덱스가 변하는 것이다.! 이동했을 때 또한 다르면 당시의 pi배열 접두사 접미사의 정보를 가지고 또 건너 뛸 수 있다! 건너 뛴 후 preifx와 suffix가 일치해야한다는 전제 조건이 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

Traveling Salesman Problem(Traveling Sales-Person Problem) minimization optimization 조합 최적화 문제 택배 배달 시스템. 1,000개 boxes -> 가장 먼저 퇴근경로? h-value estimation in TSP Minimization Optimization: h = under-estimate -> TSP : under-estimation ==> 실수 X. incorrect prune X. -> 0 h = h* - alpha(smaller) #include using namespace std; const int N = 4;// 노드 수 int final_path[N + 1];// 경로 저장 ..

0/1 Knapsack Example using Branch&Bound #include #include #include using namespace std; struct Item { double weight; // 무게 int value; // 가치 }; struct Node { int level, profit, bound; double weight; }; bool cmp(Item a, Item b) { double r1 = a.value / a.weight; double r2 = b.value / b.weight; return r1 > r2; } // bounding function int bound(Node u, int n, int W, Item arr[]) { if (u.weight >= W) re..

Backtracking = DFS visit + bound function --> DFS를 BFS visit으로 전환하면? --> Branch and Bound. Backtracking = DFS + bound function Branch&Bound = BFS + bound function --> 차이는 DFS vs BFS. Q1. DFS vs BFS 장단점을 논하시오. --> in practice, Branch&Bound >> Backtracking. --> BFS: 신뢰성이 더 좋음 Q2. f = g + h tree traverse(child visit)순서에 따라, g value, h value는 update 차이 발생 ** 미..