코딩테스트 준비105 [백준 2750번][C++] 수 정렬하기 - 9. 카운팅 정렬 #include #include #include #include #include #include #include #include #include #include #include using namespace std; void PositiveCountingSort(vector& v, int maxVal) { vector count(maxVal + 1); // 각 데이터 별 개수를 저장할 벡터 for (int i = 0; i < v.size(); i++) { count[v[i]]++; // 각 데이터 별로 갯수를 셈 } // 0부터 오름차순으로 정렬할 것이므로 0번은 구했던 값 그대로이기 때문에 1부터 시작 for (int j = 1; j < count.size(); j++) { // 자신의 값에 이전의 원소.. 2023. 7. 23. [백준 10816번] 숫자 카드 2 - unordered_map #include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { // 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; unordered_map SG; // 상근이의 카드더미 for (int i = 0; i > card; SG[card]++; // 카드 별로 갯수를 셈 } int M; cin >> M; .. 2023. 7. 22. [백준 1620번][C++] 나는야 포켓몬 마스터 이다솜 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { // 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; map book1; // 도감1 -> 번호로 이름찾기 map book2; // 도감2 -> 이름으로 번호찾기 for (int num = 1; num > name; book1.insert({ num,name }); book2.insert({ name,num }); .. 2023. 7. 21. [백준 2750번][C++] 수 정렬하기 - 8. 기수 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void RadixSort(vector& v, int maxRadix, int firstIndex) { // maxRadix는 [최대 자릿수 + 1] 이므로 그 이전까지만 반복을 진행 for (int i = 1; i 104, 103은 1번, 555는 5번, 777은 7번 // 0번 인덱스는 해당 자릿수의 값이 없는 경우 // ex) 100의 자릿수 검사 -> 1,.. 2023. 7. 21. [백준 2705번][C++] 수 정렬하기 - 7. 쉘 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void SkipInsertionSort(vector& v, int start, int skipNum) { // 숫자를 건너뛰는 삽입정렬 for (int i = start + skipNum; i = 0; j -= skipNum) { if (v[j] > originNum) { // 앞의 숫자가 더 큰 경우 v[j + skipNum] =.. 2023. 7. 20. [백준 7785번][C++] 회사에 있는 사람 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int n; cin >> n; map entry; for (int i = 0; i > name >> record; if (record == "enter") { // 들어온 경우 entry.insert({ name, true }); } else { // 나간 경우 -> 아예 삭제 entry.erase(name); } } for (map::iterator iter = entry.begin(); iter != entry.en.. 2023. 7. 20. [백준 14425번][C++] 문자열 집합 #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int result = 0; int N, M; cin >> N >> M; map map; for (int i = 0; i > s; map.insert({ s, true }); } for (int i = 0; i > s; if (map[s]) result++; } cout 2023. 7. 19. [백준 2705번][C++] 수 정렬하기 - 6.병합 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void Merge(vector& v, int left, int mid, int right) { int i = left; // 왼쪽 부분 시작지점 int j = mid + 1; // 오른쪽 부분 시작지점 int k = left; // 원소를 넣을 위치 vector sortedVec(v.size()); // 정렬된 벡터를 저장할 공간 // 왼쪽부분과 오른쪽 부분의 원소들을 하나씩 차례로 비교하여 더 작은 원소를 sortedVec에 넣음. // 왼쪽 부분과 오른쪽 부분은 이미 오름차순으로 정렬되어있는 상태이므로 .. 2023. 7. 19. [백준 2750번][C++] 수 정렬하기 - 5. 삽입 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void InsertionSort(vector& v) { for (int i = 1; i = 0; j--) { if (insertVal swap 아님 // -> 뒤의 원소에 앞의 원소의 값을 넣음 v[j + 1] = v[j]; insertIndex--; } else { /.. 2023. 7. 18. [백준 10815번][C++] 숫자 카드 - map #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { int N; cin >> N; map map; for (int i = 0; i > x; map.insert({ x, true }); } int M; cin >> M; vector v; for (int i = 0; i > x; v.push_back(x); } for (int i = 0; i M; for (int i = 0.. 2023. 7. 17. [백준 2750번][C++] 수 정렬하기 - 4. 힙 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; void MakeMaxHeap(vector& v) { // 최대힙을 생성하는 함수 // 완전이진트리의 노드번호는 1번부터 시작하기때문에 0번 인덱스를 1번으로 취급해야함 // 0번을 시작으로할때 // 자식노드번호가 홀수인 경우, 부모인덱스 = 자식 인덱스 / 2 // 자식노드번호가 짝수인 경우, 부모인덱스 = 자식 인덱스 / 2 - 1 for (int i = 1; i 가장 큰 수라면 밑 부터 차례.. 2023. 7. 17. [백준 2750번][C++] 수 정렬하기 - 3. 퀵 정렬 #include #include #include #include #include #include #include #include #include #include using namespace std; int Partition(vector& v, int left, int right) { // left번 인덱스부터 right번 인덱스를 pivot번 인덱스의 원소를 기준으로 큰 값, 작은 값을 나눔 int pivot = left; // 기준 인덱스 값(고정) int swap = left; // 중간중간 swap에 사용될 인덱스 값 for (int i = left + 1; i v[i]) { swap++; // swap(i swap) int temp = v[i]; v[i] = v[swap]; v[swap] = te.. 2023. 7. 16. 이전 1 ··· 5 6 7 8 9 다음
