반응형 [PCCP] Lv2: 가장 큰 정사각형 찾기(12905) 해설 문제- 문제 링크: 가장 큰 정사각형 찾기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: board의 행의 길이- M: board의 열의 길이- 벡터의 크기를 구하는 함수는 시간 복잡도 O(1)- 중첩 반복문은 총 N*M번 수행하므로 최종 시간 복잡도: O(N*M)더보기#include #include using namespace std;int solution(vector> board) { // 주어진 2차원 보드의 행과 열의 개수를 변수에 저장 int ROW = board.size(), COL = boa.. 2024. 12. 26. [PCCP] Lv2: 땅따먹기(12913) 해설 문제- 문제 링크: 땅따먹기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 행의 길이- 반복문은 총 16*N번 실행하므로 최종 시간 복잡도는 O(N)더보기#include #include using namespace std;int solution(vector> land) { // 각 행마다 이전 행의 최대 점수를 더해가며 최대 점수 누적 for (int i = 1; i solution 2)더보기#includesolution 3)더보기#include (C#)solution 1)더보기#includesoluti.. 2024. 12. 26. [PCCP] Lv2: 2xn 타일링(12900) 해설 문제- 문제 링크: 2xn 타일링 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 가로의 길이- 가로 길이가 1 또는 2인 경우는 단순 동작이므로 O(1)- 반복문은 N - 2번 수행하므로 시간 복잡도는 O(N)- 최종 시간 복잡도는 O(N)더보기#include using namespace std;long long solution(int n) { // 바닥의 가로 길이가 1이면 바닥을 채우는 방법의 수는 1 if (n == 1) { return 1; } // 바닥의.. 2024. 12. 25. [PCCP] Lv2: 피보나치수(12945) 해설 문제- 문제 링크: 피보나치수 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 피보나치의 문제에서 구할 N번째 항- N번째 피보나치 수를 구할 때까지 반복문은 N번 수행하므로 시간 복잡도는 O(N)더보기#include using namespace std;// 피보나치 수열의 n번째 값을 계산하는 함수int solution(int n) { vector fib = {0, 1}; // fib(0) = 0, fib(1) = 1 for (int i = 2; i solution 2)더보기#inclu.. 2024. 12. 25. [PCCP] Lv2: 귤 고르기(138476) 해설 문제- 문제 링크: 귤 고르기 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: tangerine의 길이- counter에 귤의 개수를 저장하는 시간 복잡도는 O(N)- 귤의 개수만 다시 sorted_counts에 넣고 내림차순으로 정렬: O(NlogN)- 반복문은 최악의 경우 모든 원소를 순회하므로 시간 복잡도는 O(N)- 최종 시간 복잡도: O(NlogN)더보기#include #include #include #include using namespace std;int solution(int k, v.. 2024. 12. 25. [PCCP] Lv2: 구명보트(42885) 해설 문제- 문제 링크: 구명보트 해설- 자료구조: - 시간복잡도: (풀이과정)1) 2) 3) 4) 코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: people의 길이- sort(): O(NlogN)- 반복문은 최악의 경우 people 배열 끝까지 반복하므로 최종 시간 복잡도: O(NlogN)더보기#include #include using namespace std;int solution(vector people, int limit) { sort(people.begin(), people.end()); // 몸무게를 오름차순으로 정렬 int count = 0; .. 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] 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 다음 반응형
