반응형 [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. [PCCP] Lv2: 미로 탈출(159993) 해설 문제- 문제 링크: 미로 탈출 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 지도 한 변의 길이- isWithinRange()의 시간복잡도: O(1)- findStartPoint()의 시간복잡도: O(N^2)- 이동과정은 최악의 경우 지도의 크기가 N*N, 네 방향으로 이동하므로 시간 복잡도는 O(4*(N^2))- 최종 시간 복잡도: O(N^2)더보기#include #include #include using namespace std;// 현재 좌표, 해당 좌표까지 이동 횟수struct Point .. 2024. 12. 25. [PCCP] Lv3: 섬 연결하기(42861) 해설 문제- 문제 링크: 섬 연결하기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 노드 개수- E: costs의 길이. 간선 개수- 간선을 비용 기준으로 정렬하기 위한 시간 복잡도: O(ElogE)- costs 순회하면서 find(), union() 호출하기 위한 시간 복잡도: O(E)- 최종 시간복잡도: O(ElogE)더보기#include #include #include using namespace std;// 상호배타적 집합 정의class DisjointSet {private: vector .. 2024. 12. 24. [PCCP] Lv1: 폰켓몬(1845) 해설 문제- 문제 링크: 폰켓몬 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- nums를 집합으로 변환: O(N)더보기#include #include using namespace std;int solution(vector nums){ int answer = 0; // s는 nums의 중복값을 제거한 집합 unordered_set s(nums.begin(), nums.end()); // nums/2의 개수와 s의 개수 중 작은 값을 반환 answer = min(nums.size()/2, s.s.. 2024. 12. 24. [PCCP] Lv3: 길 찾기 게임(42892) 해설 문제- 문제 링크: 길 찾기 게임 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: nodeinfo의 길이. 노드의 개수- 이진 트리 구축 과정에서 nodeinfo를 정렬하는 시간 복잡도: O(NlogN)- 노드를 추가하는 과정에서 최악의 경우는 노드가 한 줄로 연결된 경우이므로 시간 복잡도는 O(N^2)- 전위 순회와 후위 순회는 노드를 한 번씩 탐색하므로 시간 복잡도는 O(NlogN)- 최악의 경우 시간 복잡도는 O(N^2)더보기#include #include #include using names.. 2024. 12. 24. [PCCP] Lv3: 다단계 칫솔 판매(77486) 해설 문제- 문제 링크: 다단계 칫솔 판매 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: enroll의 길이- M: seller의 길이- seller별로 enroll을 탐색하는 시간복잡도: O(N*M)더보기#include #include #include using namespace std;vector solution(vector enroll, vector referral, vector seller, vector amount) { vector answer; unordered_map pa.. 2024. 12. 24. 이전 1 ··· 5 6 7 8 9 10 11 ··· 61 다음 반응형
