정렬4 SW 문제해결 기본 - Array 2 1. 2차원 Array ① 2차원 Array의 선언 2차원 이상의 다차원 Array는 차원에 따라 인덱스를 선언한다. 2차원 Array의 선언은 세로 길이(행의 개수), 가로 길이(열의 개수)를 필요로 한다. ② 2차원 Array의 순회 순회란 Array의 모든 원소를 모두 조회하는 것을 말한다. 행 우선 순회, 열 우선 순회, 지그재그 순회가 있다. 지그재그 순회 첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Array의 원소를 조사하는 방법 int i;// 행의 좌표 int j;// 열의 좌표 for i from 0 to n-1 for j from 0 to m-1 Array[i][j + (m-1-2*j) * (i%2)]; ③ 델타를 이용한 2차 Array 탐색 델타의 개념을 이용하여 2차 Array.. 2019. 4. 29. [BOJ] 10989. 수 정렬하기 3 (Counting Sort) https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 처음에 Counting Sort로 풀라길래 정석적인 Counting Sort로 풀었는데 메모리 초과가 나서 게시판을 참고해서 줄이고 줄여서 풀었다. 원래 정렬 전 배열과 정렬 후 배열도 가지고 있었는데 N이 10,000,000 이하이기 때문에 10,000,000짜리 배열을 두 개나 가지고 있으니 메모리 차지를 많이 할 수 밖에 없었다. 그래서 입력 받은 수를 배열에 저장하지 않고 바로 numbersCnt 배열로 계.. 2019. 4. 28. [BOJ] 2750. 수 정렬하기 (Bubble Sort) https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include using namespace std; int N, numbers[1000]; void bubbleSort(int cnt); void print(); int main() { cin.tie(0); ios::sync_with_stdio(0); cin >> N; for (int i = 0; i > numbers[i]; } bubbleSort(0);.. 2019. 4. 27. 정렬 알고리즘 비교 알고리즘 평균 수행시간 최악 수행시간 알고리즘 기법 비고 버블 정렬(Bubble Sort) O(n^2) O(n^2) 비교와 교환 코딩이 가장 손쉬움 계수 정렬(Counting Sort) O(n+k) O(n+k) 비교환 방식 n이 비교적 작을 때만 가능함 선택 정렬(Selection Sort) O(n^2) O(n^2) 비교와 교환 교환의 횟수가 버블, 삽입정렬보다 작음 퀵 정렬(Quick Sort) O(n long n) O(n^2) 분할 정복 최악의 경우 O(n^2) 이지만, 평균적으로는 가장 빠름 삽입 정렬(Insertion Sort) O(n^2) O(n^2) 비교와 교환 n의 개수가 작을 때 효과적 병합 정렬(Merge Sort) O(n long n) O(n long n) 분할 정복 연결리스트의 경우 .. 2019. 4. 27. 이전 1 다음
