반응형 [PCCP] Lv2: 전력망을 둘로 나누기(86971) 해설 문제- 문제 링크: 전력망을 둘로 나누기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C#)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (Java)solution 1)- N은 송전탑의 개수- 깊이우선탐색을 이용하여 한 번에 탑을 구하므로 시간 복잡도는 O(N)- N이 100이하이므로 O(N^2)으로 풀이 가능더보기import ja.. 2024. 12. 25. [PCCP] Lv3: 경주로 건설(67259) 해설 문제- 문제 링크: 경주로 건설 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C#)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (Java)solution 1)- N: 보드의 한 변의 길이- 너비 우서 탐색은 N * N개의 노드를 탐색하고 네 방향을 고려하므로 시간 복잡도는 O(N^2)더보기import java.util.ArrayD.. 2024. 12. 25. [PCCP] Lv2: 배달(12978) 해설 문제- 문제 링크: 배달 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C#)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (Java)solution 1)- E: road의 길이- 그래프를 추가할 때 시간 복잡도는 O(E)- 다익스트라 알고리즘은 우선순위 큐를 활용했으므로 O((N + E)logN)- 마지막 결과 리스트를 순회하며 K.. 2024. 12. 25. [PCCP] Lv3: 양과 늑대(92343) 해설 문제- 문제 링크: 양과 늑대 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: info의 길이- edges 벡터를 순회하면서 트리를 생성하는 동작의 시간 복잡도는 O(N)- 이후 너비우선탐색을 할 때의 시간 복잡도는 O(N^2)- 최종 시간 복잡도: O(N^2)더보기#include #include using namespace std;vector> tree;vector visited, comp;int n, answer = 0;// 깊이우선탐색을 수색하는 함수void dfs(vector cur) { int sheep = 0, wolf = 0; // 현재 방문한 경로를 기준으로 양과 늑대의 개수를 셈 for (i.. 2024. 12. 25. [PCCP] Lv3: 네트워크(43162) 해설 문제- 문제 링크: 네트워크 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 노드(컴퓨터)의 개수- E: 간선의 개수- 인접행렬로 구현한 깊이우선탐색은 노드의 연결 여부에 상관없이 모두 체크하므로 시간 복잡도는 O(N^2)- computers의 정보가 인접행렬이므로 O(N^2)더보기#include #include using namespace std;vector visited;// 깊이우선탐색을 수행하는 함수void dfs(const vector>& network, int node) { visi.. 2024. 12. 25. [PCCP] Lv2: 게임 맵 최단거리(1844) 해설 문제- 문제 링크: 게임 맵 최단거리 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N*N: 배열의 크기- 너비우선탐색은 모든 노드를 한 번씩 확인하므로 최종 시간 복잡도는 O(N*M)더보기#include #include using namespace std;const int MAX_SIZE = 100;const int dx[4] = {-1, 0, 1, 0};const int dy[4] = {0, 1, 0, -1};int check[MAX_SIZE][MAX_SIZE];// 좌표 정보 및 좌표 연산을 하기.. 2024. 12. 25. [C++로 배우는 알고리즘과 자료구조] Day 25: 다익스트라 알고리즘 (Dijkstra's Algorithm) 다익스트라 알고리즘 (Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 단일 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 그래프에서 작동합니다.다익스트라 알고리즘의 시간 복잡도:일반적인 구현: (O(V^2))우선순위 큐를 사용한 구현 (힙): (O((V + E) \log V))다익스트라 알고리즘 구현그래프 구현 (인접 리스트 사용)#include #include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int u, int v, int weight); // 간선 추가 vo.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬) 그래프 표현 방법그래프는 다양한 방식으로 표현할 수 있습니다. 주요한 두 가지 방법은 인접 리스트와 인접 행렬입니다. 각 표현 방법은 공간 복잡도와 특정 연산에 대한 시간 복잡도에서 장단점이 있습니다.인접 리스트 (Adjacency List)인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식으로 그래프를 표현합니다. 이 방법은 연결 리스트나 벡터를 사용하여 구현할 수 있습니다.인접 리스트의 특징:공간 복잡도: (O(V + E)), 여기서 (V)는 노드의 수, (E)는 간선의 수입니다.장점: 희소 그래프(Sparse Graph)에 적합하며, 메모리 사용이 효율적입니다.단점: 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.인접 리스트 구현AdjacencyLis.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념 그래프 (Graph)그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.그래프의 구성 요소:노드 (Vertex): 그래프의 개별 요소입니다.간선 (Edge): 노드 간의 연결을 나타냅니다.그래프의 종류:방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.그래프의 표현 방법그래프는 다음과 같은 방법으로.. 2024. 8. 1. [알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료1. 서로소 집합 자료구조Disjoint Sets- 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find)- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조- 두 종류의 연산을 지원- - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산- - Find: 특정한 원소가 속한 집합이 어떤 집합인지- 연결성을 통해 집합의 형태를 확인 (동작 과정)1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - A'를 B'.. 2024. 7. 20. 이전 1 2 다음 반응형
