본문 바로가기
반응형
[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.
[C++로 배우는 알고리즘과 자료구조 심화] Day 22: 고급 정렬 알고리즘 (TimSort, IntroSort) 고급 정렬 알고리즘정렬 알고리즘은 데이터 처리와 분석에서 매우 중요한 역할을 합니다. 오늘은 두 가지 고급 정렬 알고리즘인 TimSort와 IntroSort에 대해 학습하겠습니다. 이 두 알고리즘은 효율성과 안정성 측면에서 매우 강력하며, 실세계에서 널리 사용됩니다.TimSortTimSort는 삽입 정렬과 병합 정렬을 혼합한 하이브리드 정렬 알고리즘입니다. 이 알고리즘은 실제 데이터가 부분적으로 정렬되어 있는 경우 매우 효율적입니다. Python의 sort() 함수와 Java의 Arrays.sort()에서 사용되는 기본 정렬 알고리즘이기도 합니다.TimSort의 주요 단계Runs 분할: 주어진 배열을 일정 크기(기본적으로 32 또는 64)로 분할하여 각각을 정렬합니다.Runs 병합: 병합 정렬을 사용하여.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 20: 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort)힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.힙 정렬의 주요 단계:힙 구성 (Heapify): 배열을 이진 힙으로 변환합니다.정렬 (Sort): 힙의 루트 요소를 제거하고, 힙을 재구성하여 정렬된 배열을 만듭니다.힙 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n \log n))최선의 경우: (O(n \log n))힙 정렬 구현힙 구성 함수힙 속성을 유지하면서 배열을 이진 힙으로 변환합니다.#include #include // 힙 구성 함수void heapify(std::vector& arr, int n, int.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 19: 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort)퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 피벗(Pivot)을 기준으로 두 개의 하위 배열로 나눈 다음, 각각을 정렬합니다. 퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘으로 간주됩니다.퀵 정렬의 시간 복잡도:평균의 경우: (O(n \log n))최악의 경우: (O(n^2))최선의 경우: (O(n \log n))퀵 정렬의 공간 복잡도:(O(\log n)) (재귀 호출 스택 공간)퀵 정렬 구현퀵 정렬의 주요 단계:분할 (Partition): 피벗을 기준으로 배열을 두 부분으로 나눕니다.정복 (Conquer): 하위 배열을 재귀적으로 정렬합니다.결합 (Combine): 분할된 하위 배열이 정렬된 상태이므로 추가.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 16: 버블 정렬과 선택 정렬 버블 정렬 (Bubble Sort)버블 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸면서 배열을 정렬합니다. 배열의 끝까지 이 과정을 반복하면 가장 큰 값이 맨 끝에 위치하게 됩니다. 이 과정을 여러 번 반복하여 배열이 정렬될 때까지 진행합니다.버블 정렬의 시간 복잡도:최선의 경우: (O(n))평균의 경우: (O(n^2))최악의 경우: (O(n^2))버블 정렬 구현#include #include // 버블 정렬 함수void bubbleSort(std::vector& arr) { int n = arr.size(); for (int i = 0; i arr[j + 1]) { std::swap(arr[j], arr[j +.. 2024. 8. 1.
반응형

티스토리툴바