반응형 [PCCP] Lv1: 예산(12982) 해설 문제- 문제 링크: 예산 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: d의 길이- sort(): O(NlogN)- 반복문은 최악의 경우 모든 원소에 대해 반복하므로 시간 복잡도는 O(N)- 최종 시간 복잡도: O(NlogN)더보기#include #include using namespace std;int solution(vector d, int budget) { sort(d.begin(), d.end()); // 벡터 d를 오름차순으로 정렬 int count = 0; // 지원할 수 있.. 2024. 12. 25. [PCCP] Lv4: 지형 이동(62050) 해설 문제- 문제 링크: 지형 이동 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: land의 한 변의 길이- 각 지점을 방문하는데 필요한 시간 복잡도는 O(N^2)- 우선순위 큐를 활용해 너비 우선 탐색을 진행하므로 최종 시간 복잡도는 O(N^2 * log(N^2))더보기#include #include #include using namespace std;// 현재 칸의 좌표, 이전 칸에서 현재 칸으로 가는 비용struct Pos { int r; int c; int heightDiff; bool operator p.heightDiff; }};int dy[4] = {-1, 0, 1, 0};int dx[4] =.. 2024. 12. 25. [PCCP] Lv2: 튜플(64065) 해설 문제- 문제 링크: 튜플 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- updateCounts()에서 문자열 s의 길이를 N이라고 한다면, 문자열을 한번 순회하므로 시간 복잡도는 O(N)- 반복문 내부에 sort()가 있지만 각 숫자는 최대 10만이므로 6자리를 넘지 않아 무시 가능한 연산- solution()의 freqPairs를 정렬하는 부분에서 freqParis의 원소 개수를 M이라 한다면 시간 복잡도는 O(MlogM)- freqPairs를 순회할 때 시간 복잡도는 O(M)- 최종 시간 복잡도: O(N + M*logM + M) → O(N + M*logM)더보기#include #include using namespace s.. 2024. 12. 25. [PCCP] Lv2: 가장 큰 수(42746) 해설 문제- 문제 링크: 가장 큰 수 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: numbers의 길이- sort()에서 compare()을 기준으로 정렬. compare()는 두 수를 문자열로 변경한 후 조합해서 비교하는 함수- 각 수는 최댓값이 1,000이므로 문자열을 합칠 경우 최대 문자열의 길이는 7- 데이터가 N개일 때 정렬에 필요한 시간 복잡도는 O(NlogN)- 최종 시간복잡도는 O(7NlogN) → O(NlogN)더보기#include #include #include using namespace std;// 문자열로 바뀐 두 수를 조합해서 크기 비교bool.. 2024. 12. 25. [PCCP] Lv1: K번째 수(42748) 해설 문제- 문제 링크: K번째 수 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: array의 길이- M: commands의 길이- commands의 각 원소에 대해 배열을 자르는 시간 복잡도는 O(N)- 이후 정렬을 포함한 시간 복잡도는 O(NlogN)이고 이를 M번 반복하므로 최종 시간 복잡도는 O(M*(NlogN))더보기#include #include #include using namespace std;vector solution(vector array, vector> commands) { vector answer; vector subArray; for (const auto& cmd : comman.. 2024. 12. 25. [PCCP] Lv1: 정수 내림차순으로 배치하기(12933) 해설 문제- 문제 링크: 정수 내림차순으로 배치하기 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 주어진 숫자- 주어진 숫자의 자릿수는 대략 logN이고 이를 문자열로 만드는 작업에 걸리는 시간 복잡도는 O(logN)- 이후 문자열을 sort()함수로 정렬하는 시간 복잡도는 O(logN * log(logN))- 최종 시간 복잡도: O(logN * log(logN))더보기#include #include using namespace std;long long solution(long long n) { // 숫자를 문자열로 변환 string str = to_strin.. 2024. 12. 25. [PCCP] Lv1: 문자열 내 마음대로 정렬하기(12915) 해설 문제- 문제 링크: 문자열 내 마음대로 정렬하기 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: strings의 길이- S: strings의 문자열의 길이- 각 문자열을 비교하면서 정렬하므로 시간 복잡도는 O(N*S*logN)더보기#include #include #include using namespace std;int idx; // 비교 함수bool compare(string a, string b) { return a[idx] == b[idx] ? a solution(vector strings, int n) { idx = n; // 각 문자.. 2024. 12. 25. [PCCP] Lv0: 캐릭터의 좌표(120861) 해설 문제- 문제 링크: 캐릭터의 좌표 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: keyinput의 길이- 반복문은 keyinput 길이만큼 반복하고, 내부 연산은 모두 시간 복잡도가 O(1)- 최종 시간 복잡도: O(N)더보기#include #include using namespace std;vector solution(vector keyinput, vector board){ // 현재 위치를 나타 내는 크기가 2이고 값이 모두 0인 벡터 선언 vector v(2,0); // 키 입력순으로 캐릭터 이동 for(string s : keyinput){ if (s=="up" &&.. 2024. 12. 25. [PCCP] Lv2: 점프와 순간 이동(12980) 해설 문제- 문제 링크: 점프와 순간 이동 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: 입력으로 주어진 숫자- N을 2진수로 변환할 때 시간 복잡도는 O(logN)- 변환된 문자열의 길이는 최대 logN이므로 문자열에서 "1"을 셀 때의 시간 복잡도는 O(logN)- 최종 시간 복잡도: O(logN)더보기#include using namespace std;int solution(int N) { return bitset(N).count(); // 2진수로 변환한 N의 1의 개수를 반환}solution 2)더보기#includesolution 3)더보기#include (C#)solution 1)더보기#includesolution.. 2024. 12. 25. [PCCP] Lv2: 카펫(42842) 해설 문제- 문제 링크: 카펫 코드(C언어)solution 1)더보기#includesolution 2)더보기#include (C++)solution 1)- N: total_size- 한 변의 최대 길이는 sqrt(N)이므로 최종 시간 복잡도는 O(sqrt(N))더보기#include #include using namespace std;vector solution(int green, int white) { // 격자의 총 개수 (파란색 격자 + 흰색 격자) int total_size = green + white; // 세로 길이의 범위는 3부터 (파란색 격자 + 흰색 격자)의 제곱근 for (int vertical = 3; vertical #include using namespace std;void pri.. 2024. 12. 25. 이전 1 2 3 4 5 ··· 7 다음 반응형
