Way to be gorgeous developer

https://www.acmicpc.net/problem/2240 W 최대 30번 2^30백트래킹 -> 시간초과 #include using namespace std;/* 자두를 심고 먹는다 자두까 떨어지면 받아먹는다 자두가 바닥에 떨어지기 전 허공에 있을 떄 잡아야한다 매 초, 두개 나무중 하나의 나무에서 자두가 떨어진다 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 자두는 T초동안 떨어진다 자두는 최대 W번 움직인다 1≤T≤1,000 1≤W≤30 자두가 받을 수 있는 자두의 최대 개수를 출력한다 자두는 1번 자두나무 아래에 위치해 있다고 한..

Breadth First Search다음 깊이의 정점으로 이동하기 전, 현재 깊이의 모든 정점을 탐색한다.방문한 정점은 다시 방문하지 않는다.같은 가중치를 가진 그래프에서 최단거리 알고리즘으로 사용된다.자료구조 Queue를 사용한다.최단거리 알고리즘으로 사용하기 때문에, visited 배열은 bool값이 아닌 최단경로를 기입한다.BFS(G, u){ u.visited = 1 q.push(u); while(q.size()) u = q.front() q.pop() for each v ∈ G.Adj[u] if v.visited == false v.visited = u.visited + 1 ..

Depth First Search그래프 탐색 알고리즘인접한 노드들을 재귀적으로 방문한다.방문한 노드는 다시 방문하지 않는다.각 분기마다 가능한 가장 멀리 있는 노드까지 방문한다.DFS(u, adj){ u.visited = true for each v ∈ adj[u] if v.visited == false DFS(v, adj)} 1차원 DFS#include using namespace std;const int n = 6;vector adj[n];int visited[n];void DFS(int u){ visited[u] = 1; cout  2차원 맵 DFS#include using namespace std;/* N * M맵, 맵의 배열이 주어진다.*/int a[104][104];boo..

부모 노드와 자식 노드로 이루어진 계층 구조무방향 그래프의 일종, 사이클이 없는 자료구조이다.노드간 경로는 반드시 존재하며, 반드시 하나이다.  루트노드 - 부모노드내부노드 - 부모노드와 리프노드 사이의 노드리프노드 - 자식이 없는 마지막 계층의 노드 Vertex - 1 = EdgeVertex 갯수는 6, Edge의 갯수는 5이다.Vetex 갯수 - 1 = Edge 갯수이다. 트리 내에 트리의 구조를 띄는 구조를 서브트리라고 한다.루트노드부터 리프노드까지의 가장 긴 거리는 높이이다.서브트리에서 루트노드부터 리프노드까지의 최단거리는 깊이, 레벨이다.이진 트리자식 노드의 수가 2개 이하인 트리. 균형 이진트리가 알고리즘에서 가장 중요하다.균형이진트리는 모든 노드에서 봤을 때, 왼쪽 하위 트리와 오른쪽 하위 ..

그래프는 정점과 간선으로 이루어진 집합들이다. 정점(Vertex) = 노드객체, 점, 위치, 사람 등 간선(Edge)정점을 잇는 선.단방향 간선과 양방향 간선(무방향 간선)이 있다.관계, 경로 등U: 보통 시작하는 정점을 지칭한다. From의 의미V: 도착하는 정점을 지칭한다. To의 의미. u - >v 단방향 간선(직선)이 3개이고, v -> u 단방향 간선(곡선)이 2개일 때 U의 관점에서OutDegree는 3, InDegree는 2 이다.가중치정점과 정점 사이의 드는 비용.시간, 칸, 비용 등인접행렬, 인접리스트컴퓨터에게 그래프를 알려주는 방법. 시간복잡도 간선 1개 찾기간선 모두 찾기  인접행렬O(1)O(V^2)  인접리스트O(V)O(V+E)   연결된 정점이 별로 없을 때는 -> 간선이 적을 때..

endl 대신 '\n'을 사용해라.endl; = '\n'  flush, 버퍼플리시는 임시 저장 영역에서 영구 메모리로 데이터를 전송한다.

요소들의 누적된 합을 의미한다.어떠한 배열을 기반으로 앞에서 부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다.누적합은 시간복잡도를 줄여주기 때문에 용이하다. #include using namespace std;/* 지정된 배열의 요소가 변하지 않는 정적배열에 대해서만 누적합을 사용할 수 있다. 사용의 편리함을 위해 1번째 순서부터 사용한다. 누적합을 만들 원본 배열의 0번째 요소는 0으로, 누적합 배열의 0번째 요소도 0으로 초기화한다. 아래 요소들을 prefix sum으로 진행하면 a[11] = [0, 1 2 3 4 5 6 7 8 9 10] p[0] = 0 p[1] = 1 = p[0] + a[1] p[2] = 1 + ..

map 활용#include using namespace std;vector RemoveDuplicate(vector& vec){ map dMap; for(int i : vec) { // if(dMap[i]) // continue; if(dMap.find(i) != dMap.end()) continue; dMap[i] = i; } vector result; for(auto iter : dMap) result.push_back(iter.second); return result;}int main(){ vector v = {1,1,2,2,2,3,3,3,3,3,3,4,5,5,5}; ..

c++에는 split 함수가 없다.#include using namespace std;vector split(const string& input, string delimiter){ vector result; auto start = 0; auto end = input.find(delimiter); // index of delimiter while(end != string::npos) { result.push_back(input.substr(start, end - start)); start = end + delimiter.size(); end = input.find(delimiter, start); } result.push_back(..

서로 다른 n개의 원소에서 r개를 중복 없이, 순서를 고려하지 않고 선택하는 것. 어떤 순서로 원소를 선택했는지는 중요하지 않기에 순열과는 다른 개념이다 #include using namespace std;/* 공식 nCr -> n개중에 r개를 뽑는 경우의 수 n! / (n-r)! * r!*/int n = 5, r = 3, a[5] = {1, 2, 3, 4, 5};void print(vector& b){ for(int i : b) cout & v){ if(v.size() == r) { print(v); return; } for(int i = start + 1; i vec; combination(-1, vec); ..