Storage Gonie

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/390 # C++ #include #include #include #include #include using namespace std; vector vec[100001]; // 인접리스트 int check[100001]; // bfs를 위한 check 배열 int dist[100001]; // 루트로부터의 거리를 저장할 배열 void bfs(int x); int main() { int n; cin >> n; // 입력받아서 인접리스트 만들기 for (int i = 0; i > s; //끝정점 및 가중치를 입력받아 인접리스트에 추가. while(true){ int p..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터7-3-트리-문제풀이 # C++(DFS, 인접리스트를 이용한 풀이) #include #include using namespace std; int e; // 간선의 개수 vector vec[100001]; // 인접리스트 bool check[100001]; // check배열 int parent[100001]; void dfs(int x); int main() { //정점의 개수 cin >> e; //입력을 받아 인접리스트 만들기 for (int i = 0; i > a >> b; // 주어진 간선이 양방향이라고 하였으므로 vec[a].push_back(b); vec..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터7-3-트리-문제풀이 # C++(2차원 배열로 왼쪽자식과 오른쪽 자식을 저장하는 방식) # include using namespace std; int arr[26][2]; void preOrder(int x){ if(x == -1) return; cout > parent >> leftChild >> rightChild; // 부모노드 parent = parent - 'A'; // 왼쪽 자식노드의 값 삽입 if (leftChild == '.') arr[parent][0] = -1; else arr[parent][0] = leftChild - 'A'; // 오른쪽 자식노드의 값 삽입 if (rightChild == ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터6-3-그래프-그래프의-탐색 # C++(인접 행렬 사용) #include #include #include // memset using namespace std; int v, e, startNum; int arr[1001][1001]; // 인접행렬 bool check[1001]; // check배열 void dfs(int x); void bfs(int x); int main() { /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/ cin >> v >> e >> startNum; /*입력을 받아 인접행렬 만들기*/ while(e--){ int x, y; cin >> x >> y; arr[x][y] ..

그래프를 탐색하는 방법 - 그래프를 탐색하는 방법에는 DFS와 BFS가 있으며, 두 방식 모두 목적은 모든 정점을 1번씩 방문하기 위한 것이다. - 따라서, 두 방법 모두 각각의 노드에 방문 했는지 안했는지를 체크하는 check 배열이 필요하다. - 순서를 출력해 낼 때, 현재 정점의 위치만을 출력하며, 이것은 두 방식 모두 동일하다. # DFS(깊이 우선 탐색) 구현 : 스택 or 재귀호출 스택을 직접 컨트롤하는 경우, 재귀호출을 사용하지 않고 구현할 수 있고, 재귀호출을 사용하는 경우 중첩된 호출에 의해 스택을 간접적으로 사용하게 됨. 의미 : '최대한 깊숙히 많이 가는 방법'으로 모든 정점을 1번씩 방문하는 것 탐색방법 : 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정..

그래프의 표현 정점 : {1, 2, 3, 4, 5, 6} 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} - '정점'이 V개 일 때 보통 정점에 1~V 혹은 0~V-1로 번호를 매기기 때문에 개수만 저장해둬도 된다. - '간선'은 무엇과 무엇을 연결하는지에 대한 중요한 관계를 나타내므로 간선을 저장하는 것이 그래프를 저장하는 것이 된다. - 그래서 보통 문제에서 그래프에 관해 입력데이터를 줄 때는 정점의 개수, 간선의 개수, 간선의 관계를 아래와 같이 준다. (양방향 그래프인지 단방향 그래프인지는 문제의 본문을 읽어야지만 알 수 있다) 예시 1) 가중치가 없는 경우 6 8 // n : 정점의 개수, m : 간선의 개수 1 2 /..

그래프의 개념 # 그래프(Graph) - 자료구조의 일종 - 그래프는 정점집합과 간선집합으로 만들어진다. G = (V, E) - 정점(Node, Vertex)은 말그대로 점을 의미하고, 간선(Edge)은 정점간의 관계를 나타낸다. - 예시1) 지하철노선이나 도로를 그래프로 나타낼 수 있음. - 예시2) 페이스북같은 경우는 사람이 정점이고 두 사람이 친구사이면 둘을 간선으로 연결해줄 수 있음 그래프에서 사용되는 용어 # 경로(Path) - 출발지와 도착지가 있고 그 사이를 연결하는 정점과 간선이 있으면 이것을 경로라고 한다. - 예시) A->C->D->E->B A->B A->C->B # 사이클(Cycle) - 경로 중에서 시작점과 도착점이 같은 경우를 사이클이라고 한다. - 예시) 'A'->C->B->'A..

용도 : sort()가 전체를 다 정렬시킨다면 nth_element()는 부분적으로 정렬을 시키는 함수이다. 1. 헤더파일 #include 2. 함수형태 - 시작과 끝 Iterator를 맨 왼쪽과 왼 오른쪽에 넣어주고, 가운데에 index로 어디 자리가 확정될 때까지 정렬을 진행할지 넣어줌. void nth_element( RandomIt first, RandomIt nth, RandomIt last ); 3. 사용방법 #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; // index : 0번째 자리가 확정날 때 까지만 ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++ #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n); for (int i = 0; i > v[i].first; v[i].second = i; } sort(v.begin(), v.end()); // NlogN의 시간복잡도 int ans = 0; for (int i = 0; i < n; i++){ if (ans < (v[i..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++ #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector v(n); for (int i = 0; i > v[i]; nth_element(v.begin(), v.begin() + (k-1), v.end()); cout