반응형 [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. [PCCP] Lv2: 예상 대진표(12985) 해설 문제- 문제 링크: 예상 대진표 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 참가한 인원 수- 같은 번호가 될 때까지 계속해서 2로 나누는 연산: O(logN)더보기#include using namespace std;int solution(int n, int a, int b){ int answer = 0; do { a = (a + 1) / 2; b = (b + 1) / 2; ++answer; } while (a != b); return .. 2024. 12. 24. [PCCP] Lv2: 메뉴 리뉴얼(72411) 해설 문제- 문제 링크: 메뉴 리뉴얼 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: orders의 길이- M: course의 길이- orders의 각 주문을 정렬하는 시간 복잡도는 O(각 order의 길이 * NlogN)이고 각 order의 길이는 최대 10이므로 무시 가능- course만큼 순회하는 반복문에서 각 order의 조합을 만들 때 시간 복잡도는 O(2^N)- 조합의 개수만큼 최댓값을 구하는 과정과 가장 많이 주문된 구성을 찾는 과정의 시간 복잡도는 O(2^N)- course만큼 순회하므로 반복문의 시간 복잡도는 O(M*(2^N)*logM*(2^N))이지만 특정 조건에 맞는 조합이므로 이보다 작음- 최종 시간 복잡도.. 2024. 12. 24. 이전 1 2 3 4 5 6 7 다음 반응형
