알고리즘&자료구조/정렬5 라딕스 정렬 십진수에서 특정 자릿수를 추출하는 방법x를 10의 a승으로 나눈 몫을 가져오는 것은 추출하고자 하는 자릿수가 일의 자리로 이동하도록 하는 과정이다."123"에서 1번째 자릿수인 1을 일의 자리로 취하기 위해서 10의 2승으로 나눈 몫을 가져온다.1이 위치한 곳은 100(백) 단위기 때문에 10의 2승인 100으로 나눠야지 1을 일의 자리로 이동시킬 수 있다.주어진 숫자가 십진수이기 때문에 10으로 나눈 나머지는 0~9 사이의 값이 나온다.왜냐하면 십으로 나누면 십 이상의 자릿수는 모두 사라지기 때문에 0~9 사이의 일의 자리만 나머지가 발생함코드import java.util.*;public class Main2 { // 알고리즘을 왜? 풀어야지에 대한 의문이 계속해서 생김 왜 그럴까? .. 2024. 6. 22. 카운트 소트 #include using namespace std;int freq[2000001]; // 각 수의 등장 횟수를 저장하는 배열int n;int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i > a; // ex) 2라는 정수를 입력받으면 2가 몇 번 나오는지 카운트 함 // freq[2]의 의미는 2라는 정수가 몇 번 나왔는지의 횟수를 의미함 // -백만을 해준 이유는 문제에서 -백만의 값이 주어질 수 있기 때문에 인덱스를 양수로 변환 // freq[-백만] -> 인덱스에는 음수가 불가능하기 때문에 문제에서 가장 작은 음수값이 주어졌을 때 0이 되는 값을 더해줘야됨 freq[a + 100000.. 2024. 6. 21. 퀵 소트 import java.util.Scanner;public class Main2 { static int[] arr = new int[100]; static public void quickSort(int st, int ed) { // ex) arr = [3, 1, 4] // [0]을 pivot으로 잡아서 왼쪽에는 pivot보다 작은 값 오른쪽에는 pivot보다 큰 값 세팅 // pivot보다 작은 왼쪽 리스트와 큰 오른쪽 리스트 두 개로 나뉨 리스트가 1이 될때까지 반복 // 왼쪽 리스트는 pivot보다 작은 수들의 집합이지만 그 안에서 정렬이 안되어 있기 때문에 정렬이 되어 있는 최소단위인 1까지 반복해야 함 // ex) arr =[3] 데이터가 하나 있는 경우는 재귀적으로 반복하지 않고.. 2024. 6. 17. 백준 2751 Merge Sort 구현#include using namespace std;int n;int arr[1000005];int tmp[1000005];void merge(int st, int ed) { int mid = (st + ed) / 2; int lIndex = st; int rIndex = mid; for (int i = st; i = ed) tmp[i] = arr[lIndex++]; else if (arr[lIndex] > n; for (int i = 0; i > arr[i]; mergeSort(0, n); for (int i = 0; i 2024. 6. 16. 이전 1 2 다음
