반응형 [PCCP] Lv3: 정수 삼각형(43105) 해설 문제- 문제 링크: 정수 삼각형 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 삼각형의 높이- N*N 2차원 dp 테이블을 초기화할 때의 시간 복잡도는 O(N^2)-dp 테이블을 채우는 동작 또한 O(N^2)이므로 최종 시간 복잡도는 O(N^2)더보기#include using namespace std;int solution(vector> triangle) { int n = triangle.size(); vector> dp(n, vector(n, 0)); // dp 테이블 초기화 // dp 테.. 2024. 12. 26. [PCCP] Lv3: 기지국 설치(12979) 해설 문제- 문제 링크: 기지국 설치 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 전체 범위- W: 전파의 세기- 최악의 경우 location이 매번 2W + 1씩 증가하므로 N / (2W + 1)번 반복문을 수행- 최종 시간 복잡도: O(N/W)더보기#include using namespace std;int solution(int N, vector stations, int W) { int answer = 0; int location = 1; // 현재 탐색하는 아파트의 위치 int .. 2024. 12. 25. [PCCP] Lv3: 사라지는 발판(92345) 해설 문제- 문제 링크: 사라지는 발판 해설- 자료구조: - 시간복잡도: (풀이과정)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: board의 가로 길이- M: board의 세로 길이- 각 위치에서 상하좌우 4개의 경우의 수 존재- 최종 시간 복잡도: O(4^(M*N))더보기import ja.. 2024. 12. 25. [PCCP] Lv3: 외벽 점검(60062) 해설 문제- 문제 링크: 외벽 점검 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)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: dist의 길이- M: weak의 길이- weak 리스트에 항목을 추가하는 연산: O(M)- 이후 반복문에서 모든 weak 지점을 순회(M)하며 친구들의 순열을 모두 확인(N!)- 현재.. 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] 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] 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] 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 2 다음 반응형
