본문 바로가기

Algorithm

 (57)
[백준] 10989번: 수 정렬하기3 문제 링크 : https://www.acmicpc.net/problem/10989 문제 풀이 Counting sort로 풀었다. 계수 정렬 게시글 https://manzoo.tistory.com/57 의 소스 코드로 제출하였더니 메모리 초과가 났다. 문제를 다시 자세히 보니 메모리 제한이 8MB로 걸려져 있었다. 하지만 데이터 값은 10000을 넘지 않는다는 조건이 있었다. 그래서 입력 데이터 수 만큼 배열을 할당하지 않고 카운트 배열만 10001만큼 할당을 받았다. 입력받는 대로 바로 count 배열에 저장한 후, 앞에서부터 개수만큼 출력을 했다. 하지만 그대로 제출하니 시간초과가 떴다. cin → scanf cout → printf 로 변경하니 시간초과가 뜨지 않았다. 소스코드 /* * 백준 1098..
[Algorithm] 정렬 - 계수 정렬 (Counting Sort) 계수 정렬(Counting Sort)이란? - 데이터 값을 직접 비교하지 않고, 단순하게 개수를 세어 기록하고 정렬하는 방식이다. - 값 비교가 일어나지 않기 때문에 속도가 매우 빠르다. - 하지만 개수를 저장하는 배열, 정렬할 배열을 위한 추가 공간이 필요하다. - 또한 숫자가 매우 큰 경우에는 속도가 현저히 느려질 수 있다. 작동 방식 1) 데이터 중 제일 큰 수 + 1의 크기로 카운트 배열을 만든다. (아래 예시에서는 4 = 크기가 5인 배열 할당) 2) 카운트 배열에 각 숫자가 몇 번 나타나는지 개수를 세어 해당 인덱스에 저장한다. (숫자 2는 두 번 나타나므로, 카운트 배열 인덱스 2에 2를 저장) 3) 누적합을 만든다. (이 전 숫자를 더한다.) 누적합이 의미하는 것은 정렬되는 위치이다. 0의..
[Algorithm] 정렬 - 힙 정렬 (Heap Sort) 힙 정렬(Heap Sort)이란? - 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다. 작동 방식 [초기 배열] 1) 배열 값 순서대로 부모노드 - 왼쪽 자식 - 오른쪽 자식 순서대로 완전 이진트리를 구성한다. 2) 최대 힙이 되도록 힙을 구성한다. - 자식 노드를 비교하여 더 큰 값을 찾는다. - 부모노드보다 큰 지 비교한 후, 부모노드보다 크면 값을 교환한다. - 루트까지 반복한다. 3) 루트와 마지막 단말 노드(자식이 없는 노드) 값을 교체한 후 노드를 제거한다. 4) 변경된 트리를 다시 최대 힙이 되도록 재구성한다. (2~3 반복) 2~3번 작업을 반복하게 되면, 최대 힙이 되도록 재구성할 때마다 루트에 최댓값이 오게 된다. 4번 작업을 통해 가장 큰 값이 배열의 가장 오른쪽 끝 인덱..
[Algorithm] 정렬 - 빠른 정렬 (Quick Sort) 빠른 정렬(Quick Sort)이란? - 피벗을 하나 정한 후 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬하는 방식이다. - 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. - 분할 정복 알고리즘의 하나이다. - 불안정 정렬에 속한다. * 안정 / 불안정 정렬 동일한 값에 대해 기존의 순서가 유지되는지 여부에 따라 안정 / 불안정 정렬로 구분된다. 작동 방식 1) 피벗을 정한다. 2) 데이터의 양쪽 끝 값과 피벗을 비교한다. 3) 왼쪽 값이 피벗보다 크고, 오른쪽 값이 피벗보다 작으면 두 값을 서로 교체한다. 4) 만약 왼쪽 값이 피벗보다 작거나, 오른쪽 값이 피벗보다 크면 교체하지 않는다. 5) 한차례 비교하게 되면, 피벗을 기준으로 피벗보다 작은 값들은 피벗 ..
[Algorithm] 정렬 - 합병 정렬 (Merge Sort) 합병 정렬(Merge Sort)이란? - 작은 조각까지 나눠, 조각을 병합하면서 정렬하는 방식이다. - 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속한다. - 분할 정복 알고리즘의 하나이다. 작동 방식 1) 리스트를 절반으로 계속해서 나눈다. (분할) 2) 가장 작은 단위로 나눠지면, 나눠진 두 조각의 값들을 비교한다. 3) 두 리스트를 비교하면서 하나의 정렬된 리스트에 값을 정렬한다. (합병) 소스코드 #include using namespace std; int* sorted; void mergeSort(int* arr, int left, int right); void merge(int* arr, int left, int right); int main() { int N; cin >> N; s..
[백준] 2750번: 수 정렬하기 문제링크 : https://www.acmicpc.net/problem/2750 문제풀이 삽입정렬, 거품정렬, 선택정렬 방식을 이용해 풀었다. 소스코드 /* * 백준 2750번: 수 정렬하기 */ #include using namespace std; void insertionSort(int* arr, int len); void bubbleSort(int* arr, int len); void selectionSort(int* arr, int len); int main() { int N; cin >> N; int* arr = new int[N]; for (int i = 0; i > arr[i]; } selectionSort(arr, N); for (int i = 0; i < N;..
[Algorithm] 정렬 - 선택 정렬 (Selection Sort) 선택 정렬(Selection Sort)이란? 가장 작은 값을 찾아 앞으로 차례로 옮기는 방식이다. 예) 1) 배열의 첫번째 값을 min값으로 설정한다. 2) 두번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다. 3) min값을 가장 첫번째 값과 교체한다. 4) 배열의 두번째 값을 min값으로 설정한다. 5) 세번째 값부터 마지막 값까지 비교하여, min보다 작은 값이면 그 값을 min값으로 설정한다. 6) 두번째 값과 min값을 교체한다. 이 작업을 반복하게 되면 작은 값부터 차례로 정렬이 된다. 소스코드 #include using namespace std; void selectionSort(int* arr, int len); int main() { int N; ..
[Algorithm] 정렬 - 거품 정렬 (Bubble Sort) 거품 정렬(Bubble Sort)이란? 앞에서부터 차례로 두 개씩 비교하여, 작은 값을 앞으로 정렬하는 방식이다. 예) 1) 맨 앞부터, 두 개의 값인 arr[0]과 arr[1]을 비교한다. 2) arr[0]값이 더 크므로 두 값을 교체한다. (작은 값을 앞으로) 3) 그 다음 두 개 값인 arr[1]과 arr[2]를 비교한다. arr[2]값이 더 크므로 교체하지 않고 넘어간다. 4) 그 다음 두 개 값인 arr[2]와 arr[3]을 비교한다. arr[3]값이 더 크므로 교체하지 않고 넘어간다. 5) 그 다음 두 개 값인 arr[3]과 arr[4]를 비교한다. 6) arr[4]값이 더 크므로 두 값을 교체한다. 이렇게 1회전을 돌면 제일 큰 값이 맨 뒤에 오게 된다. 따라서 2회전을 돌 때에는, 제일 마..

티스토리툴바